[Swift] 9081 단어 맞추기 (next permutation)

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

9081번: 단어 맞추기

 

처음에는 재귀를 사용하여 구현하였는데 시간초과가 나서 검색을 뒤지다가 next permutation 이라는 저 기억 건너편에 있던게 생각이 났다...

왜 여태까지 next permutation 이 재귀로 구현된 것이라고 생각했는지 모를 노릇이지만.. 이제라도 알았다는 사실이 다행이다.

 

next permutation 은 재귀로 구하던 순열보다 훨씬 짧은 시간인 O(n) 시간안에 구할 수 있다.

자세한 설명

https://github.com/NEULiee/week-we-learn/blob/main/%F0%9F%92%AB%ED%95%98%EB%8A%98%EC%9D%B4/next_permutation.md

 

문제가 딱 현재 문자열에서 다음단계 순열을 구하는 것이기 때문에 next permutation 을 모두 돌려 모든 순열을 구할 필요 없이

한번만 돌려서 다음 순열을 찾아주면 된다.

for문보다 while문으로 구현하는 것이 코드가 더 깔끔하다.

 

+ 새로이 알게된 점 (아니 다시 깨달은 점..)

배열안에 범위를 넣어서 배열을 나눌 수 있다..!

word[..<top]
word[top...]

 

import Foundation

let T = Int(readLine()!)!

for _ in 0..<T {
    
    // next-permutation
    // 단어를 받고 reverse -> 앞에서부터 찾으려고
    var word = Array(readLine()!.reversed())
    // next-permutation 에서 word[i-1] < word[[i] 가 되는 가장 큰 값
    var top = -1
    
    // top 값 찾기
    for index in 0..<word.count {
        // 만약 찾는 값 없이 맨 앞에 도달했다면 이미 word가 마지막 순열 값
        if index == word.count - 1 {
            break
        }
        
        if word[index + 1] < word[index] {
            top = index
            break
        }
    }
    
    // 처음 word 값 출력
    if top == -1 {
        print(word.reversed().reduce("", { String($0) + String($1) }))
        continue
    }
    
    // top 값 뒤에 있는 (revere라서 앞에 있는) 값 중 top + 1의 값보다 큰 값 찾기
    for index in 0..<word.count {
        // index가 top보다 커질 경우를 고려할 필요가 없다.
        if word[top + 1] < word[index] {
            word.swapAt(top + 1, index)
            break
        }
    }
    
    // 원래 순서로
    word = word.reversed()
    
    top = word.count - top - 1
    let frontWord: String = word[..<top].reduce("", {String($0) + String($1)})
    // top 뒤의 값은 오름차순으로 정렬
    let backWord: String = word[top...].sorted(by: <).reduce("", {String($0) + String($1)})
    print(frontWord + backWord)
}

 

 

 

참조

https://rimkongs.tistory.com/212