[BOJ] 17298 - 오큰수

문제

 

풀이 코드

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

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

for index in answer {
    nums[index] = -1
}

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

 

풀이 과정

혼자 해결하지 못한 문제였다.

 

처음 생각은 filter를 이용해 현재 인덱스의 값보다 작은것들만 모아놓고,

그렇게 생성된 배열이 비어있으면 -1을, 

비어있지 않으면 해당 배열의 첫번째 인덱스를 저장하면 될것 같았는데

애초에 그렇게 구현하지 못하는 문제였기도 했고, 가능하다 했어도 매번 filter를 사용해야 하기 때문에 시간초과에서 걸렸을것 같았다.

 

그래서 인터넷의 코드를 참고하여 이해하는 수준에 그쳤다..

너무 어려운 문제였다.

 

우선,

answer 배열에 -1이 들어갈 인덱스를 저장한다.

그리고 for 루프 내에서 while 루프를 돌려, 오큰수를 찾고, 오큰수를 찾지 못하면 해당 인덱스를 저장하여

 

마지막에 해당인덱스 요소를 -1 로 바꿔 주었다.

 

디버깅