[python] 백준 - 2493. 탑

🤔문제 해결

• G4 | 자료구조, 스택

문제를 푼 뒤 문제 유형을 봤는데 스택이라고 되어있었다.

하지만 내 풀이는 스택을 사용하지 않았다. 그런데 다른 사람보다 효율이 좋게 나왔다. 메모리는 평균인듯.

 

풀이 방법

1번탑부터 마지막탑 순으로 탐색했다.

• 현재탑과 이전탑과 같을 때
  • 현재탑의 레이저 신호를 수신하는 탑은 이전탑의 레이저 신호를 수신하는 탑과 같다.
• 현재탑이 이전탑보다 낮을 때
  • 현재탑의 레이저 신호를 수신하는 탑은 이전탑이다.
• 현재탑이 이전탑보다 높을 때 🐱‍🐉
  • 이전탑의 레이저 신호를 수신한 탑으로 건너 뛴다.
  • 그 탑을 위의 3가지 방법으로 체크한다.
  • 아직 현재탑이 높은 상태라면 또 그 탑의 레이저 신호를 수신한 탑으로 건너 뛴다.

이렇게 3가지로 분리했다.

💻소스 코드

 if __name__ == '__main__':
    N = int(input())
    TOP = list(map(int, input().split()))
    answer = [0] * N

    for i in range(1, N):
        j = i - 1
        while j >= 0:
            if TOP[i] == TOP[j]:  # 이전과 같을 때
                answer[i] = answer[j]
                break
            elif TOP[i] > TOP[j]:  # 이전보다 높을 때
                j = answer[j] - 1
            else:  # 이전보다 낮을 때
                answer[i] = j + 1
                break

    print(' '.join(list(map(str, answer))))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/2493

2493번: 탑