[Java] 15663번 : N과 M (9)

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

15663번: N과 M (9)

 

오늘도 새롭게 알아가는 자바의 심오한 세계!!!

 

처음 2번 틀린건 한 60프로정도,,,? 그리고 컴파일 에러 났던거는 C++로 제출해서이다,,,푸히ㅣ히ㅣ

문제는 N과M(3)에서 크게 달라지는건 없었지만, 중복제거가 고민을 좀 했어야했다!

 

HashMap도써보고,,,별짓다해봤지만 최고의 방법은 바로 이것!

https://adjh54.tistory.com/175#google_vignette

[Java/Short] 배열/리스트 중복제거 방법 : 전체, 인접한 요소 중복 제거

 

단, 이 한줄로 해결할 수 있었다! 

str = Arrays.stream(str).distinct().toArray();

 

자바가 어렵지만 생각보다 좋은게 많은듯 ㅎㅎ

이 부분만 잠깐 보면, 우선 str 배열을 초기화해주고! 순열 함수를 돌린 후에, 그 함수에서 나온 값에 대한 중복값을 처리하고 StringBuilder를 이용해서 출력해주면 시간초과없이 깔끔하게 나온다! 

Collections.sort(a);
Arrays.fill(str,"");
permutation(a, visited, output, 0, m);
str = Arrays.stream(str).distinct().toArray();
for(int i=0;i<str.length;i++) {
    sb.append(str[i]).append("\n");
}

 

처음에 static으로 배열을 우선 선언해두었다! 결과를 담을 배열을!

static int n, m;
static int cnt=0;
static StringBuilder sb = new StringBuilder();
static Object[] str = new String[100000004];

 

순열 함수를 살짝 바꿔서 값이 나올때마다 str 배열에 저장해두었다! 

public static void permutation(List<Integer> a, boolean visited[], int output[], int depth, int r) {

        if(depth==r) {
            for(int i=0;i<r;i++) {
                str[cnt] += (output[i]+" ");
            }
            cnt++;
            return;
        }

        for(int i=0;i< a.size();i++) {
            if(!visited[i]) {
                visited[i]=true;
                output[depth] = a.get(i);
                permutation(a, visited, output, depth + 1, r);
                visited[i]=false;
            }
        }

    }

 

그리고 visited 배열에 이미 체크한거는 true로 바꿔두어서 중복되지않도록 했다! 

 

[전체코드]

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

public class Main {

    static int n, m;
    static int cnt=0;
    static StringBuilder sb = new StringBuilder();
    static Object[] str = new String[100000004];

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

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        ArrayList<Integer> a = new ArrayList<>();
        int x;
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            x = Integer.parseInt(st.nextToken());
            a.add(x);
        }
        int output[] = new int[a.size()];
        boolean visited[] = new boolean[a.size()];
        Collections.sort(a);
        Arrays.fill(str,"");
        permutation(a, visited, output, 0, m);
        str = Arrays.stream(str).distinct().toArray();
        for(int i=0;i<str.length;i++) {
        	sb.append(str[i]).append("\n");
        }
        System.out.print(sb);
    }


    public static void permutation(List<Integer> a, boolean visited[], int output[], int depth, int r) {

        if(depth==r) {
            for(int i=0;i<r;i++) {
                str[cnt] += (output[i]+" ");
            }
            cnt++;
            return;
        }

        for(int i=0;i< a.size();i++) {
            if(!visited[i]) {
                visited[i]=true;
                output[depth] = a.get(i);
                permutation(a, visited, output, depth + 1, r);
                visited[i]=false;
            }
        }

    }

}