백준: 17298 오큰수

문제

17298번: 오큰수

 

문제 풀이

 3 5 2 7의 수열이 주어지면, 한 원소를 기준으로 오른쪽에 큰 값이 있으면 최초의 큰 값을 기록하여 반환하는 문제이다. 만약 큰 값을 찾을 수 없다면 -1을 반환한다. 이 문제는 다른 stack의 문제와 달리 수열의 값을 stack에 넣는 것이 아닌, 각 인덱스를 통해 문제를 해결하는 방식으로 접근하면 쉽게 풀 수 있다. 또한, 파이썬으로 문제를 풀기 위해서는 각 처리마다 list를 append 할 경우 시간 초과가 발생하므로, 미리 list를 초기화해두고 진행하여야 한다.🙂

 

1. stack에 인덱스 0번부터 추가하여, 우선 바로 옆 원소와 비교한다.
2. 1의 과정은 stack의 인덱스가 존재하지 않을때 까지 반복한다.
3. 2의 과정이 끝나면 다음 인덱스를 추가한다.

1 - 3의 과정을 3 5 2 7과 같은 예시가 입력될 경우에 대한 처리를 진행한다면 다음과 같이 진행된다.

• 0번 인덱스를 stack에 넣고 다음 인덱스인 1과 비교하니 값이 크므로 인덱스 0의 값을 5로 갱신하고 인덱스 0을 stack에서 pop 한다.
• 1번 인덱스를 stack에 넣고 다음 인덱스인 2와 비교하니 값이 크지 않으므로 갱신하지 않는다.
• 2번 인덱스를 stack에 넣고 다음 인덱스인 3과 비교하니 값이 크므로 인덱스 2의 값을 7로 갱신하고 인덱스 2를 stack에서 pop 한다.
  • 아직 stack에 1번 인덱스가 있으니 인덱스 1과 다음 인덱스인 3을 비교하니 값이 크므로 인덱스 1의 값을 7로 갱신하고 인덱스 1을 stack에서 pop 한다.
• 가장 마지막인 3번 인덱스는 확인할 필요가 없다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    stack = [0]
    answer = [-1] * n

    i = 1

    while i < n:
        while stack and nums[stack[-1]] < nums[i]:
            answer[stack[-1]] = nums[i]
            stack.pop()

        stack.append(i)
        i += 1

    for num in answer:
        print(num, end=' ')

 문제 풀이에서 소개한 풀이 방법을 그대로 코드로 작성한 것이다. answer를 미리 -1로 초기화해두어 변경이 없을 경우 처리할 필요 없이 진행하면 된다. 원소를 탐색하면서 stack에 값이 있을 경우 같이 처리해야 한다. (채점 시 시간이 상당히 소요된다.)