[백준/Java] 15663 - N과 M (9)

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

문제

---

풀이

여태까지 N과 M 문제와 다르게 입력되는 수가 중복으로 주어진다

그래서 출력하는 배열도 중복으로 나올 수 있다

그 중복을 제거하는 것이 문제의 핵심이다

 

인덱스를 기준으로 방문처리를 하고 재귀 호출 하는 식으로 진행한다

하지만 이렇게 끝낸다면 출력되는 배열은 중복이 나온다

입력:

3 2

4 4 2

출력:

2 4

4 2

4 4

4 2

4 4

 

따라서 출력할 때 List 자료구조를 사용하여 리스트에 넣으려고 하는 값이 없을 때만 추가하면 중복을 제거할 수 있다

 

자세한건 코드를 보자

코드

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


public class Main {

	static int N, M;
	static int[] input; // 입력 배열
	static int[] arr; // 출력 배열
	static boolean[] visited; // 방문 여부

	static StringBuilder sb = new StringBuilder();
	static List<String> list = new ArrayList<>(); // 중복 제거용 리스트

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		input = new int[N];
		visited = new boolean[N];
		arr = new int[M];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		// 오름차순 정렬
		Arrays.sort(input);
		permu(0); // 인덱스 0부터 순회 시작

		for (String s : list) {
			sb.append(s);
		}
		System.out.println(sb);
		br.close();
	}

	static void permu(int idx) {
		if (idx == M) { // 인덱스가 M과 같아지면
			// tmp를 1 2\n 형태로 만들어준다
			StringBuilder tmp = new StringBuilder();
			for (int i = 0; i < M; i++) {
				tmp.append(arr[i]).append(" ");
			}
			tmp.append("\n");
			// 리스트에 존재하지 않으면 추가
			if (!list.contains(tmp.toString())) {
				list.add(tmp.toString());
			}
			return;
		}

		for (int i = 0; i < N; i++) {
			if(visited[i]) continue; // 이미 방문 했으면 continue
			visited[i] = true; // 방문 처리
			arr[idx] = input[i]; // 배열에 입력값 넣어줌
			permu(idx + 1); // idx 증가시키고 재귀 호출
			visited[i] = false; // 다음을 탐색을 위해 false 처리
		}
	}
}

결과