백준 15649) N과 M (1)

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

15649번: N과 M (1)

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

 

 

---

 

시간 복잡도

 

 

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까지 돌리므로 시간복잡도는 O(N)이다.

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

 

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

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

 

 

 

접근 방법

 

 

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

 

 

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

 

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

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

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

 

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

 

 

 

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

 

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

 

go(idx+1, n, m)

 

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

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

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

 

 

 

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

 

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

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

 

 

 

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

 

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

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

 

 

 

 

코드

 

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

    print(sb)
}

private fun go(idx : Int, n : Int, m : Int) {
    if(idx==m) {
        arr.forEach { sb.append(it).append(' ') }
        sb.append("\n")
        return
    }
    for(i in 1..n) {
        if(check[i]) continue
        check[i] = true
        arr[idx] = i
        go(idx+1, n,m)
        check[i] = false
    }
}