공부 160일차: 백준 15663번 N과 M (9) 자바 java

15663 N과 M (9)

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

15663번: N과 M (9)

 

 

 

 

 

---

백준 15663번 문제 N과 M (9)

---

문제

---

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/295

공부 156일차: 백준 15654번 N과 M (5) 자바 java

이 문제를 기반으로 한다

 

위의 문제와 같은 코드로는

4 4

1 1 1 1을 입력하면 이렇게 나오는 것을,

1 1 1 1

예제 출력처럼 뽑아내야 한다

 

결국 중복된 수열을 없애야 하는데,

https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-15663%EB%B2%88-N%EA%B3%BC-M-9-java

이 블로그가 도움이 많이 됐다

 

before라는 정수 변수를 두어, 다음으로 들어갈 값이 이 before와 같다면 수열에 넣지 않는 방법이다

(중복을 허용하지 않는 Set을 이용한 분들도 많았다)

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[] arr, nums;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
    
    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());
        arr = new int[m];
        nums = new int[n];
        visited = new boolean[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        
        DFS(0);
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) throws IOException {
        if(depth == m) {
            for(int val : arr) {
                bw.write(val+" ");
            }
            bw.newLine();
            return;
        }
        
        int before = 0;
        for(int i = 0; i < n; i++) {
            if(visited[i]) {
                continue;
            }
            
            if(before != nums[i]){    
                visited[i] = true;
                arr[depth] = nums[i];
                before = nums[i];
                DFS(depth+1);
                visited[i] = false;
            }
        }
    }
}

 

N과 M의 모든 문제가 큰 변화가 없는 편이지만, 이 문제는 다른 문제에 비해 정답률이 낮은 편이다

 

 

 

---