[Swift][BruteForce] 백준 10972번(다음순열)

요구능력 : 순열에 대한 이해를 하고 있는가

 

코드설명 : 

 

문제에 나와있는 N = 3일때 만으로는 규칙을 보기 애매하다.

N = 4일 때를 기준으로 보자.

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

.

.

이 있다.

다음순열을 구하는데에는 내가 공부하면서 봐온바로는 2가지가 있다.

1. 앞에서부터 뒤로 탐색하는 방법

2. 뒤에서부터 앞으로 탐색하는 방법

 

아래의 코드도 2번방법으로 쉽게 변경가능하지만 1번방법으로 하겠습니다.

위의 나열되어있는 수 중에서 1 3 4 2를 보자.

1 3 4 2 -> 1 4 2 3 이된다.

이걸 아래 알고리즘으로 설명하기위해 첫번째 for문부터 살펴보면,

아래 코드를 보면 맨앞에서 맨뒤까지 i = 0일때, 1씩증가하는 i가 arr[i] < arr[i + 1]를 만족하면 idx에 i를 넣어주었다.

아래에서 위치를 바꾸기 위해서 마지막으로 커지는 부분의 인덱스를 넣어준것이다.

그렇다면 왜 마지막으로 커지는 부분의 인덱스를 넣어준것일까? 라는 의문을 가졌지만, 직접 손으로 써보면서 살펴보면 알겠지만,

그건 그냥 규칙이라고 생각하면 편할것이다.

 

이제 아래의 두 번째 for문을 살펴보자.

idx위치부터 for문이 실행된다.

arr[idx]보다 큰 인덱스와 큰 수를 갖는 인덱스(j)를 찾는것이다.

arr[idx]보다 큰 인덱스와 큰 수를 찾는 이유:

현재 1 3 4 2를 예시로 설명중이다.

위의 for문에서 idx값은 [1]이 나왔다.

 

반례를 들어 설명해 보면,

큰 인덱스 중에서 작은 수랑 arr[1]인 3이랑 맞바꾸면 그게 오름차순 순열은 확실히 아니게된다.

큰 인덱스가아닌 작은인덱스중에서 큰 수와 바꿔버리면 그것도 위의 이유와 마찬가지로 오름차순 순열이 아니게된다.

그렇다고 작은인덱스 중에서 작은 수랑 바꾸면? 이것도 말이 안된다.

 

이렇게 for문을 모두 실행하고 나서 바꾸기위해 구한 index를 스왑한다.

스왑하고나서 1 3 4 2 는 1 4 3 2가 될 것이다.

그럼 이건 오름차순 순열이 또 아니게된다.

앞부분 idx인 [1]까지는 가만히 냅두고 [1] 뒷부분은 오름차순 정렬을 해주면

1 3 4 2는 1 4 2 3이 된다.

 

여태까지 설명한걸 요약정리하자면,

1. 마지막에 오는 순열 부터 처리해준다.

2. 앞에서부터 뒤로가면서 수를 비교하고 마지막으로 큰 수가 나오는 부분의 인덱스를 구해준다.

3. 2번에서 구한 인덱스부터 뒤로 가면서 마지막으로 큰 수가 나오는 부분의 인덱스를 구해준다.

4. 구한 인덱스를 스왑한다.

5. 앞에서 스왑한 인덱스를 기준으로 뒤에있는 부분을 오름차순 정렬해준다.

 

후기 : 규칙을 찾고 어떻게든 풀어보려고 하루죙일 붙잡고 시간초과를 없애보려 했지만, 실패했다.

그래서, 코드를 여러개 찾아보다가 1등이신분의 코드가 가장 이해가 잘되서 보고 이해했다.

이걸 보고 Swift로 구현하는 다른 사람들에게 도움이 되기를..

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

if Array(1...n).reversed() == arr{
    print("-1")
}else {
    var idx = 0
    for i in 0..<n{
        if i + 1 < n, arr[i] < arr[i + 1] {
            idx = i
        }
    }

    var biggerIndex = 0
    for j in idx..<n {
        if arr[idx] < arr[j] {
            biggerIndex = j
        }
    }
    arr.swapAt(idx, biggerIndex)
    arr = arr[...idx] + arr[(idx + 1)...].sorted()
    print(arr.map{String($0)}.joined(separator: " "))
}