[백준]2493.탑

문제설명

간단히 말하여 높이가 서로 다른 탑들이 주어졌을 때 탑 꼭대기 왼쪽방향에 해당 탑보다 큰 탑이 존재하면 해당 탑의 번호를(1부터 시작), 없으면 0을 출력한다.

문제를 이해하는데 있어 중요한 내용은

1.탑의 높이는 중복없음.

2.탑의 수는 50만이하 탑의 높이는 1억이하이다.

접근

아이디어가 곧바로 떠오르지 않아 예제를 통해 어떻게 접근할 지 결정하고자 했다.

예제 : 6 9 5 7 4

1.6기준 왼쪽에 탑이 없으므로 0출력

2.9기준 6은 낮으므로 또 0 출력

3.5기준 9가 높으므로 9의 번호인 2번 출력

4.7기준 왼쪽에 있는 5는 낮으나, 9가 만나 2추력

5.4기준 7을 만나 그 번호인 4출력.

위를 봤을 때 관심의 대상이 되는 빌딩기준 왼쪽에 더 큰 빌딩이 있는지 봐야하는데 단계가 지나갈 때 정보를 재사용하고 있다. 정보는 빌딩의 번호와 높이라 할 수있다. 따라서 이를 어떻게 효과적으로 저장하여 이용할 수 있을지 고민하는 것이 이 문제의 핵심이라 볼 수 있다.

방법1. count 정렬처럼 인덱스에 대한 크기를 기억해두자.

해당 정보를 리스트로 선언하여 인덱스는 빌딩의 크기, value는 빌딩의 번호로 정하여 관심의 대상보다 큰 값이 있었는지 확인해보면 되지 않을까? 초기값은 -1로 이는 미방문된 빌딩이라 본다.

문제

관심의 대상의 빌딩의 높이가 H라 한다면 H보다 더 큰 빌딩을 찾기 위해선 인덱스를 일일이 탐색해야 하며 결국 탐색시 O(N)이 소요된다. 빌딩의 수가 N개이므로 O(N^2). 입력이 50만이므로 시간이 초과된다.

방법2.맥스힙 또는 이진탐색트리를 이용해보자.

관심의 대상이 되는 빌딩기준 큰 값을 구해야 하니까 지나왔던 길은 맥스힙으로 저장해두면 탐색이 빠르지 않을까? 결국 '탐색'해야하는 문제이고, 정렬되어 있는 상태로 저장한다면 탐색이 매우 빨라질테니까. 빌디의 번호와 높이를 동시에 고려해야하므로 맥스힙의 원소는 (n,h)를 원소로 가진다. 그리고 h를 기준으로 저장한다. 값을 탐색할 때 루트노드가 관심의 대상인 빌딩보다 높다면 n을 기준으로하는 맥스힙에 저장해야한다. 그 이유는 관심대상의 빌딩에서 번호가 가장 빠른 빌딩이 있어야하기 때문. 그리고 루트노드보다 작아도 관심빌딩보다 높으면 되기 때문에 재귀적인 탐색을 통해 그 값을 찾아 n을 기준으로하는 힙에 넣는다. 그렇게 다 넣은 뒤, 루트노드의 n값을 출력해주면 그것이 답. 시간복잡도를 고려해보면 (n,h)를 넣는 힙에 총 n번을 넣어야 하므로 nlogn, n번째에서 값을 탐색하여 n을 넣는 힙에 넣어야 하므로 nlogn(재귀탐색시간)+nlogn(n을 넣는 힙에 넣는 시간)으로 3nlogn -> O(nlogn)으로 문제 해결 가능!

문제

시간복잡도 계산이 잘못됬다.

뒷부분의 nlogn+nlogn의 시간은 매 스텝마다 고려해주어야 하므로 2nlogn*n = 2n^2logn -> O(n^2logn)이 된다. 잘못 계산해서 이 방법으로 풀었다가 시간초과가 났다.

힙에 넣을 때 하나는 (n,h)로 튜플 하나는 n으로 원소라서 두개의 힙을 만들지 하나의 힙으로 만드는 것을 통합하여 만들어보려다가 구현하는데 너무나 많은 시간을 소요하였다. 결국 두 개 분리하여 작성. 다형성에 대해 깊이 생각해보자.

방법3. 스택을 이용하자

