백준 17298 오큰수
23 Jun 2021https://www.acmicpc.net/problem/17298
수열이 주어졌을 때 각 원소에 대해서 본인보다 오른쪽에 있으면서 본인보다 원소 값이 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다. 이 때 존재하지 않는다면 -1을 출력하도록 한다.
스택을 활용하면 아주 간단하게 풀리는 문제이다. 먼저 스택에 수열을 앞에서부터 집어넣는데 이 때 수열의 index를 같이 저장시켜준다. 만약 새롭게 들어오는 원소가 stack에 top에 들어있는 값보다 크다면 stack에서 pop해준 뒤 해당 index에 새롭게 들어오는 원소값을 입력해주면 되는 문제이다.
최종적으로 stack에 남아있는 원소들에 대해서는 index를 하나씩 찾아가 -1을 입력해주면 된다.
- 전체 코드
let n = Int(readLine()!)!
var num = readLine()!.split(separator: " ").map{Int(String($0))!}
var stack:[(v:Int, i:Int)] = []
stack.append((v:num[0], i:0))
for i in 1..<n {
let value = num[i]
while let tmp = stack.last {
if tmp.v < value {
num[tmp.i] = value
stack.removeLast()
}
else {
break
}
}
stack.append((v:num[i], i:i))
}
while let tmp = stack.popLast() {
num[tmp.i] = -1
}
var str = ""
for i in num {
str += "\(i) "
}
print(str)