[Algorithm] 백준 - 17299번 오등큰수 (Swift)

문제 소개

17299번: 오등큰수

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 설명하기가 좀 복잡해서 아래 문제 캡처를 첨부한다.

 

문제 풀이

처음 등장한 횟수를 어떻게 저장할까 고민했는데, 가장 효율적으로 접근이 가능한 데이터 구조는 딕셔너리 구조라고 생각했다. 따라서 아래와 같이 딕셔너리에 반복되는 횟수를 저장해 줬다.

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

var count = [Int: Int]()

for num in nums {
    if count[num] == nil {
        count[num] = 1
    } else {
        count[num]! += 1
    }
}

 
그리고 어떻게 이 값을 비교할 수 있을까? 바로 스택을 사용하면 된다. index를 stack에 쌓고, 쌓인 index를 문제조건에 따라 추출 할 수 있게 했다.

import Foundation

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

var count = [Int: Int]()
var stack = [Int]()

for num in nums {
    if count[num] == nil {
        count[num] = 1
    } else {
        count[num]! += 1
    }
}

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

for i in stack {
    nums[i] = -1
}

print(nums.map { String($0) }.joined(separator: " "))