[baekjoon] 2493. 탑

✅ 문제

 

---

✅ 풀이

solution 1)  힙 이용 - 시간 초과

💡 Point
1. 인덱스와 함께 리스트를 힙 정렬함(최소 순으로 정렬)
2. 조건 확인 후
  1) 현재 탑보다 숫자가 커야 함(숫자가 작으면 송신 불가)
  2) 최초 리스트 기준 왼쪽으로 순회한다는 말 = 현재 탑보다 인덱스가 작아야 함
3. 결과 리스트 0으로 세팅해 두고, 현재 탑의 자리에 발사한 레이저를 송신한 탑의 인덱스+1 값을 넣어줌

 

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

# 송신탑 자리번호를 매겨 최소힙으로 만들어 정렬
top_list = [(num, i) for i, num in enumerate(top)]
heapq.heapify(top_list)
result = [0] * n

while top_list:
    current_top = heapq.heappop(top_list)
    index = current_top[1]
    for num, i in top_list:
        if current_top[0] < num and index > i:
            result[index] = i+1
print(result)

 

내가 생각하는 실패 이유는 쓸데없이 힙정렬한 후 이중 루프를 돌면서 시간 복잡도가 O(N^2)가 됐다는 것이다.

진행방향이 오른쪽에서 왼쪽이니까 굳이 힙정렬하지 말고, 역순으로 for문 돌리면 되지 않을까 싶다.

단일 루프로 시간복잡도를 O(n)으로 감소시킬 필요가 있음

 

---

 

solution 2) 스택 이용 -  통과!

💡 Point
1. 탑 리스트를 오른쪽에서부터 순회(for문 역순으로 돌림) 
2. 조건 확인
  1) 현재 탑이 오른쪽에 있는 탑(스택에 담겨있음) 보다 큰 경우 송신이 가능
  2) 스택에서 제거 후 그 탑의 result 자리에 현재 탑의 index+1을 해준다.
3. 스택에 현재 탑의 번호를 담아 왼쪽 탑으로 넘어감

n = int(input())
top = list(map(int, input().split()))
top_list = [(num, i) for i, num in enumerate(top)]
result = [0] * n
stack = []

# 왼쪽 방향으로 순회(역순으로 for문)
for num, i in top_list[::-1]:
    # 현재 확인할 탑
    current_top = top_list[i]
    index = current_top[1]
    
    # 스택에 담긴 값보다 크면 현재 탑에서 이전 탑의 신호를 수신하니까
    # 이전 탑의 result에 현재 탑의 index+1이 담겨야 함(index는 0부터 시작이므로)
    while stack and stack[-1][0] < current_top[0]:
        prev = stack.pop()
        result[prev[1]] = index + 1
    stack.append(current_top)
    
print(*result)