구글링해서 사람들이 적용한 방법을 참조한 것으로, 일반적으로 스택의 성질을 설명하자면 이렇다. 스택은 지나쳤던 정보를 보는데 있어 좋은 자료구조(이 때문에 함수, 인터럽트 시 pc저장 등 이를 이용)이다. 위 문제를 이와 같이 접근할 수 있다. 5기준 왼쪽에 5보다 큰 빌딩은 6와 9가 있지만 9가 더 크기 때문에 6는 더이상 닿을 일이 없다. 따라서 고려하는 요소로 제외.(여기서 왼쪽을 본다는 건 지나쳤던 빌딩을 본다는 것과 같은 말.) 그리고 7기준으로 왼쪽에 6,9,5가 있는데 5는 지나치고 9가 높다. 그런데 이후 빌딩을 생각해보면 5보다 7이 더 높기 때문에 방금 전에 봤던 6와 9 사례에서 처럼 5는 더이상 닿을 일이 없다. 6과 5는 더이상 고려의 대상이 아니라는 말과 같다.(높은 빌딩이 나오는 가장 큰 번호를 구해야 하므로) 그래서 X번째 빌딩을 고려할 시에 왼쪽의 빌딩보다 X번째 빌딩이 더 크다면 X-1번째 빌딩을 pop해준다. 이 작업을 X-2, X-3....해서 X번째보다 큰 빌딩이 나올 때까지 pop해준다. 이 작업을 통해! X번째보다 더 큰 빌딩이 나왔을 때 X-1번째 빌딩(X번째보다 더 작은 빌딩들)을 중복해서 고려하는 경우를 제외할 수 있다. 예를 들어 5,4,3,2,8,9가 주어졌을 때 8기준으로 [5,4,3,2]가 다 작으므로 이 값은 모두 pop하여 8,9만을 고려한다. 9 기준으로 8이 작으므로 9만이 남겨진다. 이때 [5,4,3,2]를 지우지 않았다면 9도 [5,4,3,2]를 고려했을 것이다.

이 방법도 최악의 경우는 O(n^2)이다. 1,2,3,4,5,6,7,8,9,10.....으로 주어졌을 때 말이다. 그런데 무작위로 주어진다면 말은 달라질 것이다. 구체적으로 구하는 건 좀 까다로워서 random 함수를 이용하여 몬테카를로 실험처럼 민,맥스,평균을 구해보았다.(출력은 제외) n은 50만, 빌딩은 1~50만의 수로 제한했다. 30회 실행시 그때 결과는

최소,최대,평균 : 0.28 0.70 0.42이다.

구현

방법2 구현

class oneHeap:
    def __init__(self,n):
        self.n = 0
        self.heap = [0 for _ in range(n+1)]

    def insertNode(self, node):
        self.n += 1
        curIdx = self.n
        parentIdx = curIdx // 2
        item = node

        while self.heap[parentIdx] < item and curIdx != 1:
            self.heap[curIdx] = self.heap[parentIdx]
            curIdx = parentIdx
            parentIdx = curIdx // 2
        self.heap[curIdx] = node

    def pop(self):
        return self.heap[1]


class tupleHeap:
    def __init__(self,n):
        self.n = 0
        self.heap = [(0,0) for _ in range(n+1)]

    def insertNode(self,node):
        self.n += 1
        curIdx = self.n
        parentIdx = curIdx//2
        item = node[0]

        while self.heap[parentIdx][0]<item and curIdx != 1:
            self.heap[curIdx] = self.heap[parentIdx]
            curIdx = parentIdx
            parentIdx = curIdx//2

        self.heap[curIdx] = node

    def returnBuldingNums(self, val):  # heap에서 val 초과인 building 값들을 모두 받기 이는 tuple함수만 이용가능
        buldings = oneHeap(self.n)

        def _recursiveValue(i, target):  # 재귀적으로 탐색하여 val보다 큰 값을 찾아 받음. 초기 루트부터 탐색. node = 1
            nonlocal buldings
            if i > self.n:
                return

            item = self.heap[i][0]
            if item > target:
                buldings.insertNode(self.heap[i][1])  # node[1]은 빌딩번호.
                _recursiveValue(i * 2, target)
                _recursiveValue(i * 2 + 1, target)
            else:
                return

        _recursiveValue(1, val)

        return buldings

n = int(input())
inputBuildings = list(map(int,input().split()))
passBuldings = tupleHeap(n)

for i in range(1,n+1):
    passBuldings.insertNode((inputBuildings[i-1],i))
    print(passBuldings.returnBuldingNums(inputBuildings[i-1]).pop(),end = " ")

방법3 구현

n = int(input())
buildings = [0]+list(map(int,input().split()))
stack = []

for i in range(1,n+1):
    h = buildings[i]
    if stack:
        empty = False
    else:
        stack.append((i,h))
        print(0, end=" ")
        continue

    while stack[-1][1] < h :
        if stack:
            stack.pop()
            if not stack:
                empty = True
                break

    if empty :
        print(0, end=" ")
    else:
        print(stack[-1][0], end=" ")
    stack.append((i,h))