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

 

관련글

 

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

관련 문제인 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)은 여기를 참조
관련 문제인 N과 M(10)은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

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

 

 

2. 풀이

 

이전의 N과 M(9)와 N과 M(10)에서 사용했던 중복된 수가 몇 번 나오는지 센다. 그 후 그 숫자가 1회 이상 중복되는 숫자라면 같은 수를 M개 여러 개 골라 출력할 수 있도록 한다.

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

 

이전 N과 M(7)에서 사용한 로직을 동일하게 사용하되, 중복된 수가 1회 이상 나오는 경우에만 적용하면 된다.

 

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);
        
        System.out.println(sb);
        br.close();
    }
    
    private static void go(int seq){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i=0; i < n; i++){
            // 현재 중복된 숫자를 사용할 수 있는 것이 0개 초과라면
            if(count[i] > 0){
                selected[seq] = unique[i];
                go(seq+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 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];
        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);
        
        // LinkedHashSet에 저장된 내역을 출력
        ans.forEach(System.out::println);
        br.close();
    }
    
    private static void go(int seq){
        if(seq == m){
            StringBuilder sb = new StringBuilder();
            for(int i : selected){
                sb.append(i).append(" ");
            }
            // sb 객체를 LinkedHashSet에 넣어 중복되는 경우는 제외 시킴
            ans.add(sb.toString());
            return;
        }
        
        // N과 M(3), N과 M(7)과 동일한 로직 사용
        for(int i=0; i < n; i++){
            selected[seq] = nums[i];
            go(seq+1);
        }
    }
}

 

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