[백준, 15650] N과 M (2) (백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

접근 방식

이번 "백준 - N과 M(2)" 문제는 다음의 조건을 만족하는 수열을 출력하는 문제입니다. 

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

[백준, 15649번] N과 M(1) (백트래킹, Java)

 

위 N과 M (1)문제와 다른 점은 오름차순이라는 점입니다.

 

순열 문제로, 순서를 고려하여 모든 경우를 출력합니다. 따라서 아래와 같은 결과가 나옵니다.

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

조합 문제로, 선택한 숫자들이 항상 오름차순이어야 하며, 순서를 고려하지 않습니다. 즉, 1 2와 2 1은 같은 조합으로 간주됩니다. 따라서 결과는 다음과 같습니다.

 

1 2
1 3
1 4
2 3
2 4
3 4

 

전체 코드

 

getPermutation() : 수열 함수

 

먼저 매개변수는 start: 현재 수열에서 시작할 시작점(숫자), end: 수열에서 사용할 수 있는 가장 큰 수(N), idx: 현재 수열의 몇 번째 자리를 채우고 있는지 나타내는 인덱스입니다.

 

그리고 재귀를 사용하여 수열을 계속 구해줄 것이기 때문에 탈출조건을 정해줘야합니다.

 

탈출조건은 idx가 permutation의 길이(M)와 같아질 때입니다. 이는 M개의 숫자를 모두 골랐다는 의미이고, 이때 현재까지 만들어진 수열을 StringBuilder에 저장합니다.

 

탈출조건이 만족되지 않았다면, start부터 end까지의 숫자를 현재 위치(idx)에 하나씩 넣어보면서 수열을 만들어갑니다.

 

이때 중요한 점은 다음 재귀 호출에서 start를 현재 선택한 숫자보다 1 크게(num + 1) 설정함으로써, 항상 이전에 선택한 수보다 큰 수가 선택되도록 보장한다는 것입니다.

 

1. arr[0]=1 설정 후
   arr[1]=2 -> [1,2] 출력
   arr[1]=3 -> [1,3] 출력
   arr[1]=4 -> [1,4] 출력

2. arr[0]=2로 변경 후
   arr[1]=3 -> [2,3] 출력
   arr[1]=4 -> [2,4] 출력

3. arr[0]=3으로 변경 후
   arr[1]=4 -> [3,4] 출력

 

이렇게 하나의 배열을 계속 재사용하면서

1. 첫 번째 자리(arr[0])의 값을 정하고
2. 두 번째 자리(arr[1])의 값을 바꿔가며 모든 경우를 만들고
3. 다시 첫 번째 자리 값을 바꾸고
4. 다시 두 번째 자리 값을 바꿔가는...

이런 식으로 재귀적으로 진행되면서 모든 조합을 만들어내는 것입니다.