[Swift Algorithm] 오큰수 BOJ #17298

문제 설명

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

입출력 예제

입력1

4
3 5 2 7

출력1

5 7 7 -1

 

입력2

4
9 5 4 8

출력2

-1 8 8 -1

 

내 문제 풀이

import Foundation

var count = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map({Int(String($0))!})
var stack = [[0, nums[0]]]
var answer = Array(repeating: "-1", count: count)

for i in 1..<nums.count {
    while !stack.isEmpty && nums[i] > stack.last![1] {
        answer[stack.removeLast()[0]] = "\(nums[i])"
    }
    stack.append([i, nums[i]])
}

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

• 스택, LIFO로 풀이했다.
• nums 배열에 공백으로 구분한 입력 숫자들을 넣어주었고,
  인덱스와 nums값을 쌍으로 갖는 stack 배열을 생성했다.
• 오큰수를 찾지 못한 수는 -1로 표시해야 하기 때문에 처음부터 -1로 채운 배열을 만들었다.
• for문 시작 전, 미리 nums 첫 번째 수를 stack에 넣었고, for문은 1부터 시작했다.
• 스택이 비어있지 않으며, 스택의 마지막 요소가 현재 입력된 nums 값보다 작을 때 반복을 시행했다.
• stack의 마지막 요소를 삭제함과 동시에 삭제된 수의 인덱스를 answer배열의 위치로 사용했다.

아래 자세한 풀이 과정을 첨부한다. 

 

➕

그리고 내가 이 문제를 빨리는 풀었는데,, 자꾸 시간초과가 나서 애먹었다.

근데 그 이유가 단지 spilt 대신 components를 써서,, 그런거였다.

split이 components보다 시간을 덜잡아먹고, 성능이 좋다고 한다. 

지금까지는 이걸 몰랐고, components가 [String]으로 반환해주는게

사용하기 편해서 맨날 components로 사용했는데, 앞으로는 웬만하면 split으로 사용해야겠다.

(split과 components 비교! 요기👇)

2021.08.08 - [📍 Swift Note/📋 개념 정리] - [Swift] split과 components의 차이점

[Swift] split과 components의 차이점

 

💡 피드백

• 아직도 swift 언어에 대한 이해도가 부족한가보당 ㅜ 책좀 더 읽자!~

 

---

 

문제

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