[Java] 15664번: N과 M(10)

🌎 Link : https://www.acmicpc.net/problem/15664

15664번: N과 M (10)

---

💡 접근 방법

1. 문제 이해

기존 N과 M시리즈 문제를 풀면서 어느 정도 백트레킹에 대한 감을 익히고 있다. 하지만 이 문제의 특징이 몇 가지가 있다.

1. 중복된 수열은 출력하지 마라
2. 수열은 사전순으로 출력해라
3. 고른 수열은 비내림차순이어야 한다(오름차순, 값이 같아도 된다)

2. 문제 풀이

• 중복된 수열은 출력하지 마라
  • 이를 해결하기 위해 자료구조 Set을 사용할 예정이다. 하지만 Set의 자료구조는 크게 세가지로 나뉘는데 각자의 특징이 있기 때문에 알맞은 자료구조를 선택해야 한다. 나는 중복을 허용하지 않고 입력한 순서대로 출력을 할 것이기 때문에 LinkedHashSet을 사용한다.
  • HashSet : 순서값을 보장하지 않는다.
  • TreeSet : 오름차순으로 정렬되 저장된다.
  • LinkedHashSet : 추가된 순서대로 저장이 된다.
• 수열은 사전순으로 출력해라
  • 정렬을 해서 해결한다.
• 고른 수열은 비내림차순이어야 한다(오름차순, 값이 같아도 된다)
  • int []을 복사해서 정렬 후 기존의 값이 다를 경우 false 같을 경우 true로 처리해서 해결한다.

---

🗝 풀이 코드

1차 풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static boolean[] isVisited;
    static int[] temp, store;
    static LinkedHashSet<String> answer;

    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());

        answer = new LinkedHashSet<>();
        temp = new int[M];
        isVisited = new boolean[N];
        store = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(store);

        backtracking(0);

        answer.forEach(System.out::println);
    }

    private static void backtracking(int depth) {
        if (depth == M) {
            if (!validate()) return;
            findAnswer();
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isVisited[i]) {
                temp[depth] = store[i];
                isVisited[i] = true;
                backtracking(depth + 1);
                isVisited[i] = false;
            }
        }
    }

    private static void findAnswer() {
        StringBuilder sb = new StringBuilder();
        for (int t : temp) {
            sb.append(t).append(" ");
        }

        answer.add(sb.toString());
    }

    private static boolean validate() {
        int[] copyTemp = temp.clone();
        Arrays.sort(copyTemp);

        return Arrays.equals(temp, copyTemp);
    }
}

 

문제는 해결했지만 다른 사람들은 어떻게 풀었는지 확인하다가 색다른 방법을 알게 됐다. 우선 나는 비내림차순을 구하기 위해 Arrays.equals()를 사용해서 구현을 했지만 기존에 Arrays.sort(stroe)로 정렬을 해준 상태를 활용하는 방법도 있었다. 또한 같은 인덱스의 접근을 막기 위해서 isVisited []를 활용했지만 이 부분도 함께 처리할 수 있었다.

 

예를 들어 1, 4, 7, 9면 정답은 (1-4, 1-7, 1-9, 4-7, 4-9, 7-9)로 출력이 된다. 여기서 포인트가 7(index 2)-1(index 0)과 같이 안 나오면 된다. backtracking의 매개변수를 기존 depth에 start를 추가를 해줘서 이를 for 반복문에서 시작 인덱스를 설정을 해주면 위와 같은 탐색은 실행되지 않는다. 또한 기존 정렬을 해줬기 때문에 따로 비내림차순을 검증할 필요도 없어진다.

2차 풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[] store, temp;
    static LinkedHashSet<String> answer;

    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());

        store = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(store);

        temp = new int[M];
        answer = new LinkedHashSet<>();

        backtrack(0, 0);

        answer.forEach(System.out::println);
    }

    private static void backtrack(int depth, int start) {
        if (depth == M) {
            addCombination();
            return;
        }

        for (int i = start; i < N; i++) {
            temp[depth] = store[i];
            backtrack(depth + 1, i + 1);
        }
    }

    private static void addCombination() {
        StringBuilder sb = new StringBuilder();
        for (int number : temp) {
            sb.append(number).append(" ");
        }
        answer.add(sb.toString());
    }
}