[ BAEKJOON ] 탑 / 2493 / Python

 

 

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

 

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

 

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

 

예제 입력 1

5
6 9 5 7 4

예제 출력 1

0 0 2 2 4

 

---

 

나의 풀이

처음에 문제를 보자마자 되게 단순한 로직으로 풀리겠다고 생각을 했다. 문제가 단순하여 배열을 거꾸로 돌려서 해당 인덱스보다 앞의 인덱스를 탐색하며 자신보다 큰 인덱스 번호 + 1 을 출력하면 되겠다고 생각했다.

하지만, N값이 500,000으로 그렇게 되면 for문을 두 번 도는 것과 같아 시간 복잡도가 O(n^2) 으로 시간 초과가 나게 된다.

최적화하여 풀기 위해 스택을 도입하여 풀어야 하는데, 시간초과를 해결할 수 없어서 민재님의 도움을 받아 풀었다!

 

로직

stack에는 가장 큰 탑들의 크기부터 작은 순으로 배열이 되도록 쌓을 것이다.

그러면 현재 나의 탑 크기와 비교하여 나보다 높은 탑을 바로 찾을 수 있을 것이다.

 

예를 들어, 6 9 5 7 4 라는 탑의 크기가 주어질 때, 최종적으로 stack에는 9 7 이 들어있을 것이다.

천천히 단계를 수행하면서 접근해보자.

주어진 탑의 크기의 첫번째 인덱스부터 마지막 인덱스로 접근할 것이다.

 

[ 현재 탑 - 6 ]

현재 탑이 6이라고 할 때, STACK 이 비어있으므로 현재 내가 가장 높은 탑의 크기가 된다.

STACK	6
ANSWER	0

STACK에는 현재 시점에서 가장 큰 탑들이 순차적으로 들어갈 테니 현재 탑의 크기를 저장해준다. 현재보다 큰 탑이 왼쪽에 존재하지 않으니 답에는 당연히 0이 들어갈 것이다.

 

[ 현재 탑 - 9 ]

STACK의 마지막부터 조사하여 나보다 큰 탑이 존재하는지 확인해보자.

현재 STACK의 6은 현재 탑 크기 9보다 작으므로 6이라는 탑은 이후에 나오는 값들의 비교 대상이 될 수 없다.

STACK
ANSWER	0

6을 STACK에서 제거하고, 현재 탑 크기인 9를 STACK에 넣어준다.

STACK	6
ANSWER	0	0

이때 ANSWER에는 현재보다 큰 탑이 왼쪽에 존재하지 않으니 0이 들어갈 것이다.

 

[ 현재 탑 - 5 ]

현재의 5와 STACK에 저장되어 있는 가장 큰 탑 9와 비교한다. 9가 더 크기 때문에 답에는 9의 인덱스 값인 2가 들어가고, 현재의 탑 크기가 STACK에 저장된다.

STACK	9	5
ANSWER	0	0	2

 

[ 현재 탑 - 7 ]

현재 탑의 크기인 7과 마지막으로 큰 탑의 크기 5를 비교하였을 때, 현재 나의 탑이 더 크기 때문에 5는 더이상 비교 대상이 될 수 없다. 5를 STACK에서 제거해준다.

STACK	9
ANSWER	0	0	2

그다음 9와 비교하였을 때, 현재 나보다 큰 탑이 존재하기 때문에 ANSWER에는 9의 위치 값인 2가 들어간다.

STACK	9
ANSWER	0	0	2	2

추가로 현재 탑의 크기까지 STACK에 쌓아준다.

STACK	9	7
ANSWER	0	0	2	2

 

[ 현재 탑 - 4 ]

마지막 현재 탑의 크기인 4와 비교하였을 때, 7이 더 크기 때문에 ANSWER엔 7의 위치 값인 4가 들어가게 된다.

STACK	9	7
ANSWER	0	0	2	2	4

⇒ 결론적으로는 STACK에는 오른쪽으로 갈 수록 가장 큰 탑에서 작은 탑이 되는 수만 정렬이 된다고 생각하면 된다.

 

 

코드

위의 로직을 코드로 나타날 땐, STACK에 저장되는 값을 INDEX로 저장하여 ANSWER에 넣는 값과 탑의 크기 비교를 쉽게 한다.

n = int(input())
lst = list(map(int, input().split()))

stack = []
answer = []

for idx, value in enumerate(lst):
    if stack == []:
        stack.append(idx)
        answer.append(0)
    else:
        while stack:
            if lst[stack[-1]] > value:
                answer.append(stack[-1] + 1)
                stack.append(idx)
                break
            else:
                stack.pop()
        else:
            stack.append(idx)
            answer.append(0)

for ans in answer:
    print(ans, end=' ')

 

 

 

[ 나의 오답.. 친구들.. ]

n = int(input())
lst = list(map(int, input().split()))

beforeLength = 0
mxLength = 0
answer = list()

for i in range(n):
    if lst[i] > beforeLength:
        if lst[i] < mxLength:
            # 그 전 탐색
            for j in range(i - 1, -1, -1):
                if lst[i] < lst[j]:
                    answer.append(j + 1)
        else:
            answer.append(0)
    else:
        answer.append(i)
    
    beforeLength = lst[i]

    if mxLength < lst[i]:
        mxLength = lst[i]

for i in range(n):
    print(answer[i], end=' ')

→ 시간 초과!

n = int(input())
lst = list(map(int, input().split()))

stack = []
answer = []

for idx, value in enumerate(lst):
    if stack == []:
        stack.append(idx)
        answer.append(0)
    else:
        for i in range(-1, -len(stack)-1, -1):
            if lst[stack[i]] > value:
                answer.append(stack[i] + 1)
                stack.append(idx)
                break
        else:
            answer.append(0)
            stack = [idx]

for ans in answer:
    print(ans, end=' ')

→ 시간 초과!