백준 17298 오큰수

출처: www.acmicpc.net/problem/17298

분류: 스택

---

접근방식

스택을 이용해서 풀 수 있었는데, 처음에 접근을 떠올리지 못해서 다른 분들의 풀이를 참고해서 겨우 풀었습니다.

 

 

아직 오큰수를 찾지 못한 수들을 스택에 담아줍니다.

현재 a[i]가 스택의 top 보다 크다면 top의 오큰수는 a[i]가 됩니다.
스택의 있는 수들은 아직 오큰수를 찾지 못한 수들이기 때문에 오른쪽에 있으면서 가장 큰 수가 바로 a[i] 입니다.

따라서 스택에는 오큰수를 찾지 못한 인덱스를 넣어주면서 a[i] 보다 크다면 빼서 해당 인덱스의 오큰수를 a[i]로 기록해주고,
다음으로 a[i]의 오큰수를 또 찾아야 하기 때문에 stack에 a[i]의 인덱스 i 를 넣어주고 넘어가줍니다.

for i in 0..<n {
    while !notFindIndices.isEmpty, a[notFindIndices.last!] < a[i] {
        let index = notFindIndices.popLast()!
        result[index] = "\(a[i])"
    }
    
    notFindIndices.append(i)
}

 

오큰수를 찾지 못한 수는 -1을 출력해야 하기 때문에

저는 처음에 -1로 세팅해주고 오큰수를 찾은 인덱스만 바꿔주는 방식으로 풀었습니다.

어차피 출력해야 하기 때문에 String으로 바꿔서 넣어주고 join 해서 print 해줬습니다.

 

해결방법

let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map { Int(String($0))! }
var result = [String](repeating: "-1", count: n)
var notFindIndices = [Int]()

for i in 0..<n {
    while !notFindIndices.isEmpty, a[notFindIndices.last!] < a[i] {
        let index = notFindIndices.popLast()!
        result[index] = "\(a[i])"
    }
    
    notFindIndices.append(i)
}

print(result.joined(separator: " "))

 

배운점

다른 분들의 풀이나 설명을 봐도 바로 이해하기가 어려웠다.... 

내 설명은 누군가에게 이해되기를...

처음에 다른 블로그의 거꾸로 접근하는 풀이 로 풀었는데 이건 시간초과가 나더라.. 긁적