https://programmers.co.kr/learn/courses/30/lessons/42588
접근
결국 각 탑 마다 왼쪽에서 제일 가까운 나보다 높은 탑의 위치를 가지고 있으면 되기 때문에,
이를 저장하는 배열을 선언해서 풀었습니다.
카테고리가 스택인걸로 보아, 순회하면 O(N^2)이기 때문에 스택을 이용해서 최적화 하라는것 같은데,
제 방법대로 해도 O(N^2)은 피할수 있을것 같아 그냥 구현해 보았습니다.
구현
간단합니다. 내가 전송할 탑의 위치를 저장하는 배열을 answer라고 하고,
처음엔 이를 모두 0으로 초기화 합니다. 0은 전송할 수 없음을 나타냅니다.
맨 왼쪽 탑은 절대로 전송할 수 없기에 , 왼쪽에서 1번째 탑부터 조사합니다.
다음과 같은 로직입니다.
- 만약 현재보다 하나 왼쪽 탑의 높이가 나보다 높다면 그 탑으로 전송
- 그렇지 않다면 그 탑의 전송 위치의 높이 조사
- 0(전송할수 없음)이면 현재 탑 또한 전송불가능
1,2를 반복한다면 마치 union find에서 find하는 과정처럼 진행이 됩니다.
즉 왼쪽의 전송위치를 살펴보는 것은 나보다 낮은 값보다는 높은 높이의 탑을 조사하는 것 입니다.
[1,2,3,4 ... , 9999] 인 경우에서는 배열을 1번씩 돌면서 모두 실패로 뜨기 때문에 O(N)일것이며,
[9999,9998, ... ,1] 같은 경우도 바로 왼쪽에다 전송하게 되므로 O(N)일 것 입니다.
익스트림 케이스를 생각해 본다해도
[100,1,2,3,4,5,6, ... 9999] 같은 경우나
[100,1,101,2,102,3 ...,9999] 과 같은 경우를 따져보아도
왼쪽을 모두 검사하는게 아니라 나보다 작거나 같은 높이보다 큰 값만 계속 찾기 때문에
O(N)을 달성 할 수 있습니다.
다음은 코드 전문입니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> heights) {
vector<int> answer;
for(int i = 0 ; i < heights.size(); i++){
answer.push_back(0);
}
for(int i = 1 ; i < heights.size(); i++){
int com = i;
while(true){
if (heights[com-1] > heights[i]) {
answer[i] = com;
break;
}else{
com = answer[com-1];
if (com == 0) {
break;
}
}
}
}
return answer;
}