알고리즘 문제(Swift)

알고리즘 문제(Swift) - 백준 - 10972 (다음 순열)

Goniii 2025. 1. 5. 21:48

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

 

첫 번째 방법: 재귀 함수 이용 (String 타입 배열)

let N = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map{String($0)}
var visited = Array(repeating: false, count: N + 1) // 숫자의 방문 여부 저장
var flag = false // 현재 입력 순열을 찾았는지 여부
var isLast = false // 마지막 순열인지 여부 (마지막 순열까지 입력 순열을 못찾았으면 "-1" 출력을 위함)

func recur(choose: [String]) {
    if choose.count == N {
        if flag { // 입력 순열 이후 순열일 경우, 해당 순열 추가
            print(choose.joined(separator: " "))
            flag = false
            isLast = false // 마지막 순열이 아니니, false 처리
        }
        if choose == input { // 선택한 순열이 입력 순열과 같다면 flag 변경
            flag = true
            isLast = true // 마지막일 경우 true로 변경
        }
        return
    }
    
    for i in 1...N {
        if visited[i] { continue } // 이미 선택한 숫자는 건너뜀
        visited[i] = true // 숫자 선택 
        recur(choose: choose + ["\\(i)"])
        visited[i] = false // 숫자 선택 해제
    }
}
recur(choose: [])

if isLast { 
    print(-1) // 마지막 순열이면 -1 출력
}

→ 메모리 초과

  • 재귀함수 내에서 choose 배열을 출력이 빠르도록 String 배열로 선언 했지만, 위 문제에는 출력이 하나 뿐이므로, Int 배열로 수정이 필요함
  • String은 16 byte, Int는 4 byte이기 때문에 Int가 메모리 관리에 효과적

 

두 번째 방법: 재귀 함수 이용 - Int 배열로 변경

  • String 타입은 16 byte, Int는 4 byte 이므로 Int 배열로 변경
let N = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map{Int($0)!}
var visited = Array(repeating: false, count: N + 1) // 숫자의 방문 여부 저장
var flag = false // 현재 입력 순열을 찾았는지 여부
var isLast = false // 마지막 순열인지 여부 (마지막 순열까지 입력 순열을 못찾았으면 "-1" 출력을 위함)

func recur(choose: [String]) {
    if choose.count == N {
        if flag { // 입력 순열 이후 순열일 경우, 해당 순열 추가
            print(choose.map{String($0)}.joined(separator: " "))
            flag = false
            isLast = false // 마지막 순열이 아니니, false 처리
        }
        if choose == input { // 선택한 순열이 입력 순열과 같다면 flag 변경
            flag = true
            isLast = true // 마지막일 경우 true로 변경
        }
        return
    }
    
    for i in 1...N {
        if visited[i] { continue } // 이미 선택한 숫자는 건너뜀
        visited[i] = true // 숫자 선택 
        recur(choose: choose + ["\\(i)"])
        visited[i] = false // 숫자 선택 해제
    }
}
recur(choose: [])

if isLast { 
    print(-1) // 마지막 순열이면 -1 출력
}

→ 시간 초과

  • 배열 타입을 Int로 변경하여 메모리 초과 문제는 해결되었으나 시간 복잡도가 여전히 높음

 

세 번째 방법: 시간 초과를 막기 위해 재귀 함수 종료 로직을 추가

let N = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map{Int($0)!}
var visited = Array(repeating: false, count: N + 1)
var flag = false
var isBreak = false // 재귀 호출을 조기 종료하기 위한 변수

func recur(choose: [Int]) {
    if isBreak {return} // 조기 종료 조건
    if choose.count == N {
        if flag {
            print(choose.map{String($0)}.joined(separator: " "))
            isBreak = true // 다음 순열을 찾았으면 조기 종료 설정
        } 
        if choose == input {
            flag = true
        }
        return
    }
    
    for i in 1...N {
        if visited[i] { continue }
        visited[i] = true
        recur(choose: choose + [i])
        visited[i] = false
    }
}

if input == Array(1...N).reversed() { // 마지막 순열이라면 -1 출력
    print(-1)
} else {
    recur(choose: [])
}

→ 시간 초과

  • 시간 초과를 해결하기 위해 조기 종료 로직을 추가했지만, 모든 순열을 확인해야 하는 방식 자체가 비효율적인 것 같음

 

네 번째 방법: 순열의 규칙 이용

순열의 규칙

  • N = 5: 순열의 길이가 5일 때
  • 1 2 5 4 3 → 이후 순열은 1 3 2 4 5
  1. N -1 부터 i를 1씩 줄여가면서 array[i - 1] < array[i] 인 i를 찾기!
    • 1 2 5 4 3 → i = 4, array[i - 1] = 4, array[i] = 3
    • 1 2 5 4 3 → i = 3, array[i - 1] = 5, array[i] = 4
    • 1 2 5 4 3 → i = 2, array[i - 1] = 2, array[i] = 5 → array[i - 1] < array[i]
    → i = 2, i -1 = 1
  2. N - 1부터 i까지 array[i - 1] < array[j] 인 j를 찾기
    • j는 4, 3, 2 순으로 내려감 → i가 2이기 때문
    • 1 2 5 4 3 → j = 4 일 때, array[i - 1] = 2, array[j] = 3 → array[i - 1] < array[j]
    → j = 4
  3. array[i - 1]과 array[j]의 값을 Swap
    • array.swapAt(i - 1, j)
    • 변경 전
      • array[i - 1] = 2
      • array[j] = 3
    • 변경 후
      • array[i - 1] = 3
      • array[j] = 2
    → 1 3 5 4 2
  4. i ~ N - 1까지 오름차순 정렬
    • i = 2, N - 1 = 4
    → 1 3 2 4 5
import Foundation
let N = Int(readLine()!)!
var input = readLine()!.split(separator: " ").map{Int($0)!}

if input == Array(1...N).reversed() { 
    print(-1) // 마지막 순열이면 -1 출력
} else {
    Loop: for i in (0..<N).reversed() { // N - 1부터 i를 1씩 줄여가면서 array[i - 1] < array[i] 인 i를 찾기!
        if input[i - 1] < input[i] {
            for j in (i..<N).reversed() { // N - 1부터 i까지 array[i - 1] < array[j] 인 j를 찾기
                if input[i - 1] < input[j] {
                    input.swapAt(i - 1, j) // array[i - 1]과 array[j]의 값을 Swap
                    let sortedArray = input[i...].sorted() // i ~ N - 1까지 오름차순 정렬 
                    input = input[...(i-1)] + sortedArray // 최종 결과 조합
                    print(input.map{String($0)}.joined(separator: " "))
                    break Loop // 외부 루프 종료
                }
            }
        }
    }
}
  • Loop 레이블
    • 첫번째 for 루프에 레이블 Loop를 붙여 break Loop를 통해 해당 루프 전체를 종료함
    • Loop 레이블을 사용하지 않고 내부 for문에서 break를 사용해도 외부 for문을 작동하기 때문에 Loop 레이블을 사용

→ 효율적인 코드 실행 가능

 

728x90