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

3. y에 해당하는 인덱스부터 sort(오름차순정렬)를 한 뒤에 이어 붙인다.

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

10972번: 다음 순열

 

 

 

 

풀이 과정 

https://ji-gwang.tistory.com/262

백준 10972번 파이썬 문제풀이(브루트 포스 - 다음 순열)

1 4 3 2를 예시로 알고리즘을 알아본다.

 

1. 뒤에서부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고, (1,4)가 해당된다. 
   1. 이 때, 1의 인덱스를 x라고 칭한다.
   2. 4의 인덱스는 y라고 한다.
2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
   1. 1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap한다.
3. y에 해당하는 인덱스부터 sort(오름차순정렬)를 한 뒤에 이어 붙인다.
   1. 4 3 1을 sort해서 1 3 4가 된다.
   2. 이어 붙이기 때문에 2 1 3 4가 된다.

어떻게 하는지 그리고 왜 그렇게 되는지 아무리 생각해 봐도 답이 안나와서 풀이 참고해 봤음. 이미 예시를 잘 들었지만... 이거 이해 안가서 다시 해봤음...

 

Example)

arr = [5, 4, 6, 3, 2, 1] 일 때를 가정해 보자.

1. 뒤에서 부터 순열을 비교하며  뒷 값이 앞 값보다 큰 경우까지 반복한다.

이렇게 된다면 (2, 1) (3, 2) (6, 3) 을 돌다가 (4, 6)에서 멈춘다. 이 때 xInd yInd를 저장한다. xInd = 1, yInd = 2 에 대입한다. 

정리하면 이렇게 된다. xInd = 1, arr[xInd] = 4 // yInd = 2, arr[yInd] = 6 

 

2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.

arr[xInd] 보다 큰 값을 찾는다. 이는 inputArr에서 역순으로 찾는다. for문에서 찾기위해 돌아가는 값을 tempValue라고 칭할 때 tempValue = 1 , 2, 3, 6 ... 으로 돌아간다. 이 때 가장먼저 arr[xInd]보다 큰 값이 나오는 tempValue는 6이다.

swap을 진행한 arr은 [5, 6, 4, 3, 2, 1]이 된다.

 

3. y에 해당하는 인덱스부터 sort(오름차순정렬)를 한 뒤에 이어 붙인다.

yInd = 2인데 3번에 따라서 arr이 2부터 정렬한다. arr[2...]은 [4, 3, 2, 1]인데 이것을 오름차순 정렬하게 된다면 [1, 2, 3, 4]이다. 따라서 결과는

resArr = arr[0..<2] + sortedArr

 

4. 예외처리

만약 inputArr에서 변화가 이루어지지 않을 때 예외처리를 해준다.

func corSol() {
    let N = Int(readLine()!)!
    var inputArr = readLine()!.split(separator: " ").map{Int($0)!}
    let flag = inputArr
    var xInd = 0
    var yInd = 1
    for i in stride(from: N - 2, to: 0 - 1, by: -1) {
        if inputArr[i] < inputArr[i + 1] {
            xInd = i
            yInd = i + 1
            break
        }
    }
    
    for i in stride(from: N - 1, to: 0 - 1, by: -1) {
        if inputArr[xInd] < inputArr[i] {
            let temp = inputArr[i]
            inputArr[i] = inputArr[xInd]
            inputArr[xInd] = temp
            break
        }
    }
    if flag == inputArr {
        print(-1)
        return
    }
    let tempArr = inputArr[yInd...].sorted(by: <)
    let resArr = inputArr[..<yInd] + tempArr
    print(resArr.map{String($0)}.joined(separator: " "))
}