[Swift][백준 알고리즘] 10972 다음 순열

 문제    

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

10972번: 다음 순열

 

 풀이방법    

아래는 12345가 입력으로 들어왔을 때 사전순으로 다음에 오는 순열을 구하는 프로그램의 일부이다.

당연한 말이지만,, 아래 flow의 규칙성을 찾아야 한다. 

12345
12354
12435
12453
12534
12543
13245
13254
...
54321

 

이 사전순으로 다음에 오는 순열을 구하는 프로그램에는 다음과 같은 규칙이 있다.

 

작성한 코드는 다음과 같다. 

import Foundation

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

// 4,3,2,1 이면 다음 값이 없음으로 반환
if Array(1...N).reversed() == array {
    print("-1")
} else {
    // range는 작은 거 ~ 큰 걸로 할 수 밖에 없음. reversed로 거꾸로 만들기
    Loop: for i in (0..<N).reversed() {
        // array[i-1] 가 array[i] 보다 작은 i-1 구하기
        if array[i-1] < array[i] {
            
            // i ~ N-1 인덱스에서 array[i-1] 보다 큰 녀석 찾기
            for j in (i..<N).reversed() {
                if array[i-1] < array[j] {
                    // 둘이 스왑
                    array.swapAt(i-1, j)
                    // i 앞은 그대로, i 부터는 오름차순으로 정리 (i 밑으로 reversed 해도 됨...!)
                    let orderArray = array[i...].sorted(by: <)
                    array = array[...(i-1)] + orderArray
                    
                    for i in 0..<N{
                        print(array[i], terminator: " ")
                    }
                    
                    break Loop
                }
            }
        }
    }
}

 

 

  Tips   

N-1부터 1씩 숫자를 줄여가면서 확인을 하는 것을 코드로 구현할 때 reversed()라는 녀석을 이용했다.

 

이를 C 언어에서는  i가 10부터 시작을 해서 0보다 클 때 까지 1씩 감소시키는 이런 for 문을 돌릴 수 있었다.

for (int i = 10, i > 0, i-- ){
	// code
}

 

하지만 swift에서는 이런 오류가 발생한다.

이 이유는 N-1...0과 같이 나타내는 게 ClosedRange<Int>형이고 하단의 정의에서 볼 수 있는 거처럼 작은 값에서 큰 값으로 증가하는 구조를 가져야 한다.

 

그래서 이런 경우에는 .reversed()로 값을 뒤집어 줘야 한다.

ClosedRange에 .reversed()를 하면 반환 값이ReversedCollection<ArraySlice<Element>>가 된다.

 

 

 

 성공한 사진!    

 

 

 Note    

수학... 조합론 ...

문제를 읽고 바로 안 풀려서 끙끙 거렸다. 다른 사람 코드도 보고 .. 이해를 하려고 많은 시간을 쏟고 나서야 문제를 풀 수 있었다.

여전히 갈 길이 멀구나...

reversed 를 알아보면서 ArraySlice 를 처음 알게 되었다. 이전에도 ArraySlice을 쓴 적이 있었는데 그때는 ArraySlice임을 모르고 썼었었다. 이미 알고리즘 짜면서 에너지를 많이 쏟은 상태라 힘들었는데 끝까지.. 공부를 한 내 자신.. 기특하다 ^^....

 

+ ) print

그리고 요즘 정의 보기에 재미를 들였는데 prit에도 여러 파라매터가 숨어 있었던 걸 알았다.. ㅎㅎ 제에발 알고 쓰자..