15656번: N과 M (7)

문제 풀이 아이디어

모든 수열을 구하는 N과 M 문제입니다. 완전탐색을 위한 dfs를 재귀함수로 구현하면 됩니다.

중복이 가능하므로 중복을 체크하는 배열을 사용하지 않고 dfs를 돌리면 됩니다. 다만 입력이 오름차순이라는 보장이 없으므로 사전 순으로 출력하기 위해서 오름차순으로 정렬합시다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
    //👉 정렬해서 입력 받기!

// 중간 결과를 저장하는 배열
var result = [String]()

// print문을 한번만 쓰기 위한 String
var toPrint = ""

// dfs 구현
func dfs() {
    // 탈출 조건
    if result.count == M {
        toPrint += result.joined(separator: " ") + "\n"
        return
    }
    
    // 중복이 가능하므로 중복 배열 없이 0 ~ N까지 순회
    for i in 0..<N {
        result.append(String(array[i]))
        dfs()
        _ = result.removeLast()
    }
}

// 함수 실행
dfs()
print(toPrint)

🚫  Print와 시간초과

제가 처음에 제출한 코드는 아래와 같이 매번 수열을 구할 때마다 print 함수를 실행하는 코드였는데 시간초과가 났습니다. 이처럼 print문을 너무 많이 호출하면 시간초과가 날 수 있습니다. map 함수와 마찬가지로 print도 반복문 안에서 사용하는 것을 자제합시다.

재귀함수 내부에서 print를 많이 호출 할 것이 예상된다면 “\n”을 활용해서 줄바꿈을 처리하는 것으로 하고 마지막에 1번만 print를 실행합시다.

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]

let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
var result = [String]()

func dfs(_ depth: Int) {
    if depth == M {
        print(result.joined(separator: " ")) //🚫 매번 print 실행 -> 시간초과
        return
    }
    
    for i in 0..<N {
        result.append(String(array[i]))
        dfs(depth + 1)
        _ = result.removeLast()
    }
}

dfs(0)