[BOJ] 15663 N과 M (9) - JAVA

1. 문제

15663번: N과 M (9)

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

 

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

 

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

---

2. 풀이

static 변수

int[] arr	입력받은 전체 숫자들
int[] picked	뽑은 숫자
int N,M	주어진 수
StringBuilder sb	답으로 출력할 문자열

 

Main

3부분으로 나눠서 보면 된다.

1) 문제 입력값 저장하기

N,M,arr에 값을 저장하고 arr은 정렬한다. 중복을 거르기 위해서 필요하다.

 

2) 순열 함수 호출하기

picked 배열을 미리 만든 후 pick(0,0)을 호출한다.

 

3) 출력하기

모은 문자열을 한 번에 출력한다.

public static void main(String[] args) throws IOException {
   //1)
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   M = Integer.parseInt(st.nextToken());

   arr = new int[N];
   st = new StringTokenizer(in.readLine());
   for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
   Arrays.sort(arr);

   //2)
   picked = new int[M];
   pick(0,0);

   //3)
   System.out.print(sb);
}

 

순열

뽑았는지 여부는 flag 변수, 뽑힌 순서대로 저장된 객체는 picked다.

M개 뽑았을 때 picked에 저장된 순서대로 sb에 더하고 끝낸다.

 

입력으로 주어지는 수는 모두 자연수이기 때문에 before을 0으로 두고 시작한다.

만약 이미 뽑은 위치의 숫자이거나 이전 수와 동일한 숫자면 뽑지 않고 지나간다. 

cnt가 같은 상태에서(=같은 차례의 숫자를 뽑을 때) 동일한 숫자를 두 번 이상 뽑으면 그 이후의 과정이 모두 중복되기 때문이다.

picked[cnt]에 arr[i]를 저장하고 before을 arr[i]로 교체한다.

그 후 재귀호출한다.

public static void pick(int cnt, int flag){
   if(cnt==M){
      for(int i=0;i<M;i++){
         sb.append(picked[i]).append(' ');
      }
      sb.append('\n');
      return;
   }

   int before = 0;
   for(int i=0;i<N;i++){
      if((flag&1<<i)!=0 || before == arr[i]) continue;
      picked[cnt] = arr[i];
      before = arr[i];
      pick(cnt+1, flag|1<<i);
   }
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_15663_N과M9_2 {
   static int[] arr, picked;
   static int N,M;
   static StringBuilder sb = new StringBuilder();
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());

      arr = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(arr);

      picked = new int[M];
      pick(0,0);

      System.out.print(sb);
   }
   public static void pick(int cnt, int flag){
      if(cnt==M){
         for(int i=0;i<M;i++){
            sb.append(picked[i]).append(' ');
         }
         sb.append('\n');
         return;
      }

      int before = 0;
      for(int i=0;i<N;i++){
         if((flag&1<<i)!=0 || before == arr[i]) continue;
         picked[cnt] = arr[i];
         before = arr[i];
         pick(cnt+1, flag|1<<i);
      }
   }
}

---

3. 결과

TreeSet을 이용해서 한 번 풀었다가, 다른 사람이랑 시간, 메모리 차이가 너무 많이 나는 걸 보고 좀 참고해서 다시 풀었다. 그게 본문 풀이다! 1) 입력받은 배열을 정렬한 후 2) 뽑을 때 이전 수와 다른 걸 뽑으면 겹치지 않게 수열을 만들 수 있다.