[백준] 2493 탑

시간초과가 떴나요? 그렇다면 스택을 제대로 구현하지 못한것일 가능성이 큽니다.

다음과 같이 탑이 비치되어 있다면 빨간색 점으로 표시한 탑의 입장에서는 초록색 별로 표시한 탑의 존재는 필요가 없다.

⇒ 스택에 넣을때 초록색 별과 빨간색 점 사이의 탑에 의해서 초록색 별 탑이 지워졌을 것이기 때문

최종적으로 스택 안에 탑을 넣었을때 정리되는 모습은 탑들이 내림차순으로 정렬되게 된다. 이 과정이 제대로 이루어 지지 않았다면 확인하지 않아도 되는 탑들을 계속 확인하기 때문에 시간초과가 날 수 있다.

[코드 설명]

candidate_indices 를 stack으로 사용

1. candidate_indices 가 비어있다면?

   지금 시점에서는 현재 인덱스의 탑이 가장 높은 탑이다 = 현재 인덱스의 탑에서 레이저를 쐈을때 맞을 수 있는 탑이 없다 → 이때는 0을 출력해야 한다.

2. candidate_indices 가 비어있지 않다면 지금 시점에서 현재의 인덱스의 탑이 가장 높은 탑인지 확인해야 한다 = 현재 인덱스 탑에서 레이저를 쐈을때 맞는 탑이 존재할 수 있다. ⇒ 높이 비교를 통해candidate_indices에 들어있는 탑의 높이가 현재 인덱스의 탑보다 클때와 작을때의 처리를 나눈다.

   1. candidate_indices[-1] 의 인덱스를 가진 탑의 높이가 현재 인덱스의 탑보다 작을때

      1. 위의 설명처럼 내림차순 정렬을 위해서 현재 인덱스의 탑보다 높이가 높은 탑의 인덱스를 만날때까지 candidate_indices를 팝해준다.(while 사용)

   2. candidate_indices[-1] 의 탑의 높이가 현재 인덱스의 탑보다 높을때

      1. 이때는 candidate_indices에 현재 인덱스를 추가하는 작업이 이루어 져야 한다.
      2. 2-a. 경우에도 현재 인덱스보다 크지 않은 탑을 만날 때까지 제거만 하였으므로 2-b.의 전제와 같아진다. 따라서 2-b.의 경우는 별도의 조건 설정 없이 candidate_indices에 index를 추가해준다.

   3. 출력을 위해 탑의 갯수만큼 answer 배열을 만들고 -1로 초기화 해준다(출력시에 일괄적으로 index에 1을 더해서 출력할 예정이기 때문에 0을 출력하기 위해서는 -1로 초기화 했다)

      [6, 9, 5, 7, 4]의 예시로 보면 다음과 같은 출력결과를 얻을 수 있다.

n = int(input())
towers = list(map(int, input().split()))
candidate_indices = []
answers = [-1] * n

for index, tower in enumerate(towers):
		
    while len(candidate_indices) > 0 and tower > towers[candidate_indices[-1]]:
        candidate_indices.pop()

    if len(candidate_indices) > 0:
        answers[index] = candidate_indices[-1]

    candidate_indices.append(index)

for answer in answers:
    print(answer + 1, end=" ")