[백준] 15652 : N과 M (5) - JAVA [자바]

안녕하세요.

오늘은 N과 M (5) 문제를 풀어보도록 하겠습니다.

 

📌 접근

N개의 수를 정수 배열에 저장하여 오름차순으로 정렬하고, (사전순으로 만들어야 하기 때문입니다.)

정렬한 배열에서 하나씩 중복없이 골라서 총  M개의 조합을 완성시키면 됩니다.

 

저는 dfs를 사용한 백트래킹을 이용하여 구현하였습니다.

(길이를 depth만큼 만들면 되기 때무네. . .🫠)

 

풀이에서 주의해야할 점은, 

dfs 재귀호출 전에는 visited = true로,

dfs 재귀호출 후에는 visited = false로 값을 넣어줘야 올바른 탐색을 할 수 있습니당.

 

💻 풀이

// hyeblee
import java.io.*;
import java.util.*;

public class Main {

  public final static int MAX_SIZE = 8;

  public static int N, M;
  public static int[] nums = new int[MAX_SIZE];
  public static boolean[] visited = new boolean[MAX_SIZE];
  public static StringBuilder result = new StringBuilder("");

  public static void dfs(int depth, String str) {
    if (depth == M) {
      result.append(str + "\n");
    }
    for (int i = 0; i < N; i++) {
      if (!visited[i]) {
        visited[i] = true;
        dfs(depth + 1, str + nums[i] + " ");
        visited[i] = false;
      }
    }
  }


  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    nums = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      nums[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(nums);
    dfs(0, "");
    System.out.println(result);
  }
}

 

🤔 고민했던 점 & 어려웠던 부분

 

첫 풀이에서 숫자를 문자열 배열로 정렬하여 올바르게 정렬되지 않았다.

나중에 result에 쓰기 쉽게 문자열 배열로 숫자를 받은 것이 문제였다.

 

1 -> 10 -> 3 ❌ (문자열 정렬)

1 -> 3 -> 10 ⭕(숫자 정렬)

 

int 배열 정렬과 String 배열 정렬은 다른 결과를 나타낸다 ❕