BOJ-17299 오등큰수 Swift

문제

크기가 N인 수열 A = $A_{1}, A_{2}, ..., A_{N}$이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

$A_{i}$가 수열 A에서 등장한 횟수를 F($A_{i}$)라고 했을 때, $A_{i}$의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F($A_{i}$)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. $A_{1}$의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. $A_{3}$의 경우에는 $A_{7}$이 오른쪽에 있으면서 F($A_{3}=2$) < F($A_{7}=1$) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 $A_{1}, A_{2}, ..., A_{N}$ (1 ≤ $A_{i}$ ≤ 1,000,000)이 주어진다.

출력

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

내가 푼 풀이

접근방법: 스택

이전문제인 오큰수를 풀었다면 원리를 알기 쉽다.

주어진 수열을 왼쪽부터 검사한다면, 오른쪽에 위치한 수를 모두파악해야하므로 O($N^{2}$)가 걸린다.

주어진 수열을 반대로 오른쪽부터 왼쪽순으로 검사한다.

스택의 상단 원소와 현재 원소를 비교한다.

스택이 비어있다면, 오등큰수가 존재하지않는다는 의미다

스택이 비어있지않다면, 현재원소와 비교하여 등장횟수가 작거나 같은 원소들은 모두 Pop한다.

 

이렇게 스택의 원소들을 비워주었다면, 스택의 상단원소는 현재원소의 오등큰수가 된다.

스택이 비어있다면 오등큰수가 존재하지않음(-1)

스택을 갱신해주며 수열의 첫번째 원소까지 검사해준다.

 

등장횟수를 저장할 딕셔너리를 선언했지만, 시간초과가 났다.

배열의 크기를 100만으로 선언후 등장횟수를 저장했더니, 딕셔너리보다 더 빠르게 접근 가능했다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = Array(readLine()!.split(separator: " ").map{Int(String($0))!}.reversed())
// 등장횟수 저장할 배열
var nums = Array(repeating: 0, count: 1000001)
for i in arr {
    nums[i] += 1
}
// 스택과 결과를 저장할 배열
var result = [Int]()
var stack = [Int]()
var answer = ""

// 주어진 수열의 마지막원소부터 검사
for i in 0..<arr.count {
    // 스택의 상단원소가 현재원소보다 등장횟수가 많은 원소가 위치하도록 Pop
    while !stack.isEmpty && nums[stack[stack.count-1]] <= nums[arr[i]] {
        stack.removeLast()
    }
    // 스택이 비어있다면 오등큰수는 존재하지않음
    // 비어있지 않다면 오등큰수는 스택의 상단원소가 됨
    if stack.isEmpty {
        result.append(-1)
    } else {
        result.append(stack.last!)
    }
    // 오른쪽에 위치한 원소중 가장 왼쪽에 있는 원소가 오등큰수가 되므로 현재원소를 스택에 넣어준다.
    stack.append(arr[i])
}

// 결과 출력
for i in (0..<result.count).reversed() {
    if i == 0 {
        answer += "\(result[i])"
    } else {
        answer += "\(result[i]) "
    }
}
print(answer)