백준 15650) N과 M (2)

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

15650번: N과 M (2)

문제

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

 

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

 

---

 

시간 복잡도

 

 

N과 M (1) 의 중복을 허용하지 않는 조건에 하나의 조건의 더 추가된 문제다.

오름차순을 지켜야 하는 조건이 추가됐다.

 

N, M 모두 1-8 까지의 범위를 갖고 중복을 허용하지 않는 조건이 있다.

첫 번째 위치에서 1-N 가운데 3을 골랐다면

두 번째 위치에서는 1-N 가운데 3을 제외한 나머지 수를 골라야 한다.

 

즉 1-N 중에서 앞에 사용하지 않은 수를 M만큼 뽑아간다는 의미이다.

 

1) 1-N 중에서 1을 골랐을 시 : N

2) 1-N 중에서 1을 제외하고 2를 골랐을 시 : N-1

3) 1-N 중에서 1,2를 제외하고 3을 골랐을 시 : N-2

...

 

모든 경우의 수를 곱하게 되면 시간복잡도는 O(N!) 이 된다.

 

여기서 for문으로 1-N까지 돌리지 않고, 오름차순을 지켜야 하므로 start 라는 매개변수를 설정해서

반복문을 돌릴 때마다 start에 1씩 추가한다. 그렇다면 start-N 반복문의 시간복잡도는 O(N)이다.

결국 O(N) * O(N!) = O(N * N!) 이 총 시간복잡도가 된다.

문제의 제한 시간은 1초이고 데이터의 크기가 1억정도일 때 1초라고 한다면

8 * 8! = 322560 으로 주어진 시간 내에 충분히 해결할 수 있다.

 

 

 

접근 방법

 

 

• ans : IntArray - 가능한 경우를 저장하는 배열
• check : BooleanArray - 중복 여부를 검사하는 배열
• go : Function - 재귀 호출할 함수

 

1. 재귀 함수를 구현하기 위해 매개 변수를 정한다.

 

조건을 만족하면 증가하는 변수 : idx

오름차순을 위해 시작점이 1씩 증가하는 변수 : start,

idx==m 일 때 return 해야 함 : m

1부터 N까지의 수를 구해야 함 : n

 

go(idx : Int, n : Int, m : Int)

 

 

 

2. 다음 경우를 호출하는 방법을 고려한다.

 

중복을 허용하지 않기 때문에 BooleanArray로 체크해서 해당 값이 true라면 넘어가고, false이면 중복이 아니므로 IntArray에 저장한다.

 

1-N까지 반복문을 돌릴 때 2->1로 가지 않고 2->3 으로 가기 위해 i+1을 매개변수로 넘겨준다.

 

go(idx+1, i+1, n, m)

 

여기서 중요한 점은 함수 호출 이전에 true로 설정했으면

함수 호출 이후에 false로 설정해야 한다.

그래야 중복을 피할 수 있기 때문이다.

 

 

 

3. 조건을 만족하는 경우를 고려한다.

 

idx와 m이 동일할 때 m개의 순열을 출력할 수 있으므로

if(idx==m) 조건에 도달하게 될 경우, arr 배열에 저장했던 값들을 출력하면 된다.

 

 

 

4. 불가능한 경우를 고려한다.

 

중복을 피하는 조건으로 if(check[i]) 을 검사해서

만약 true라면 이미 사용한 수이므로 continue 시킨다.

 

 

 

코드

 

lateinit var check: BooleanArray
lateinit var ans: IntArray
val sb = StringBuilder()
fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    check = BooleanArray(n + 1)
    ans = IntArray(m)
    go(0, 1, n, m)
    println(sb)
}

private fun go(idx: Int, start : Int, n: Int, m: Int) {
    if (idx == m) {
        ans.forEach { sb.append(it).append(' ') }
        sb.append("\n")
        return
    }

    for (i in start..n) {
        if (check[i]) continue
        check[i] = true
        ans[idx] = i
        go(idx + 1, i + 1, n, m)
        check[i] = false
    }
}