백준 N과 M (9) - boj15663

15663번: N과 M (9)

백준의 N과 M 문제입니다.

이 문제는 시리즈에요.

문제풀이 방법을 잘못 접근했는데 그 과정에서 재미있는 사실을 발견해서 포스팅하게 되었습니다.

 

문제 설명

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

문제풀이 방법

아주 기본적인 백트래킹 문제입니다.

그런데 저는 DFS로만 풀었어요 ㅎㅎ

그래서 시간이 1212ms가 나왔습니다.

참고로 1페이지는 대부분 200ms였습니다.

20230424 뒤에서 5등...

자랑스러운 성적이죠?

이 문제의 요점은 같은 수가 여러 번 주어질 수 있다는 점입니다.

예제 입출력 2번을 보시면 알 수 있어요.

하지만 같은 조합이 여러 번 나오면 안 됩니다. 즉, 중복인 조합은 무시해야 합니다.

그래서 중복 무시... Set을 쓰면 되지 않을까?

라고 생각했습니다.

그런데 이상하게 다음과 같은 DFS 코드를 실행했을 때 Set이 제대로 출력되지 않는 문제가 있었어요.

fun dfs(len: Int, combination: IntArray) {
        if (len == M) {
            answerSet.add(combination)
            return
        }
        for (i in arr.indices) {
            if (visited[i]) continue
            combination[len] = arr[i]
            visited[i] = true
            dfs(len + 1, combination)
            visited[i] = false
        }
    }

마지막에 넣은 IntArray만 띡 하나 출력하고 종료되었습니다.

IntArray를 제대로 저장하지 못하고 있는 것이죠.

엥 대체 왜?

이전 프로그래머스 - 후보키 문제를 설명하면서 동일성과 동등성에 대해 짧게 짚고 넘어갔던 적이 있었는데요.

프로그래머스 - Lv2. 후보키 Kotlin

코틀린이 전부 다 해주는 줄 알고 방심했던 저의 실수입니다.

선언형으로 코딩할 때는 어디까지 구현되어 있는지 잘 알아야 하는 것 같아요.

List<String>은 == 연산자로 동등성 검사를 해 주지만, IntArray의 ==는 동등성 검사가 아니라 동일성 검사를 해 주네요.

다른 primitive type array도 마찬가지입니다.

그래서 동등성 검사를 하는 함수가 따로 있습니다. contentEquals()입니다.

동일성과 동등성이 계속 걸리적거리네요.

다음에 kotlin 카테고리에 종합해서 포스팅하겠습니다.

---

+ 했습니다.

Kotlin의 Equality, == vs ===

---

그래서 결과적으로는?

최대 N이 8이기 때문에 깡 DFS로도 풀리긴 하더라고요.

나중에 리팩토링을 해야겠지만...

 

정답

fun main() = with(System.`in`.bufferedReader()) {
    var (N, M) = readLine().split(" ").map { it.toInt() }
    var arr = readLine().split(" ").map { it.toInt() }.toIntArray()
    arr.sort()

    var visited = BooleanArray(arr.size)
    var answerSet = mutableSetOf<List<Int>>()

    fun dfs(len: Int, combination: IntArray) {
        if (len == M) {
            answerSet.add(combination.toList())
            return
        }
        for (i in arr.indices) {
            if (visited[i]) continue
            combination[len] = arr[i]
            visited[i] = true
            dfs(len + 1, combination)
            visited[i] = false
        }
    }

    dfs(0, IntArray(M))

    answerSet.forEach {
        println(it.joinToString(" "))
    }
}