17298-Swift백준골드4

https://www.acmicpc.net/problem/17298

문제 해석

먼저 문제이다. 음..? 문제 이해는 굉장히 쉽다. 그냥 나보다 오른쪽에 있는 것들중에 큰것중에 나랑 가장 가까운 놈을 찾아서 찍어주면 된다.

단순히 생각할 수 있는 방법은 포인터를 이용한 방법이였다.  2중 For문을 통해 현재 내껏보다 오른쪽으로 하나씩 가면서 큰것을 발견하면 Break를 걸어주고 정답 Array에 추가해주는 방식이다. 하지만 문제를 잘 읽어보면 1,000,000까지도 가능하다. 최악의 경우 O(n제곱)인 기존의 방법으로는 시간초과가 뜰것이 분명하다. 그래서 다른 방식을 생각해보아야 했다.

문제 풀이

Stack을 활용하여 풀이를 한다. 먼저 가장 앞의 인덱스와 해당 넘버를 스택에 넣어준다. 그 후 한칸씩 뒤로 가며 비교를 하는데 이전의 값보다 만약 작다면 그냥 stack에 추가를 해준다. 만약 크다면 바로 이전에 추가한 마지막 [인덱스,넘버]를 삭제하고 해당 answer[인덱스]에 큰 값을 넣어준다. 여기서 한번만 하는게 아니라 작은게 있으면 반복해서 삭제하고 answer에 추가해준다.예시를 들면 3,5,6,1,3가 있다고 쳐보자. 먼저 3의 오큰수는 5이다. 

1.  stack = [[0,3]]
2.  5 > 3이므로 마지막에 삽입되어있는 것을 빼고 정답[0] = 5를 추가해주면 3의 오큰수가 5라는 것을 정확하게 의미한다. 
3.  그 후 stack에 [[1,5]]가 된다.
4.  다시 6은 5보다 크므로 마지막에를 빼주고 정답[1] = 6으로 해주면 5의 오큰수는 6을 정확히 의미한다. 그리고 다시 스택에 6을 넣어준다. [[2,6]]
5.  1은 6보다 작으므로 그냥 stack에 넣어준다. [[2,6], [3,1]]
6.  3은 1보다 크다. 그러므로 마지막에 들어있는것을 삭제하고 해당인덱스 정답[3] = 3을 넣어준다. 이렇게 되면 1의 오큰수는 3이라는 것을 성립한다.
7.  3은 6보다는 작으므로 다시 stack에 넣어준다. [[2,6], [4,3]]
8.  우리는 처음에 정답어레이를 -1로 개수만큼 초기화해주었다. 하지만 보면 0,1,3을 제외하고는 정답어레이를 건드리지 않았으므로 -1이 출력된다.

  문제코드

import Foundation
let n = Int(readLine()!)!
var aarrays = readLine()!.split(separator: " ").map{Int(String($0))!}
var stack = [[0,aarrays[0]]]
var answer = Array(repeating: "-1", count: n)
for i in 1..<aarrays.count {
    while !stack.isEmpty && aarrays[i] > stack.last![1] {
        answer[stack.removeLast()[0]] = "\(aarrays[i])"
    }
    stack.append([i,aarrays[i]])
}
print(answer.joined(separator: " "))