내가 전에 면접 문제로 풀어본 문제다 난 히스토그램 문제랑 비슷하게 생각해서 했는데 탈락했다 ㅋㅋ
다시 풀어보자 여러 방법으로 과연 내가 왜 틀렸던 것인가 풀이가 틀린게 아니라면 내가 못알아 듣게 말한게 큰거 같다.
면접에서 일단 첫구현인 내가 생각했던 방법이다.
틀렸따. ㅋㅋ
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
for(int i=0;i<height.size();i++)
{
int left = i,right= i;
while(left-1 >=0 && height[left-1] > height[left]){
left -= 1;
}
while(right+1 < height.size() && height[right] < height[right+1]){
right += 1;
}
cout << left << " "<< right<< "\n";
int smaller_height = min(height[left],height[right]);
for(int j = left+1;j<right && height[i] < height[left] && height[i] < height[right]; j++){
cout << sum <<"\n";
if(smaller_height - height[j] > 0 )
sum += (smaller_height - height[j]);
}
i = right;
}//for
return sum;
}//trap
};
반례
[5,2,1,2,1,5]
결국 양쪽에 엄청 높은게 있으면 우물안에서는 양쪽에서 어느 기둥이 가장 높은것인지 알 수 없었다.
난 히스토그램 문제랑 비슷하다고 생각했다. 근데 그냥 하다 떠오른 생각인데 안된다 생각했는데 이게 더 맞는거 같다. 그냥 세그먼트 트리 이용해서 양쪽에서 가장 높은 기둥 찾으면 되는거 아닌가?
그리고 써보니까 릿코드 문제 좋은거 많은거 같다. 꼭 풀어보자 ㅋㅋ
일단 좀 고쳐보았따.
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
for(int i=0;i<height.size();i++)
{
int left = i,right= i;
while(left-1 >=0 && height[left-1] > height[left]){
left -= 1;
}
while(right+1 < height.size() && (height[right] < height[right+1]) ){
right += 1;
}
//이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에
//왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
//세그 먼트 트리 이용?
cout << left << " "<< right<< "\n";
int smaller_height = min(height[left],height[right]);
for(int j = left+1;j<right && height[i] < height[left] && height[i] < height[right]; j++){
cout << sum <<"\n";
if(smaller_height - height[j] > 0 )
sum += (smaller_height - height[j]);
}
i = right;
}//for
return sum;
}//trap
};
이 문제는 왜 직관적으로 그냥 풀면 틀리는 걸까 음.... 히스토그램 처럼 왼쪽에 가장 큰 놈을 저장해놓는 다면? 근데 이 풀이를 왜 이렇게 외워서 하는거 같지 자연스럽게 도출해보자...
다른 방법을 생각해 보았다.
기둥 들이 있을때 해당 위치에서 양쪽에 가장 긴 두 벽을 찾아야 한다. 그리고 그중에 더 짧은 벽의 길이를 알면 된다.
일단 가장 긴 두개를 찾고 그 영역을 제외한 (각 끝 기둥은 포함하는) 양쪽 영역에서 다시 가장 긴 길이를 찾으면 분할 정복으로 풀릴거 같다.
근데 같은게 여러개 있으면 제대로 작동 안한다....... 그러면 우선순위를 좀 주어야 하는데 인덱스에 따라서 좀 준다 치면 세그먼트 트리가 두가지 요인 인덱스,높이로 고를 수 있다.... 복잡해짐 다른 쉬운 방법은 없나.
보다가 알았는데 일단 기본은 빅 O를 생각하지 말고 풀어보자. 다시 원점에서 ㅋㅋ;; 이전에는 잘못 풀었으니까
낼하장
그냥 지금 해봤는데, 한개 기둥 정하고, 오른쪽으로 가면서 그 기둥보다 크거나 같은걸 찾으면 된다. 그냥 그러면 되는거 아닌가....
그런데 그럼 주어진 예제의 맨 오른쪽을 찾지 못하니까 그런 경우는 그냥 가장 높은걸 기준으로 하면 될듯?
[0,1,0,2,1,0,1,3,2,1,2,1]
컴파일 에러;;
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
int left,right;
for(left=0;left<height.size();left++)
{
//right를 구한다.
while(height[left] > height[right] && right < height.size() ){
right++;
}
//left - right 사이 면적 계산.
int min_height = min(height[left],height[right]);
for(int j=left+1;j<right;j++){
if( min_height - height[j] >0 )
sum += min_height - height[j];
}
//left = right
left = right;
}//for
return sum;
}//trap
};
고쳤는데 여전히;
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
int left,right;
int max_right_ind;
for(left=0;left<height.size();)
{
//right를 구한다.
right = left+1;
max_right_ind = right;
while(height[left] > height[right] && right < height.size() ){
right++;
if(height[right] >= height[max_right_ind])
max_right_ind = right;
}
if(right == height.size())
right = max_right_ind;
// cout << left<<" "<< right<<"\n";
//left - right 사이 면적 계산.
int min_height = min(height[left],height[right]);
for(int j=left+1;j<right;j++){
if( min_height - height[j] >0 ){
sum += min_height - height[j];
// cout << sum<<"\n";
}
}
//left = right
left = right;
}//for
return sum;
}//trap
};
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
for(int i=0;i<height.size();i++)
{
int left = i,right= i;
while(left-1 >=0 && height[left-1] > height[left]){
left -= 1;
}
while(right+1 < height.size() && (height[right] < height[right+1]) ){
right += 1;
}
//이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에
//왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
//세그 먼트 트리 이용?
// cout << left << " "<< right<< "\n";
int taller = max(height[left],height[right]);
int left_max;
int right_max;
if(height[left] < taller){
left_max = left;
while(left-1 >=0 && height[left] <= taller){
left -= 1;
// cout << left<<"\n";
if(height[left_max] <= height[left]){
left_max = left;
}
}
left = left_max;
}
else if(height[right] < taller){
right_max = right;
// cout << "rm :"<<right_max<<"\n";
while(right+1 < height.size() && height[right] <= taller){
right += 1;
if(height[right_max] <= height[right]){
// cout << "r :"<<right<<"\n";
right_max = right;
}
}
right = right_max;
}
int smaller_height = min(height[left],height[right]);
// cout << left << " "<< right<< "\n\n";
// cout << smaller_height<<"\n";
for(int j = left+1; j<=right; j++){
// cout << j<<"\n";
if(smaller_height - height[j] > 0 ){
// cout << smaller_height - height[j]<<"\n";
sum += (smaller_height - height[j]);
}
// cout << sum <<"\n";
}
i = right;
}//for
return sum;
}//trap
};
[7,6,7,6,9]
결국 맞았따. 좀 복잡하다. ㅋㅋ
class Solution {
public:
int trap(vector<int>& height) {
int cur;
int sum=0;
for(int i=0;i<height.size();i++)
{
int left = i,right= i;
while(left-1 >=0 && height[left-1] > height[left]){
left -= 1;
}
while(right+1 < height.size() && (height[right] < height[right+1]) ){
right += 1;
}
//이때 왼쪽 기둥이 오른쪽에서 찾은 기둥보다 높으면, 찾은 오른쪽 볼록 기둥 기준 오른쪽에
//왼쪽 기둥 보다 높은 기둥이 있는 지 확인해야 한다.
//세그 먼트 트리 이용?
// cout <<"1st: "<< left << " "<< right<< "\n";
int taller = max(height[left],height[right]);
int left_max;
int right_max;
// cout << "taller: "<<taller<<"\n";
if(height[left] < taller){
left_max = left;
while(left-1 >=0 && height[left] < taller){
left -= 1;
// cout << left<<"\n";
if(height[left_max] <= height[left]){
left_max = left;
}
}
left = left_max;
}
else if(height[right] <= taller){
right_max = right;
// cout << "rm :"<<right_max<<"\n";
while(right+1 < height.size() && height[right] <= taller){
right += 1;
if(height[right_max] <= height[right]){
// cout << "r :"<<right<<"\n";
right_max = right;
}
}
right = right_max;
}
int smaller_height = min(height[left],height[right]);
// cout << left << " "<< right<< "\n\n";
// cout << smaller_height<<"\n";
for(int j = left+1; j<=right; j++){
// cout << j<<"\n";
if(smaller_height - height[j] > 0 ){
// cout << smaller_height - height[j]<<"\n";
sum += (smaller_height - height[j]);
}
// cout << sum <<"\n";
}
i = right;
}//for
return sum;
}//trap
};
섭미션이나, 다른 넥스트 챌린지를 보니까 도움이 많이 된다. 일단 이 유형을 다른 사람들은 어떻게 풀었는지 좀 보자. 남의 코드도 걸린 시간 별로 볼 수 있다.
0ms 시간대.....
class Solution {
public:
int trap(vector<int>& height) {
if(height.size() == 0) return 0;
int len = height.size();
int max_r[len];
int curr;
max_r[len-1] = height[len-1];
for(int i = len-1; i > 0; i--){
if(height[i-1] > max_r[i]){
max_r[i-1] = height[i-1];
} else {
max_r[i-1] = max_r[i];
}
}
int max_l = height[0];
int diff = 0;
int totalWater = 0;
for(int i = 1; i < len-1; i++){
if(height[i] > max_l){
max_l = height[i];
}
diff = min(max_r[i], max_l) - height[i];
if(diff > 0){
totalWater = totalWater + diff;
}
}
return totalWater;
}
};
이 방법은 dp에 가까운거 같다. 즉
max_r[i]의 정의가 중요한데
i번째 위치의 오른쪽에 위치한 물이 담기는 기둥이다.
나는 오른쪽,왼쪽에서 가장 큰 벽을 찾는것을 매우 비효율적으로 했다. 어떻게 위 처럼 그냥 좌우에서 쭉 오면서 바로 결정할 수 있음을 알았지?
그런데 약간 비슷한 논리인데 이분 풀이가 훨씬 간결하다. 이 분은 그냥 어차피 가두리 양쪽중 작은 쪽을 기준으로 물이 차니까 아래처럼 한번에 풀 수 있다.
public int trap(int[] A){
int a=0;
int b=A.length-1;
int max=0;
int leftmax=0;
int rightmax=0;
while(a<=b){
leftmax=Math.max(leftmax,A[a]);
rightmax=Math.max(rightmax,A[b]);
if(leftmax<rightmax){
max+=(leftmax-A[a]); // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
a++;
}
else{
max+=(rightmax-A[b]);
b--;
}
}
return max;
}
히스토그램
[https://www.acmicpc.net/blog/view/12] 백준 풀이.
이런 말이 있다.
히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때, 가장 넓이가 큰 직사각형을 찾아야 합니다.
모든 막대 x에 대해서, x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾아야 합니다.
이렇게 명확히 하니 일단은 다른 아예 문제다 ㅋㅋ
음 아닌가 다시 생각하니 내가 왜 비슷하다 생각한지 알거 같다. 나도 비슷하게 해석했다. 답을 구하려면 현재 위치에서 만들 수 있는 가장 깊은 골을 만든다 생각한 것이다.!! 하지만 직사각형을 만드는 것과는 조금 다를 수도 있는것이다.
'알고리즘 문제 풀기' 카테고리의 다른 글
투포인터 - 백준:2143번 두 배열의 합 (0) | 2020.02.26 |
---|---|
백준 1806번 : 부분합(투포인터) (0) | 2020.02.26 |
백준 2517번 : 달리기 (0) | 2020.02.25 |
백준 2580번 스도쿠, 1799번 비숍 (0) | 2020.02.24 |
백준 2098번: 외판원 순회, 9251번 lcs (0) | 2020.02.14 |