[Swift][BruteForce] 백준 6603번 (로또)

요구능력 : N과M에 대한 이해

 

코드설명 : 

 

문제를 보면 N과M시리즈와 매우 유사하다.

1. N개의 수 중에서 6개를 뽑는다.

2. 비내림차순

 

1. 문제의 조건을 맞춰주는 부분

문제에서는 0이 입력되기전까지 계속해서 받으라고 했으므로 while문으로 처리를 해준다.

그리고 배열에서 맨 앞의수는 필요없으니 버려준다.(어차피 N개의 수에서 6개만 뽑아서 오름차순해줄것이기 때문이다.)

while true{
    input = readLine()!.split(separator: " ").map{Int(String($0))!}
    if input[0] == 0 {
        break
    }else {
        input.removeFirst()
        dfs(0, 0)
        print("")
    }
}

 

2. 백트래킹을 이용해서 N개의 수중 6개를 뽑아준다.

이 정도 수준까지 푸실정도면 N과 M은 한번쯤 풀어보셨을거라 생각합니다.

여기서 중요한점은 N의 수에서 6개를 뽑는데, 오름차순으로된 것만 뽑아야 한다는 것이다.

하지만, 그렇다고 6개를 다뽑은 시점에서 정렬된것과 비교한다면 매우 비효율적인 코드가되고 시간복잡도가 올라가서 시간초과가 나온다.

여기서 중요한점은 문제에서 "S의 원소는 오름차순으로 주어진다."라는 것이다.

오름차순이기 때문에 for문이 0에서 시작하면 다음번엔 1부터 시작하게될거고 1부터시작하면 다음번엔 2부터 시작하게된다.

이렇게 되면 시간도 대폭줄어들고 다음번에 시작하게되는 인덱스들이 현재 인덱스보다 커져서 자동으로 오름차순이 된다.

예를들어, 만약 [0]에서 시작했다면 다음번에 도는건 [1]부터 시작하면 자동으로 오름차순이 된다.

이해가 안간다면, 손으로 디버깅해보면 이해가갈것이다.

func dfs(_ depth: Int, _ start: Int){
    if depth == 6 {
        
        print(result.map{String($0)}.joined(separator: " "))
        return
    }
    for i in start..<input.count{
        if !visited[i] {
            visited[i] = true
            result.append(input[i])
            dfs(depth + 1, i)
            result.removeLast()
            visited[i] = false
        }
    }
}

 

후기 : 처음에 순열카테고리에 있어서 순열로 풀다가 복잡해져서 N과M방식으로 풀면 잘풀릴거같아서 N과M으로 풀었는데 쉽게 통과했다.

var input: [Int] = []
var sum = 1
var visited = Array(repeating: false, count: 13)
var result: [Int] = []
while true{
    input = readLine()!.split(separator: " ").map{Int(String($0))!}
    if input[0] == 0 {
        break
    }else {
        input.removeFirst()
        dfs(0, 0)
        print("")
    }
}

func dfs(_ depth: Int, _ start: Int){
    if depth == 6 {
        print(result.map{String($0)}.joined(separator: " "))
        return
    }
    for i in start..<input.count{
        if !visited[i] {
            visited[i] = true
            result.append(input[i])
            dfs(depth + 1, i)
            result.removeLast()
            visited[i] = false
        }
    }
}