[백준/Gold IV] 오큰수 - 17298

[Gold IV] 오큰수 - 17298

문제 링크

 

분류

자료 구조, 스택

 

문제 설명

크기가 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. 입력 받기:

let n = Int(readLine()!)!
let array = readLine()!.split(separator: " ").map { Int($0)! }

• 첫째 줄에서 수열의 크기 n을 입력받습니다.

• 둘째 줄에서 수열의 원소들을 공백으로 구분하여 입력받고, 이를 정수 배열로 변환합니다.

2. 초기화:

var result = Array(repeating: -1, count: n)
var stack = [Int]()

• result 배열을 -1로 초기화합니다. 이 배열은 각 요소의 오큰수를 저장합니다.

• stack은 각 요소의 인덱스를 저장하는 데 사용됩니다.

3. 배열 순회:

for i in 0..<n {
    while !stack.isEmpty && array[stack.last!] < array[i] {
        result[stack.removeLast()] = array[i]
    }
    stack.append(i)
}

• 배열의 각 요소에 대해 다음을 수행합니다:

• 현재 요소 array[i]보다 작은 스택의 모든 요소를 제거하고, 해당 인덱스의 오큰수를 현재 요소로 설정합니다.

• 현재 요소의 인덱스를 스택에 추가합니다.