goodseq

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• N이 80이므로, 완전탐색(Back-tracking)으로 문제를 해결할 수 있음
• 가장 작은 수를 나태내는 수열만 출력하기 위해서 가장 작은 수인 1부터 차례로 놓았을 때, 최초로 완성되는 수열을 출력하면 되는 것을 알 수 있음
• 각 자리자리 마다 1부터 수를 놓음으로써 해당 수를 포함하는 연속되는 부분에서 중복이 없다면 다음 숫자를 놓으면 되고, 그렇지 않으면 다시 되돌아와(Back-tracking) 다음 숫자를 놓아 하나하나 일일히 해봄으로써 문제를 해결할 수 있음
• 해당 수를 포함하는 연속되는 부분에서 중복이 없는지 검사하기 위해서는 현재 놓아야 하는 숫자가 가장 끝의 위치해 있을 것이고, 연속되는 구간을 1부터 (현재 위치 + 1) / 2 까지의 구간을 검사하게 되면 알 수 있음
• 가령, [1, 2, ] 다음에 숫자를 놓아야 할 경우, 현재 위치는 2이고, 구간 1부터 (2 + 1) / 2 = 1 까지 자신 부터 구간 만큼 떨어진 곳의 원소가 중복되는지만 검사하면 되는 것을 알 수 있음

5. 전체 코드

//MARK: - goodseq

//MARK: - Framework
import Foundation

//MARK: - Variable
var isFinished: Bool = false

//MARK: - Function
func isPossible(_ result: [Int], _ current: Int, _ interval: Int) -> Bool {
    var flag: Bool = false
    
    for i in 0..<interval {
        if result[current - i] != result[current - i - interval] {
            flag = true
            break
        }
    }
    
    return flag
}

func getGoodSeq(_ result: inout [Int], _ N: Int, _ current: Int) -> Void {
    if isFinished { return }
    
    if current >= N {
        var answer: String = ""
        for number in result {
            answer += "\(number)"
        }
        print(answer)
        isFinished = true
    } else {
        for i in 1...3 {
            var flag: Bool = false
            result[current] = i
            
            for j in stride(from: 1, through: (current + 1) / 2, by: 1) {
                if !isPossible(result, current, j) {
                    flag = true
                    break
                }
            }
            
            if !flag {
                getGoodSeq(&result, N, current + 1)
            }
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    var result: [Int] = Array(repeating: 0, count: N)
    
    //MARK: - Process & Output
    getGoodSeq(&result, N, 0)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.