[백준] 15663번

사이트

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

15663번: N과 M (9)

 

문제 

 

분석

뭔가 간단하면서 조금 헷갈린 문제였다. 

먼저 입력이 아래와 같으면 

4 2
9 7 9 1

 

출력이 아래와 같이 나와야된다. 

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

즉 중복되는 것만 빼면 된다. 중복을 안빼면 

1 7 

1 9

1 9

이렇게 2개의 1 9가 나오는 것이다. 

 

그래서 필자는 가장먼저 Set을 생각했다. 

 

if (depth == m) {
    StringBuilder sb = new StringBuilder();
    for (int a : result) {
        sb.append(a).append(" ");
    }
    set.add(sb.toString().trim());
    return 0;
}

 

위와 같이 깊이가 M(길이)이랑 맞아떨어지면 if문으로 들어와 

StringBuilder를 통해 result 배열의 정수들을 문자열 바꿔 쭉 들어오게 한다. 

이때 띄어쓰기 해서 출력해야하므로 " "  도 추가!! 

 

그 후 set.add해서 sb를 추가하면 되는데 trim을 추가해서 앞뒤 공백을 지워준다. 

 

그러면 끝!! 사실상 set이 중복 문자열을 제거해줘서 원하는 결과를 이끌어낼 수 있다. 

 

 

전체 코드

package backtracking;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Back15663 {

    static int n;

    static int m;
    static int[] result;

    static int[] num;

    static boolean[] visit;

    static BufferedWriter bw;

    static Set<String> set;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        num = new int[n];
        result = new int[m];
        visit = new boolean[n];
        set = new LinkedHashSet<>();

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

        Arrays.sort(num);

        backTracking(0);

        for (String s : set) {
            System.out.println(s);
        }
    }

    private static int backTracking(int depth) {
        if (depth == m) {
            StringBuilder sb = new StringBuilder();
            for (int a : result) {
                sb.append(a).append(" ");
            }
            set.add(sb.toString().trim());
            return 0;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                result[depth] = num[i];
                backTracking(depth + 1);
                visit[i] = false;
            }
        }
        return 1;
    }
}

 

 

결과

느낀점

살짝 헷갈린 문제였다!! set 함수에 대해서 더 자세히 알아가는 문제가 되었다.