나의 풀이
# N = int(input())
# nums = list(map(int, input().split()))
# stack = []
# def binary_search(array, target, start, end):
# while start <= end:
# mid = (start + end) // 2
# if array[mid] == target:
# return mid
# elif array[mid] > target:
# end = mid - 1
# elif array[mid] < target:
# start = mid + 1
# return None
#
# for i in range(N - 1):
# target = nums[i]
# stack.append(target)
# temp = sorted(nums[i:])
# idx = binary_search(temp, target, 0, len(temp) - 1)
# if idx == len(temp) - 1:
# print(-1, end=" ")
# else:
# print(temp[idx + 1], end=" ")
# print(-1, end=" ")
#- 이진 탐색 구현하고 여러가지 시도해봤지만 입출력 예제 테스트는 성공하고 제출은 시간초과로 실패했다.
- 스택만 가지고도 간단하게 풀 수 있는 문제였다.
다른 사람 풀이 & 느낀점
stack = []
result = [-1] * N
for i in range(N):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
print(*result)- 입력값 예)
N = 4
nums = [3, 5, 2, 7] - 스택을 만들어준다.
- 결과를 담을 리스트를 -1로 N만큼 채운다.
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)- 이게 키포인트다.
- 스택을 숫자가 아닌 인덱스를 담는 그릇으로 활용한다.
- 처음에는 스택에 아무것도 넣지 않은 상태이기 때문에 while 문을 패스하고 스택에 i(0)을 담아준다.
- 그러면 그 다음에는 스택이 비어있지 않게 되고, nums[stack[-1] = 0] < nums의 i(1)번 째 숫자 를 비교하여 i 번째 숫자가 오큰수인 동안
- result 리스트에 스택의 인덱스에 해당하는 자리에 오큰수를 넣어준다.
- 그렇다면 result[stack.pop() == 0] = (nums[1] == 5) 가 될 것이다. 조건에 맞지 않는다면 result 는 이미 -1로 채워져있기 때문에 따로 -1를 추가해줄 필요가 없다.
- 그러면 스택은 비어있게 되고 while 문을 빠져나와 다시 스택에 i 인덱스를 추가해준다.
- 이러한 과정을 계속해서 반복해준다.
스택을 인덱스를 담는 그릇으로 활용할 수 있다.
print(*리스트) 를 하면 리스트의 내용을 사이사이 공백을 두고 출력해준다.
