[알고스팟] 울타리 쳐내기(FENCE)

[알고스팟] 울타리 쳐내기(FENCE)

목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "울타리 쳐내기"를 풀어보자

문제 URL

풀이

이 문제를 푸는 열쇠는 스택과 스위핑 알고리즘입니다. 스위핑 알고리즘이란 간단히 말해서 이미 연산이 진행된 이전 공간에 대해서는 연산을 하지 않는다라고 생각하시면 됩니다. 개념 자체는 쉽습니다만... 굉장히 생각하기 어렵다는게 함정입니다. 이 문제를 예를 들어 설명하겠습니다. 이 문제에서 우리가 사각형을 구하기 위해 필요한 정보는 그 사각형의 왼쪽 끝과 오른쪽 끝 그리고 높이입니다. 높이가 오른쪽 끝점의 높이라고 했을 때, 왼쪽으로 연속된 판자들 중 이 높이를 포함하는 가장 낮은 지점이 왼쪽 끝 점이 되겠죠. 이 성질을 이용해서, 문제를 푸는 것이죠.

그래서 어떻게 풀 것이냐? 우리가 관심 있는 것은 지점 index 입니다. 따라서 스택에 인덱스를 저장하고, 너비를 구할때, 혹은 스택에서 꺼낼 때, 울타리의 높이를 접근하면 됩니다. 그럼 언제 index를 꺼내야 끝 점의 정보를 얻을 수 있을까요? 그것은 스택에 나중에 저장된 위치의 울타리보다, 현재 울타리 위치가 낮을 때, 그 이전 울타리의 영역을 계산해 주면 됩니다. 다만, 스택에서 지점을 뺄 때, 스택이 비어있는지는 확인을 해보아야 합니다. 이제 예제를 통해서 동작을 이해해봅시다. 첫 번째 예제 입력은 다음과 같습니다.(C는 생각하지 않습니다)

• N = 7
• fences = [7, 1, 5, 9, 6, 7, 3]
  
  

| fences | 7 | 1 | 5 | 9 | 6 | 7 | 3 |

| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

이 때 스택을 생성해 줍니다.

st = [], answer = 0

자 이제 0 ~ N-1 까지 스택에 index를 순회합시다. 다만, 위에서 말한 것을 바꿔 말하면 스택이 비지 않고, 가장 나중에 저장된 위치의 울타리 높이가 현재 위치의 울타리 높이보다 크거나 같다면, 스택에서 빼주어야 합니다. 따라서 다음처럼 동작하게 됩니다.

--------------------------------------------------------------------------------------------------------------------------------------

index = 0, fences[index] = 7

0일 때는 스택이 빈 상태이기 때문에 반복문을 타지 않고, index를 스택에 넣어줍니다.

st = [0], answer = 0

--------------------------------------------------------------------------------------------------------------------------------------

index = 1, fences[index] = 1

st = [0]

이 때, 스택은 비지 않았고 스택의 가장 나중에 저장된 위치 0의 위치의 울타리 높이는 7로 현재 울타리 높이보다 큽니다. 그래서 스택에서 빼고 사각형의 너비를 계산해주어야 합니다. 이 때, 스택이 비게 되는데, 이 때는 너비를 현재의 index로 해 줍시다. 그러면 사각형의 넓이는 너비 * 높이, 높이는 fences[스택에서 뺴온 위치]이므로 7이 됩니다. 사각형이 계산될 때 마다 넓이를 갱신해주면 됩니다. 이 연산 끝에 이제 현재 index를 넣어주어야 합니다.

st = [1], answer = 7

계속 보겠습니다.

--------------------------------------------------------------------------------------------------------------------------------------

index = 2, fences[index] = 5

st = [1]

현재 위치의 울타리 높이 5는 스택에서 가장 나중에 저장된 위치 1의 높이인, 1보다 크기 때문에 반복문을 타지 않고 index를 스택에 저장합니다.

st = [1, 2], answer = 7

--------------------------------------------------------------------------------------------------------------------------------------

index = 3, fences[index] = 9

st = [1, 2, 3], answer = 7

--------------------------------------------------------------------------------------------------------------------------------------

index = 4, fences[index] = 6

이 때, 현재 위치의 울타리 높이 6보다 스택에서 가장 나중에 저장된 위치의 높이(fences[3] = 9)가 크기 때문에 스택에서 3을 뺴주어야 합니다. 이 떄는 스택이 비지 않았는데, 이 떄의 너비는 index - 현재 스택에 나중에 저장된 울타리의 높이 - 1입니다. 그러면, 3이 빠지고 가장 나중에 저장된 높이는 2이기 떄문에, 너비는 4(index) - 2(현재 스택에서 나중에 저장된 울타리 위치) - 1 = 1 높이는 9이므로 넓이는 9이고 갱신해주면 됩니다.

st = [1, 2], answer = 9

