알고리즘 풀이 - 백준 15664(N과 M(10), 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조
백트래킹 관련 포스팅은 여기를 참조

관련 문제인 N과 M(1)은 여기를 참조
관련 문제인 N과 M(2)는 여기를 참조
관련 문제인 N과 M(3)은 여기를 참조
관련 문제인 N과 M(4)는 여기를 참조
관련 문제인 N과 M(5)는 여기를 참조
관련 문제인 N과 M(6)는 여기를 참조
관련 문제인 N과 M(7)는 여기를 참조
관련 문제인 N과 M(8)은 여기를 참조
관련 문제인 N과 M(9)은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이 문제는 이전 N과 M(2)와 N과 M(6)과 유사한데, 1은 1~N, 5는 10,000 이하의 서로 다른 N개의 자연수가 주어졌다.

하지만 N과 M(10)는 10,000이하의 임의의 자연수가 주어진다.(즉, 동일한 숫자가 여러 개 주어질 수 있다.)

 

 

2. 풀이

 

이전의 N과 M(9)에서 사용했던 중복된 수가 몇 번 나오는지 세고, 그 내용을 통해 비 내림차순으로만 설정하면 된다.

우선 각 중복된 수가 몇 번 나오는지 판단 후, 중복이 없는 숫자의 배열을 만들어 그 배열 안에서 반복 / 재귀를 통해 문제를 해결할 수 있도록 한다.

그리고, 비 내림차순이라는 것은 이후 숫자가 현재보다 크거나 같아야 하므로, 다음 재귀를 통해 수행 시에는 현재의 index번째의 숫자부터 시작한다.

이전 N과 M(6)에선 중복되는 숫자가 없어서 다음 index를 넘겼는데, 이 문제는 중복이 있을 수 있어서 현재 index를 넘기면 된다.

 

2가지 방법을 사용해볼 수 있다.

① 각 숫자가 몇 번 나오는지 세고 출력되는 경우의 수를 조정
② LinkedHashSet을 이용하여 Set을 사용해 중복되는 경우를 제거

 

아래 3-1에서는 ①의 방법을 사용하여 풀어본다.

3-2에서는 ②의 방법을 사용해 풀어본다.

 

코드를 보면 이해할 수 있다.

 

 

3-1. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int m;
    static int[] nums;     // 주어지는 숫자를 저장
    static int[] unique;   // 중복되는 숫자를 빼고 고유 숫자들만 저장
    static int[] selected; // m개를 선택하는 배열
    static int[] count;    // 중복되는 숫자가 몇 번 나오는지 저장
    static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        nums = new int[n];
        unique = new int[n];
        selected = new int[m];
        count = new int[n];
        
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        
        // 숫자를 미리 정렬시킴
        Arrays.sort(nums);
        
        // 각 숫자를 중복된 개수를 세고 고유 숫자만 따로 저장한다.
        unique = new int[n];
        int current = nums[0];
        int k = 0;
        int cnt = 1;
        for(int i=1; i < n; i++){
            if(nums[i] == current){
                cnt++;
            } else {
                count[k] = cnt;
                unique[k] = current;
                k++;
                cnt = 1;
                current = nums[i];
            }
        }
        count[k] = cnt;
        unique[k] = current;
        go(0, 0);
        
        System.out.println(sb);
        br.close();
    }
    
    private static void go(int seq, int idx){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i=idx; i < n; i++){
            // 현재 중복된 숫자를 사용할 수 있는 것이 0개 초과라면
            if(count[i] > 0){
                count[i] -= 1;
                selected[seq] = unique[i];
                
                // 현재의 index를 넘겨야 함. 그래야 중복인 경우도 체크 가능
                go(seq+1, i);
                count[i] += 1;
            }
        }
    }
}

 

 

3-2. 코드(LinkedHashSet)

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedHashSet;

public class Main{
    static int n;
    static int m;
    static int[] nums;      // 주어지는 숫자를 저장
    static int[] selected;  // m개를 선택하는 배열
    static boolean[] check; // 방문 여부 판단하는 배열
    static LinkedHashSet<String> ans;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        nums = new int[n];
        selected = new int[m];
        check = new boolean[n];
        ans = new LinkedHashSet<>();
        
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        
        // 숫자를 미리 정렬시킴
        Arrays.sort(nums);
        go(0, 0);
        
        // LinkedHashSet에 저장된 내역을 출력
        ans.forEach(System.out::println);
        br.close();
    }
    
    private static void go(int seq, int idx){
        if(seq == m){
            StringBuilder sb = new StringBuilder();
            for(int i : selected){
                sb.append(i).append(" ");
            }
            // sb 객체를 LinkedHashSet에 넣어 중복되는 경우는 제외 시킴
            ans.add(sb.toString());
            return;
        }
        
        // N과 M(2), N과 M(6)과 동일한 로직 사용
        for(int i=idx; i < n; i++){
            if(check[i]) continue;
            check[i] = true;
            selected[seq] = nums[i];
            
            // 여기서는 별도로 중복 배열에 대한 처리를 하지 않았으니 다음 index를 넘겨야 함
            go(seq+1, i+1);
            check[i] = false;
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.