[Swift][문자열] 백준 10973번 (이전순열)

요구능력 : 문자열의 이해

 

코드설명 : 

 

이 문제는 딱 세가지만 알면 쉽다.

첫째, 큰수 > 작은수

둘째, 내림차순

셋째, 큰수 > 작은수에서 큰수보다 작으면서 맨 마지막에 있는 인덱스

 

처음에 문제를 풀때 다음순열과 비슷한 방식으로 접근했다.

그래서 수를 나열 해봤는데 아래와 같은 규칙이 나왔다.

.

.

.

1 2 4 5 3

1 2 4 3 5

1 2 3 5 4

1 2 3 4 5

 

우선 쭉 보면서 어디가 바뀌는지 찾아보자.

1. 1 2 4 5 3 -> 1 2 4 3 5

2. 1 2 4 3 5 -> 1 2 3 5 4

 

1번은 5와 3의 자리가 바뀌었고

2번은 4와 3과 5의 자리가 바뀌었다.

 

직접 적으면서 해보면 알겠지만,

왼쪽부터 오른쪽으로 수를 돈다고 가정할 때,

큰수 > 작은수 가 되는 부분이 있다.

수를 쭉 나열해보면 여기서 큰수 부분의 자리가 계속 바뀌는 규칙이 있다.

여기까지 보면 하나 해결한거다. 

 

그리고 두 번째,

여기서 주목할점은 1 2 4 3 5 이다.

1 2 4 3 5는 1 2 3 5 4가 된다.

4(index : 3)와 3(index : 4)의 값이 바뀌고 3(index : 3)인 부분 뒤로 내림차순이 된것이 보일것이다.

 

그리고 세 번째,

이 규칙이 가장 찾기 어려울 것이다.

순열을 잘 모르는 사람에게서 이왜틀(이게 왜 틀려?)나오기 딱 좋은 부분

그래서 이해하기 쉬운 예제를 준비해 봤다.

1 2 5 3 4를 보자.

1 2 5 3 4의 이전순열은 1 2 4 5 3 이다.

위에서 찾은 규칙대로 보면 큰수 > 작은수가 나오는 부분인 5와 3의 자리를 바꿔준다.

그리고 그 뒤를 내림차순해주면 1 2 3 5 4가 나오게된다.

위에서 찾은 첫번째, 두번째대로 했는데 틀렸다.

해결방법을 알아보자.

1. 1 2 5 3 4에서 큰수>작은수에서 큰 수 부분을 찾는다.

2. 5(index: 2)가 큰수이다.

3. 여기서 큰수 > 작은수에서 작은수는 그냥 작은수가 아니고 배열의 맨 뒤에있는 작은수이다. 왜냐하면 그렇게해야 순열이 완성되니까.

 

이렇게하면 이전 순열 문제의 알고리즘 설명이 끝난다.

 

 

후기 : 다음순열이랑 같은원리다. 처음 순열을 접한다면 어려움이 있겠지만 한번 풀어봤다면 금방 넘어가는 문제

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int($0)!}
var temp: Int = 0
var bigTemp = 0

if arr.sorted() == arr {
    print("-1")
}else {
    for i in 0..<arr.count{
        if i + 1 < arr.count, arr[i] > arr[i + 1]{
            temp = i
        }
    }
    
    for i in (temp + 1)..<arr.count {
        if arr[temp] > arr[i] {
            bigTemp = i
        }
    }
    
    arr.swapAt(temp, bigTemp)
    arr[(temp + 1)..<arr.count].sort(by: >)

    print(arr.map{String($0)}.joined(separator: " "))
}