그 후, 2의 높이는 5이기 때문에 현재 울타리 높이 6보다 적으므로 스택에서 뺴주는 것을 멈춥니다. 그 후, 현재 index를 저장합니다.

st = [1, 2, 4], answer = 9

--------------------------------------------------------------------------------------------------------------------------------------

index = 5, fences[index] = 7

이 떄는, 현재 울타리의 높이 7이, 스택에서 가장 나중에 저장된 위치 4의 높이가 6보다 크기 때문에, 반복분을 타지 않고 저장됩니다.

st = [1, 2, 4, 5], answer = 9

--------------------------------------------------------------------------------------------------------------------------------------

index = 6, fences[index] = 3

현재 울타리 높이 3보다 가장 나중에 저장된 위치의 울타리 높이(fences[5] = 7)가 더 크기 떄문에 스택에서 뺴주고, 스택이 비지 않았기 때문에 위의 공식을 적용하여 너비 1(6-4-1=1)을 이용해 사각형 넓이를 구합니다. (높이 7 x 너비 1 = 7) answer 보다는 적으므로 갱신은 되지 않습니다.

st = [1, 2, 4], answer = 9

그 후 위치 4의 울타리 높이 6(fences[4]=6) 역시 현재 높이 3보다 크기 때문에 스택에서 뺴주고, 같은 공식을 이용하여, 너비 3(6-2-1=3)를 구합니다. 그리고 사각형 넓이를 구해주는데 넓이는 6 x 3 = 18 이므로 answer를 갱신해줍니다.

st = [1, 2], answer = 18

역시 위치 2의 울타리 톺이 5(fences[2]=5)는 현재 높이 3보다 크기 때문에 스택에서 빼주고 같은 공식을 이용하여 너비 4(6-1-1=4)를 구합니다. 그리고 사각형 넓이 5 X 4 = 20 을 구합니다. 이 때, answer를 갱신해부니다.

st = [1], answer = 20

그 후, 1의 위치 1보다는 현재 높이 3이 크기 때문에 반복문을 종료하고, 스택에 index를 넣어줍니다.

st = [1, 6] answer = 20

반복문을 다 돌았으면 끝이냐, 물론 아닙니다. 현재 예제는 상관이 없지만, 현재 남아 있는 위치의 높이가 엄청나게 클 경우, 이 문제는 답이 틀릴 수 있기 떄문에, 이것들을 계산해주어야 합니다. 따라서 스택이 모두 빌 때까지, (N - 위치) x 위치의 높이를 계산해주어 사각형을 갱신해주어야 합니다. 그런데 이는, 알고리즘 들어가기 전에 fences에 0을 넣어주고 index를 0~N까지 순회하는 것으로 분리해서 처리할 필요 없이 코드를 처리해줄 수 있습니다. 다음 절 코드를 살펴보시면 이해할 수 있을 겁니다. 이 문제를 푸는 알고리즘은 다음과 같습니다.

1. 스택을 생성합니다
2. 울타리를 저장하는 fences의 0을 추가합니다. //동작의 일관성 제공
3. 0부터 N까지 즉 N+1번을 다음과 같이 순회합니다. //1번에서 추가한 0 때문에
   1. 스택이 비지 않고, 현재 스택에 가장 나중에 저장된 위치의 울타리 높이가 현재 울타리 높이 이상일때까지 다음을 반복합니다.
      1. 스택에 가장 나중에 저장된 위치를 가져옵니다.
      2. 너비는 스택이 비었을 땐, 현재 위치 i 아니라면, (i - 다은 나중 저장된 위치 -1) 입니다.
      3. 사각형의 넓이를 구하고, 최대치를 갱신합니다.
   2. 스택의 현재 위치를 넣습니다.

이 알고리즘의 시간의 복잡도는 O(N)입니다.

코드

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int solution(int N, vector<int> fences) {
    int answer = 0;
    //1. 스택 생성
    stack<int> st;
    //2. 동작 일관성을 위한 0 추가
    fences.push_back(0);
    //3. 0~N까지 다음을 반복
	for (int i = 0; i <= N; i++) {
        //스택이 비지 않고, 스택에 저장된 위치의 높이가 현재 높이보다 크다면, 반복
		while (!st.empty() && fences[st.top()] >= fences[i]) {
			auto pos = st.top();
			st.pop();
            //스택이 비었다면, i가 너비가 된다. 아니라면 i - 나중에 저장된 위치 -1
			int width = st.empty() ? i : (i - st.top() - 1);
			int square = width * fences[pos];
			answer = max(answer, square);
		}

		st.push(i);
	}

	return answer;
}

int main() {
	int C, N;
	cin >> C;

	for (int i = 0; i < C; i++) {
		cin >> N;
		vector<int> fences{ vector<int>(N, -1) };
		for (int i = 0; i < N; i++) {
			int num;
			cin >> num;
			fences[i] = num;
		}

		cout << solution(N, fences) << endl;
	}
	return 0;
}