소스코드
k = int(input())
ocs = list(map(int,input().split()))
answer = [-1] * k
stack = []
for i in range (k):
while stack and ocs[i] > ocs[stack[-1]]:
answer[stack[-1]] = ocs[i]
stack.pop()
stack.append(i)
print(*answer)
알고리즘
자기보다 큰 수를 찾지 못하는 경우는 -1을 갖게 되므로 초기 세팅을 -1 * k로 해준다.
for문을 돌며 자기보다 큰 수를 발견하면 스택에 있는 인덱스를 answer[인덱스]에 그 숫자를 넣어준다.
3 5 2 7 이 입력 되었다고 생각을 해보자
0 1 2 3
1. 3을 비교하는데 3의 인덱스인 0을 스택에 넣는다.
stack = [0], answer = [-1,-1,-1,-1]
2. 5를 비교할 차례이다.
ocs[1] -> 5 > ocs[(stack[-1] -> 0)] -> 3 성립하게 된다. 그러면 while문 안으로 들어가보자
answer[stack[-1] -> 0 ] = ocs[1] 즉, answer[0] = 5가 된다.
stack = [1], answer = [5,-1,-1,-1]
3. 2를 비교해봅시다.
ocs[2] < ocs[1] 이므로 stack에 넣기만 하고 pass
stack = [1,2], answer = [5,-1,-1,-1]
4. 7 마지막
ocs[3]과 stack의 마지막 값인 2을 가져와 ocs[2]를 비교하게 된다. while문으로 간다.
answer[2] = ocs[3] = 7이 된다.
stack = [1], answer = [5,-1,7-1]
answer[1] = ocs[3] = 7
stack = [], answer = [5,7,7,-1]
종료
stack에 인덱스를 넣어서 문제를 풀어야 했다
'Coding test' 카테고리의 다른 글
[백준/2775/파이썬] 부녀회장이 될테야 (0) | 2023.11.30 |
---|---|
[백준/1931/파이썬] 회의실 - Greedy (2) | 2023.11.27 |
[프로그래머스/주차 요금 계산/파이썬] (2) | 2023.11.23 |
[프로그래머스/k진수에서 소수 개수 구하기/파이썬] (1) | 2023.11.22 |
[1912/백준/파이썬] 연속합 - DP (0) | 2023.11.21 |