프로그래머스 - 탑

So,Soon·2020년 5월 8일
0

https://programmers.co.kr/learn/courses/30/lessons/42588

접근

결국 각 탑 마다 왼쪽에서 제일 가까운 나보다 높은 탑의 위치를 가지고 있으면 되기 때문에,

이를 저장하는 배열을 선언해서 풀었습니다.

카테고리가 스택인걸로 보아, 순회하면 O(N^2)이기 때문에 스택을 이용해서 최적화 하라는것 같은데,

제 방법대로 해도 O(N^2)은 피할수 있을것 같아 그냥 구현해 보았습니다.

구현

간단합니다. 내가 전송할 탑의 위치를 저장하는 배열을 answer라고 하고,

처음엔 이를 모두 0으로 초기화 합니다. 0은 전송할 수 없음을 나타냅니다.

맨 왼쪽 탑은 절대로 전송할 수 없기에 , 왼쪽에서 1번째 탑부터 조사합니다.

다음과 같은 로직입니다.

  1. 만약 현재보다 하나 왼쪽 탑의 높이가 나보다 높다면 그 탑으로 전송
  2. 그렇지 않다면 그 탑의 전송 위치의 높이 조사
  3. 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;
}
profile
iOS Software Engineer, Audio Software Engineer, SKKU Computer Science, Business Administration

0개의 댓글