[BOJ / 백준] 17298 오큰수 (G4 / 스택) - Python

링크

https://www.acmicpc.net/problem/17298

 

 

 

 

문제 해석

n개의 수가 주어졌을 때 i번째 수의 오큰수는 i보다 오른쪽에 있으면서 가장 왼쪽에 있는 i보다 큰 수

오른쪽에 i보다 큰 수가 없다면 -1

각 자리수의 오큰수를 구하라

 

 

입력

첫 번째 줄 : n

  n : 숫자 개수

두 번째 줄 : n개의 숫자

 

 

출력

각 자리의 오큰수 출력

 

 

 

 

풀이 & 코드 해석

나보다 큰 숫자가 무엇인지 판단하는 가장 원초적인 방법은 완전탐색일 것입니다.

 

그렇다면 시간 복잡도는 O(N^2)이 될 것인데 N의 범위가 1,000,000이므로 시간 초과가 날 수밖에 없습니다.

 

 

 

문제를 풀기 위해서 스택을 사용하는 방법을 생각해 보았는데요.

 

풀이 방식은 아래와 같습니다.

1. 입력된 배열을 역순으로 탐색한다.

2. 스택이 비어있다면 현재 탐색 중인 요소의 오큰수는 -1이다.

3. 스택이 비어있지 않다면 현재 탐색 중인 요소보다 큰 수가 나올 때까지 스택의 값을 하나씩 뺀다.

4. 현재 탐색 중인 요소를 스택에 삽입한다.

 

 

 

[ 3 5 2 7 ]

1)

이렇게 4가지 숫자가 있을 때, 가장 오른쪽에 있는 7부터 시작합니다.

 

7이 들어왔을 때 스택에는 아무 숫자가 없습니다. 

 

즉 나보다 오른쪽에 있는 숫자가 아무것도 없다는 뜻이 됩니다.

 

따라서 7의 오큰수는 -1이 되고, 스택에 7을 저장합니다.

 

 

 

2)

다음으로 2를 가지고 탐색을 진행합니다.

 

2는 스택에서 7이라는 값이 있으며(오른쪽에 7이 있음), 해당 숫자가 2보다 크기 때문에 오큰수가 7이 됩니다.

 

따라서 2의 오큰수는 7이 되고, 스택에 2를 저장합니다. 

 

 

 

3)

5를 가지고 탐색을 진행합니다.

 

스택에서 나온 값 2와 비교했을 때, 2보다 5가 더 크기 때문에 2는 정답이 될 수 없습니다.

 

여기서 중요한 점은 앞으로 나올 수가 5보다 작은 수라면 무조건 5가 오큰수가 될 것이고, 그렇지 않다면 다른 큰 수가 오큰수가 될 것입니다.

 

즉 앞으로 나올 어떠한 수도 2는 정답이 될 수 없다는 점입니다.

 

그렇기 때문에 2는 더이상 정답 후보가 될 수 없으므로 스택에서 제거합니다.

 

 

다음으로 스택에 있는 숫자인 7과 비교했을 때 5가 더 작기 때문에 5의 오큰수는 7이 됩니다.

 

스택에 5를 저장합니다.

 

 

4)

앞선 1)2)3)의 방식을 토대로 3의 오큰수는 5가 됩니다.

 

 

 

이 풀이의 핵심은 스택에는 정답이 될 수 있는 후보군만 남겨둠으로써 반복을 최소화하기 입니다.

 

이 문제도 빅오표기법으로 보면 O(N^2)으로 시간초과가 발생할 가능성이 있는 문제입니다.

 

다만 중복된 실행을 최소화함으로써 제한 시간 내에 문제를 풀 수 있습니다.

 

 

 

 

코드

n = int(input())

arr = list(map(int, input().split()))

stack = []
ans = [-1] * n

for i in range(n - 1, -1, -1):
    # 스택에 값이 있다면
    if stack:
        # 빌 때까지 반복
        while stack:
            peek = stack[-1]

            if peek <= arr[i]:
                stack.pop()
            else:
                ans[i] = peek
                break
    # 스택이 비어 있다면
    else:
        ans[i] = -1
    stack.append(arr[i])

for i in ans:
    print(i, end=" ")

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java