[백준 17298 파이썬/python] 오큰수

오큰수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	61149	20728	14851	32.789%

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

풀이

1)

def print_NGE(sequence):
    N = len(sequence)
    stack = []
    result = [-1] * N

    for i in range(N):
        while stack and sequence[stack[-1]] < sequence[i]:
            index = stack.pop()
            result[index] = sequence[i]
        stack.append(i)

    return result


if __name__ == "__main__":
    N = int(input())
    sequence = list(map(int, input().split()))
    result = print_NGE(sequence)
    print(' '.join(map(str, result)))

• 풀이과정
  1. 함수 print_NGE를 정의합니다. 입력 파라미터는 sequence입니다.
  2. 수열의 길이를 N으로 지정합니다.
  3. 스택을 초기화합니다.
  4. 결과 리스트를 초기화합니다. 모든 요소를 -1로 설정합니다.
  5. 수열의 인덱스를 순회합니다.
  6. 스택이 비어 있지 않고 스택의 가장 높은 인덱스에 있는 요소가 현재 요소보다 작은 동안 반복합니다.
  7. 스택의 가장 높은 인덱스 요소를 index에 할당하고 스택에서 제거합니다.
  8. 결과 리스트의 index 위치에 현재 요소를 할당합니다.
  9. 현재 인덱스를 스택에 추가합니다.
  10. 결과 리스트를 반환합니다.
  11. 현재 스크립트가 메인 스크립트로 실행되면 다음을 실행합니다.
  12. 정수를 입력 받아 N에 할당합니다.
  13. 정수들을 입력 받아 sequence 리스트에 할당합니다.
  14. print_NGE 함수를 호출하여 결과를 얻습니다.
  15. 결과를 출력합니다.

2)

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
s = [0]
for i in range(1, n):
    if not s:
        s.append(i)
    while s and a[s[-1]] < a[i]:
        ans[s.pop()] = a[i]
    s.append(i)
while s:
    ans[s.pop()] = -1
print(' '.join(map(str,ans)))

• 풀이과정
  1. 정수를 입력 받아 n에 할당합니다.
  2. 정수들을 입력 받아 a 리스트에 할당합니다.
  3. 결과 리스트인 ans를 초기화합니다. 길이는 n이고 모든 요소는 0입니다.
  4. 스택 s를 초기화하고 첫 번째 인덱스 (0)를 추가합니다.
  5. 수열의 인덱스 1부터 n까지 순회합니다.
  6. 스택이 비어 있지 않으면 스택에 인덱스를 추가합니다.
  7. 스택이 비어 있지 않고 스택의 가장 높은 인덱스에 있는 요소가 현재 요소보다 작은 동안 반복합니다.
  8. 결과 리스트의 스택의 가장 높은 인덱스 위치에 현재 요소를 할당하고 스택에서 제거합니다.
  9. 현재 인덱스를 스택에 추가합니다.
  10. 스택이 비어 있지 않은 동안 반복합니다.
  11. 결과 리스트의 스택의 가장 높은 인덱스 위치에 -1을 할당하고 스택에서 제거합니다.
  12. 결과를 출력합니다.

Uploaded by N2T