[백준]15663-N과 M(9) 문제 풀이(Java,자바)

문제

https://www.acmicpc.net/problem/15663

 

들어가며

이 문제는 N과 M(5)에서 수열에 중복된 숫자가 들어갈 수 있는 차이가 있다.

참고) N과 M(5) - https://namamim.tistory.com/60

따라서 위에서 사용한 코드를 기반으로 충분히 문제를 풀 수 있다.

 

이걸 해결하는데 크게 두 가지의 방식있다.

방식 1 - 순열을 다 만들고 중복 거르기

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 백준15664_N과M9 {
    static int n, m;
    static int[] nums;
    static int[] output;
    static boolean[] visited;
    static Set<String> set = new LinkedHashSet<>();
    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 = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        visited = new boolean[n];
        output = new int[m];
        Arrays.sort(nums);
        search(0);
        StringBuilder result = new StringBuilder();
        for (var i : set){
            result.append(i).append("\n");
        }
        System.out.println(result);
    }
    static void search(int depth){
        if (depth >= m){
            StringBuilder temp = new StringBuilder();
            for (int i = 0; i < m; i++){
                temp.append(output[i]).append(" ");
            }
            set.add(temp.toString());
            return;
        }
        for (int i = 0; i <n; i++){
            if (!visited[i]){
                visited[i] = true;
                output[depth] = nums[i];
                search(depth+1);
                visited[i] = false;
            }
        }
    }
}

풀이

아주 단순히 생각하면 모든 순열을 만들고 중복만 거르면 된다.

여기서 흔히 사용하는 것이 Set인데, Set은 중복은 거를 수 있으나 순서가 보장되지 않는다.

문제는 사전 정렬을 원하기 때문에 순서가 유지되어야 한다.

그럴 때 사용할 수 있는 것이 LinkedHashSet 이다.

입력 순서를 유지하기 때문에 성능은 좀 HashSet보다 안좋다.

하지만, 찬물 뜨거운 물 거를 때가 아니므로 사용하면 된다.

 

 

방식 2 - 순열을 만들 때 미리 거르기

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 백준15664_N과M9 {
    static int n, m;
    static int[] nums;
    static int[] output;
    static boolean[] visited;
    static StringBuilder result = new StringBuilder();

    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 = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        Arrays.sort(nums);
        output = new int[m];
        visited = new boolean[n];

        search(0);
        System.out.println(result);
    }

    static void search(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                result.append(output[i]).append(" ");
            }
            result.append("\n");
            return;
        }

        int lastUsed = -1;
        for (int i = 0; i < n; i++) {
            if (visited[i] || nums[i] == lastUsed) {
                continue;
            }

            visited[i] = true;
            output[depth] = nums[i];
            lastUsed = nums[i];
            search(depth + 1);
            visited[i] = false;
        }
    }
}

풀이

 

int lastUsed = -1;
for (int i = 0; i < n; i++) {
    if (visited[i] || nums[i] == lastUsed) {
        continue;
    }

    visited[i] = true;
    output[depth] = nums[i];
    lastUsed = nums[i];
    search(depth + 1);
    visited[i] = false;
}

이전과 다르게 lastUsed가 추가 됐다.

이전값을 저장한 것이다.

이미 수열을 사전으로 정렬했기 때문에, 같은 숫자들은 모여있다.

예시) 1,2,2,3,3,4

그렇기에 중복 처리는 이전 값이 지금이랑 같은 지만 파악하면 끝이난다.