[자료구조(연습)] [BJ17298] 오큰수

코드 플러스

🚩 문제 설명

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

17298번: 오큰수

⏱️ 시간 복잡도
▪ 수열의 크기를 보면 100만이다 ~= 10^6
▪ 따라서 해당 문제는 O(100 x N)을 넘어가서는 안된다.

◾ A의 각 원소 A(i) 에 대한 오큰수 NGE(i)

• A(i)의 오른쪽에 있으면서 A(i) 보다 큰 수 중에서 제일 왼쪽에 있는 수

◾ 만약 오큰수가 없다면 -1 을 출력한다.

◾ 주어진 수열에 대한 오큰수를 출력하는 문제

 

 

 

---

 

 

 

✅ 입출력

1) N : 주어지는 수열의 크기
2) A의 원소인 A(i)
return ➡️ 각 원소의 오큰수를 출력

✔️ 예제 1

4
3 5 2 7

5 7 7 -1

 

✔️ 예제 2

4
9 5 4 8

-1 8 8 -1

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
stack = [0]  # 스택 배열
ans = [-1] * N  # 오큰수 배열

for i in range(1, N):
    while stack and nums[stack[-1]] < nums[i]:
        ans[stack.pop()] = nums[i]
    stack.append(i)

print(*ans)

💬 Point

➡️  스택 사용
➡️  print(*ans)로 unpacking

◾ print(*ans)를 사용하면 배열 안에 있는 원소들만 빼올 수 있다.

◾ 문제의 이해는 다음과 같다.

◾ 만약 nums = [3, 5, 2, 7] 과 같다면,

◾ ans는 오큰수를 담을 배열이다.

◾ stack은 오큰수를 아직 찾지못한 stack의 인덱스를 담는다.

◾ nums[1] = 5 > nums[stack[-1] = 0] = 3 이므로 오큰수이므로 ans[0]은 5가 된다.

◾ stack에는 다음 오큰수를 찾을 stack의 인덱스가 push 된다.

◾ nums[2] = 2 < nums[stack[-1] = 1] = 5 이므로 오큰수가 아니다.

◾ 따라서 오큰수를 찾지 못하여 stack에 push 된다.

◾ nums[3] = 7 > nums[stack[-1] = 2] = 2 이므로 오큰수다.

◾ 따라서 ans 배열에 stack[-1] = 2 인덱스에 오큰수가 들어간다.

◾ nums[3] = 7 > nums[stack[-1] = 1] = 3 이므로 오큰수다.

◾ 따라서 ans 배열에 stack[-1] = 1 인덱스에 오큰수가 들어간다.

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 오큰수 파이썬

# 백준 17298 오큰수 파이썬

# 백준 오큰수 파이썬

---