[백준 알고리즘(BOJ)] 15663번 N과M (9) 자바(java) 풀이 (LinkedHashSet 이용)

안녕하세요 호호만두에요

이번에는 N과M 시리즈중 하나인 BOJ 15663번 N과M 9번째 문제 풀어 봅시다!!

우선 N과M 9번째 문제에 앞서서 다른 N과M 문제를 전혀 풀지 않았다면

아래 글을 읽고 와주세요!!

N과M1번

BOJ N과 M(9) 링크

BOJ15663번 N과M9

이 문제도 역시 다른 N과 M 문제와 많이 비슷합니다

그냥 backtracking(백트래킹)으로 구해주면 되요

저는 이 문제도 1번 문제처럼 _순열_을 구하는 방식으로 풀었어요

주의 할 점

1. string을 sorting 하는 것은 숫자를 sorting 하는 것과 다르다

예를들어 입력이 아래와 같이 주어졌다고 합시다

2 2
9 10

그러면 순열을 뽑아서 넣고 sorting 하게 되면 다음과 같이 나옵니다

10 9
9 10

왜냐하면 10하고 9에서 1이 9보다 작기 때문에 더 앞 쪽에 오게 됩니다
이게 틀린 줄 모르고 엄청헤맸어요 ㅠㅠ

2. 두 자리수도 있다
   한 자리 수만 주어지는 것이 아니기 때문에 string으로 변환할때 구분자가 필요합니다
   아 물론 이 방식으로 푸는게 아니라면 필요 없을 수 있겠네요
   처음에 생각 못하고 풀다가 1번 틀렸네요...
   저는 그래서 string으로 변환할때 구분자로 '/'를 사용했습니다
   9 10 -> 9/10

문제 풀이

1. 우선 입력받은 값을 split을 통해 파싱하여 배열에 담습니다
2. 그리고 _오름차순_으로 sorting을 합니다
3. 그리고 이제 백트래킹을 재귀로 구현합니다

• 3.1 이때 구해진 순열 값은 깊이(depth)를 이용하여 output 배열에 임시로 저장합니다
  • 3.2 그리고 LinkedHashSet에 저장합니다

4. hash에 담아서 중복이 제거된 set을 배열로 변환합니다.
5. '/'을 기준으로 파싱하여 출력합니다.

BOJ 15663번 N과M(9) 자바(java) 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;

class Main{
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Set<String> hash;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        // 두번째 줄 입력받기
        String[] temp2 = br.readLine().split(" ");

        // 배열로 변환
        Integer[] arr = new Integer[n];

        // 값 배열에 저장
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(temp2[i]);
        }

        boolean[] visited = new boolean[n];
        String[] output = new String[m];

        hash = new LinkedHashSet<>();
        Arrays.sort(arr);
        permu(arr, output, visited, 0, n, m);

        // 반례 (string sort는 숫자와 다름)
        // 2 2
        // 9 10

        // 중복 제거된 순열을 배열로 변환
        String[] ans = hash.toArray(new String[hash.size()]);        


        for(int i=0; i<hash.size(); i++) {
            String[] temp3 = ans[i].split("/");
            for(int j=0; j<temp3.length; j++) {
                bw.write(temp3[j]);
                if(j != m-1)
                    bw.write(" ");
            }
            bw.newLine();
        }

        bw.flush();        
        br.close();
        bw.close();
    }

    public static void permu(Integer[] arr, String[] output, boolean[] visited, int depth, int n, int r) throws IOException {
        if(depth == r) {
            addHash(output, visited, r);
            return;
        }

        for(int i=0; i<n; i++) {
            if(!visited[i] ){
                visited[i] = true;
                output[depth] = arr[i].toString();
                permu(arr, output, visited, depth+1 , n, r);
                visited[i] = false;    
            }
        }
    }

    public static void addHash(String[] output, boolean[] visited, int r) {
        String str = "";

        for(int i=0; i<r; i++) {
            if(i != r-1)
                str += output[i] + "/";
            else
                str += output[i];
        }
        hash.add(str);
    }
}