[Swift] 백준 17298 - 오큰수

문제 링크

처음엔 for문을 이중으로 사용해서 풀었었다..

시간초과된 풀이

import Foundation

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

for i in 0..<n-1 {
    
    var result = 0
    
    for j in i+1..<array.count {
        
        if array[j] > array[i] {
            result = array[j]
            break
        }
    }
    
    print(result != 0 ? result : -1,terminator: " ")
}

print(-1)

다음과 같이 풀었고 당연히,, 시간초과되었다.
수의 범위를 보면 당연한데 이걸로 테스트케이스들이 해결되니 미련을 못 버리고 이걸로 자꾸 뭘 하려고 했음^^,,;;;

어쨌든, 얘를 버리고 문제 아래에 알고리즘에 stack이 있기에 스택을 이용해서 풀어보려 했다...!
그런데 모르겠고 모르겠고 모르겠어서
다른 사람들의 풀이를 참고해서 풀었다.

먼저 배열은 두 개 필요하다.
readLine()으로 입력받은 수를 담고 있을 array와
오큰수를 가지지 않는 수의 자리 값을 가지는 stack

먼저, stack이 비어있지 않은 경우,

• 만약 array[stack.last] 보다 현재의 값이 크다면 이것은 오큰수이다.
  • 그렇기에 'array[stack.removeLast()] = 현재 값' 으로 설정하여, stack에서 해당 자리 값을 제거하고, removeLast()로 반환받을 현재 자리 값을 이용하여 array배열의 해당 위치에 오큰수를 넣어준다.
• array[stack.last]보다 현재 값이 작다면, 오큰수를 가지지 않기 때문에 stack에 현재의 자리 값을 append 해준다.

stack이 비어있다면 제일 첫 원소이므로 stack에 현재 자리 값을 append한다.

위의 작업이 끝나면,
array배열에는 오큰수를 가지는 원소들만 오큰수로 값이 바뀌고
stack배열에는 오큰수를 가지지 않는 원소들의 자리 값이 들어가 있다.

따라서 for문을 사용해서 array에서 stack위치의 원소값을 -1로 바꾸면된다.

최종 코드

import Foundation

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

for i in 0..<n {

    while !stack.isEmpty && array[stack.last!] < array[i] {
        array[stack.removeLast()] = array[i]
    }
    
    stack.append(i)
}

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

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

어렵다 그치만,, 재밌다!!!