프로그래머스 - 탑
https://programmers.co.kr/learn/courses/30/lessons/42588
문제 내용.
N개의 탑을 세워 꼭대기에 신호를 송/수신 하는 장치를 설치했다.
신호는 신호를 보낸 탑보다 높아야 수신할 수 있다.
(높이 3의 탑은 높이 5의 탑의 신호를 못받는다)
신호는 왼쪽으로 발사한다는 사실을 기반으로,
각각의 탑이 쏜 신호는 어느 탑이 받았는지에 대한
정보가 담긴 배열을 작성하자.
제한 사항.
- 2 <= 탑의 개수 <= 100
- 1 <= 탑의 높이 <= 100.
- 신호를 받지 못했으면 0을 기록하자.
1. 반복문 - O(N^2)
문제에서 시키는 대로 레이저를 직접 쏴 보자.
하나의 탑, i에서 왼쪽으로 신호를 쏘는 행동을
i-1 , i-2 , … , 2, 1 번 탑 순으로
i 번 탑이 현재 탐색하는 탑 보다 높이가 낮은지 확인하는 식으로 구현하자.
만약 j 번 탑이 i 번 탑보다 높이가 높다면,
i 번 탑은 j 에 닿는다는 답을 기록하고,
i-1 번째 탑에 대해서도 똑같은 동작을 반복하자.
이 동작을 n 개의 탑에 대해서 어떻게 하는지 살펴보자.
n 번째 탑에서 1 번 탑까지 탐색하며,
탑을 찾으면 값을 입력하고 넘어간다.
n-1 번째 탑에서 1 번 탑까지 탐색하며,
탑을 찾으면 값을 입력하고 넘어간다.
… 1씩 감소시키며 반복 …
2 번째 탑에서 1번 탑까지 탐색하며,
탑을 찾으면 값을 입력하고 넘어간다.
1번 탑은 맨 앞이므로 어느 탑에도 맞지 않는다.
이런 식으로 직접 시뮬레이션을 하면 답을 찾을 수 있다.
이중 반복문으로 간단하게 구현해보자.
solution_loop.cpp
#include <vector>
using namespace std;
vector<int> solution(vector<int> heights) {
int size = heights.size();
vector<int> answer(heights.size(), 0);
for (int i=size-1; i>=0; --i)
{
for (int j=i-1; j>=0; --j)
{
if (heights[i] < heights[j])
{
answer[i] = j+1;
break;
}
}
}
return answer;
}
이렇게 하면 얼마만큼의 연산이 필요할까?
운이 매우 좋아서 쏘는 즉시 바로 왼편의 타워에 모두 맞는다면,
실행 시간은 O(N)이 될 것이다.
(1 + 1 + 1 + ... + 1 + 1 + 1)
하지만 운이 매우 안좋아서 쏘는 것 마다 맞지 않는다면,
실행 시간은 O(N^2)이 될 것이다.
(n-1 + n-2 + n-3 + ... + 3 + 2 + 1)
이 문제의 통과만을 생각한다면, N의 크기가 작은 문제인 만큼 O(N^2) 알고리즘을 사용해도 통과하는 데에는 아무런 지장이 없을 것이다. 하지만 다른 곳에서 동일한 문제가 나왔다면, 이 코드로 통과하리란 보장은 할 수 없다.
아마도 탑의 개수는 1만개 이상일 것이며, 10만개가 될 수도 있다.
2. 스택 이용하기 - O(N)
그렇다면 어떻게 해야 효율적으로 답을 구할 수 있을까?
아래의 형태를 보면서 생각해보자.
6 1 2 3 4 5
반복문으로 풀었던 동작을 다시 한번 되새겨보자.
5는 4,3,2,1에는 맞지 않으나, 6에는 맞는다.
4는 3,2,1에는 맞지 않으나, 6에는 맞는다.
3은 2,1에는 맞지 않으나, 6에는 맞는다.
가만 보니, 5와 4는 3,2,1을 검사한다. 그리고 셋 다 맞지 않는다.
그리고 둘 다 6에는 맞는다.
생각해보니 5보다 작거나 같은 타워들이 쏘고 있는 레이저가 맞지 않는다는 것은,
뒤에 있는 더 높거나 같은 탑인 5가 쏘는 레이저에도 맞지 않는다는 것을 의미한다.
높이 4짜리가 쏘는 타워에는 맞지 않는데, 높이 5짜리가 쏘는 타워에 맞는 타워는 없다.
따라서, 높이를 확인한 탑이 4 짜리가 쏘는 레이저가 맞지 않는 탑이라면,
높이 5짜리가 맞는지 안맞는지는 굳이 확인을 할 필요가 없다는 소리다.
그렇다면 현재까지 쏜 레이저 중에서, 높이가 낮은 레이저부터 확인을 하고, 맞으면 맞을수록 계속 충돌확인을 하면 계산량을 줄일 수 있을 것이다.
레이저가 맞지 않으면 맞지 않을 수록 탑의 크기는 점점 낮아거나 유지 될 것이다. 크기가 작은 탑의 레이저부터 확인하고, 맞으면 맞을 수록 큰 탑의 레이저를 확인하면 된다. 가장 나중에 들어온 작은 탑의 레이저부터 확인하고, 맞다면 가장 먼저 빠져나가야 한다.
즉, 후입선출의 구조로 동작을 수행해야 한다.
그러므로 이번 문제에서는 스택을 쓰는 것이 좋을 것이다.
그러면 스택을 어떻게 쓸 지에 대해 알아보자.
먼저, 각각의 탑을 맨 뒤에서부터 순회하자.
스택의 top에 기록된 탑의 높이, 즉 가장 낮은 높이의 탑을 확인한다. 만약 현재 확인하는 탑의 높이가 스택의 top의 높이보다 높다면, 스택의 top이 맞은 탑의 번호를 현재 확인중인 탑의 번호로 기록한다. 해당 레이저가 만난 가장 처음으로 높은 탑이 현재 순회하는 탑이기 때문이다.
만약 현재 확인하는 탑의 높이가 스택의 top의 높이보다 낮다면, 현재 확인하는 탑이 가장 낮은 높이의 탑이 된다. 따라서 스택에 push를 해 준다.
이 과정을 모든 탑에 대해서 수행할 때 까지 반복한다. 최종적으로 스택에 현재 탑의 정보를 push 하고 다음 탑으로 순회를 계속 한다.
한번 위의 예시를 통해 확인해보자.
6 1 2 3 4 5
그리고 현재의 정답은 [0,0,0,0,0,0] 이다.
탑 5부터 시작하자.
맨 처음으로 확인한 탑이므로 stack에 push하자.
그러면 현재 스택에는 [5] 하나 뿐이다.
탑 4로 넘어가자. 4는 5보다 작다. stack에 push 하자.
그러면 현재 스택에는 [5,4] 가 들어있다.
탑 3으로 넘어가자. 3은 4보다 작다. stack에 push 하자.
그러면 현재 스택에는 [5,4,3] 이 들어있다.
탑 2로 넘어가자. 2는 3보다 작다. stack에 push 하자.
그러면 현재 스택에는 [5,4,3,2] 가 들어있다.
탑 1로 넘어가자. 1은 2보다 작다. stack에 push 하자.
그러면 현재 스택에는 [5,4,3,2,1] 이 들어있다.
탑 6으로 넘어가자. 6은 1보다 크다.
그러면 탑 1은 탑 6에 맞았다.
탑 6은 첫 번째 탑이다.
따라서 정답을 [0,1,0,0,0,0]으로 수정하고, pop 하자.
탑 6은 탑 2보다 크다.
그러면 탑 2는 탑 6에 맞았다.
탑 6은 첫 번째 탑이다.
따라서 정답을 [0,1,1,0,0,0]으로 수정하고, pop 하자.
…
탑 6은 탑 5보다 크다.
그러면 탑 5는 탑 6에 맞았다.
탑 6은 첫 번째 탑이다.
따라서 정답을 [0,1,1,1,1,1]로 수정하고 pop 하자.
그러면 스택에는 더 이상 남은 탑이 없다. 계속 진행하자.
그러면 탑 6은 맨 앞에 있는 탑이므로, 여기서 끝난다.
이 과정을 코드로 작성해보자.
solution_stack.cpp
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> heights) {
int size = heights.size();
vector<int> ans(heights.size(), 0);
stack<int> tops;
stack<int> positions;
for (int i=size-1; i>=0; --i)
{
int h = heights[i];
while(!tops.empty())
{
if (h <= tops.top()) break;
ans[positions.top()] = i+1;
tops.pop(); positions.pop();
}
tops.push(h); positions.push(i);
}
return ans;
}
이 코드에서는 stack을 2개 동시에 써서 위치와 탑의 높이를 따로 저장했지만, pair를 이용하여 하나의 스택에 모두 담을 수도 있다.
코드는 순회에 비해 좀 길어질 수 있다.
하지만 수행 시간은 순회에 비해 짧아질 것이다.
코드의 길이가 수행시간의 길이를 결정하지 않는다는 사실을 기억하자.
Comments