[BOJ][6198번] 옥상정원 꾸미기

안녕하세요 Dibrary입니다.

이번 문제는 '스택'을 활용한 문제입니다. 스택을 배우긴 했는데, 어떻게 써야할 지 모르는 사람이었다면 이 문제를 풀지 못했을 겁니다. (저처럼요...)

 

6198번: 옥상 정원 꾸미기

---

먼저 예시로 나온 문제를 보면 10, 3, 7, 4, 12, 2  에서, 10을 기준으로는 3개, 7은 1개, 12는 1개 총 5개를 볼 수 있죠.

그래서 전 처음에 이런 방식으로 도전했었습니다.

모든 타워 정보를 넣은 후에, for문을 2겹으로 돌면서 기준 타워보다 그 다음에 큰 타워가 나올 때 까지의 갯수를 합하는 방식이죠.

for문이 2겹이라서 O(n^2)이 걸린다는게 좀 마음에 걸렸었지만요...

아니나 다를까, 제출 결과는 시간초과였습니다.

 

---

이 문제의 풀이는 인터넷을 검색하시면 곧바로 아시겠지만, '스택'을 활용한 풀이가 가장 많이 나옵니다.

코드는 아래와 같습니다.

굉장히 심플하죠? 저도 이 코드를 보고 당황했었습니다. 그리고 곧바로 이해가 안 되기도 해서 더 당황했죠.

위 코드대로 예제에서 주어진 값을 확인해보겠습니다.

 10, 3, 7, 4, 12, 2 이 주어지는데, 10을 기준으로 먼저 시작하면 stack이 비어있으므로 append 됩니다. 이때 stack의 길이는 1이므로 res는 0 인 상태로 남아있죠.

그 다음에 3의 경우에는 while 조건문에 해당하지 않으므로 stack에 추가 됩니다. res는 2-1이므로 1이 더해집니다.

7은 while조건문에 해당하므로 stack 에 들어있던 3을 빼내고 (마지막으로 들어간게 가장 먼저 나오는 스택의 특성.) 그 자리에 7을 넣습니다. res는 2-1이므로 1이죠.

4는 조건문에 해당이 없으므로 stack에 그대로 더해지고, res는 3-1 = 2가 더해집니다.

12의 경우에는 while 에 stack에 들어있는 모든 값이 해당됩니다. 따라서 stack안에 있는 모든 요소가 pop되고, 12 하나만 들어가게 됩니다. res는 1-1이므로 0이 더해집니다.

2는 앞서 구했던 10 다음에 3을 넣은 경우와 같으므로 res는 1입니다.

따라서, res는 총 1+1+2+1 = 5 가 됩니다.

 

개인적으로 저는 이 코드에서 len(stack)-1 부분에서 뇌리를 스쳐지나간 것이 있어서 굉장히 놀랐습니다.

만일 stack에 10, 7, 4가 들어있다면 res는 2가 나오는데, 이는 10이 4를 볼 수 있는 것 +1, 7이 4를 볼 수 있는 것 +1 이렇게 되는 것이니까요.