[python] BOJ 2493 탑
시간초과가 떴나요? 그렇다면 스택을 제대로 구현하지 못한것일 가능성이 큽니다.
다음과 같이 탑이 비치되어 있다면 빨간색 점으로 표시한 탑의 입장에서는 초록색 별로 표시한 탑의 존재는 필요가 없다.
⇒ 스택에 넣을때 초록색 별과 빨간색 점 사이의 탑에 의해서 초록색 별 탑이 지워졌을 것이기 때문
최종적으로 스택 안에 탑을 넣었을때 정리되는 모습은 탑들이 내림차순으로 정렬되게 된다. 이 과정이 제대로 이루어 지지 않았다면 확인하지 않아도 되는 탑들을 계속 확인하기 때문에 시간초과가 날 수 있다.
[코드 설명]
candidate_indices 를 stack으로 사용
-
candidate_indices 가 비어있다면?
지금 시점에서는 현재 인덱스의 탑이 가장 높은 탑이다 = 현재 인덱스의 탑에서 레이저를 쐈을때 맞을 수 있는 탑이 없다 → 이때는 0을 출력해야 한다.
-
candidate_indices 가 비어있지 않다면 지금 시점에서 현재의 인덱스의 탑이 가장 높은 탑인지 확인해야 한다 = 현재 인덱스 탑에서 레이저를 쐈을때 맞는 탑이 존재할 수 있다. ⇒ 높이 비교를 통해candidate_indices에 들어있는 탑의 높이가 현재 인덱스의 탑보다 클때와 작을때의 처리를 나눈다.
-
candidate_indices[-1] 의 인덱스를 가진 탑의 높이가 현재 인덱스의 탑보다 작을때
- 위의 설명처럼 내림차순 정렬을 위해서 현재 인덱스의 탑보다 높이가 높은 탑의 인덱스를 만날때까지 candidate_indices를 팝해준다.(while 사용)
-
candidate_indices[-1] 의 탑의 높이가 현재 인덱스의 탑보다 높을때
- 이때는 candidate_indices에 현재 인덱스를 추가하는 작업이 이루어 져야 한다.
- 2-a. 경우에도 현재 인덱스보다 크지 않은 탑을 만날 때까지 제거만 하였으므로 2-b.의 전제와 같아진다. 따라서 2-b.의 경우는 별도의 조건 설정 없이 candidate_indices에 index를 추가해준다.
-
출력을 위해 탑의 갯수만큼 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=" ")
Author And Source
이 문제에 관하여([python] BOJ 2493 탑), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jinlee/python-BOJ-2493-탑저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)