이것저것 개발 블로그

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

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main_BJ_15663_N과M9 {
    static HashMap<String, Integer> map = new HashMap<>();
    static int[] ans, arr;
    static boolean[] visited;
    static int n, m;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];

        for(int i=0; i<n; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        ans = new int[m];
        visited = new boolean[n];
        Arrays.sort(arr);
        perm(0);
//        System.out.println(map.keySet());
    }//main
    private static void perm(int cnt){
        if(cnt == m){
            String str = "";
            for(int i=0; i<m; i++)
                str += ans[i] + " ";

            if(!map.containsKey(str)) {
                map.put(str, 1);
                for (int i = 0; i < m; i++) {
                    System.out.print(ans[i] + " ");
                }
                System.out.println();
            }
            return;
        }

        for(int i=0; i<n; i++){
            if(visited[i])
                continue;
            visited[i] = true;
            ans[cnt] = arr[i];
            perm(cnt+1);
            visited[i] = false;
        }
    }//perm
}

반례 찾다가 간단하지만 어이없게 해결한 문제...

일단, 만든 수열이 중복되는지 확인하기 위해 HashMap을 이용해 key로 저장해뒀다.

이때, key는 수열을 string으로 만든것!!

이때 주의할 점이 있다.

띄어쓰기를 꼭 할 것...!

안 했더니 틀렸다...ㅋㅋㅋㅋ

// 반례
4 2
1 11 11 111


//정답
1 11 
1 111 
11 1 
11 11 
11 111 
111 1 
111 11

다른 풀이를 보니 Set을 이용하기도 하고, 이전 값을 저장해서 중복되는지 확인하는 방법도 있었다.

참고하면 좋을듯!!

아, 그리고 ArrayList로 저장해서 contains를 이용하면 시간 초과가 나오니 주의할것!!