백준 15663 N과 M (9) 자바 풀이

난이도 : 실버2

풀이일 : 2403037

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

15663번: N과 M (9)

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import java.util.Scanner;
import java.util.Arrays;
import java.util.Set;
import java.util.LinkedHashSet;

public class Main {
	static int N, M;
	static int[] nums;
	static int[] result;
	static boolean visited[];
	static Set<String> set;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		nums = new int[N];
		result = new int[M];
		visited = new boolean[N];
		set = new LinkedHashSet<>();
		
		for (int i = 0; i < N; i++) {
			nums[i] = sc.nextInt();
		}
		
		Arrays.sort(nums);
		DFS(0);
		
		// set 요소들 순서대로 출력
		set.forEach(s -> System.out.println(s));
	}
	
	static void DFS(int depth) {
		// 현재 result 요소들을 set에 추가
		if (depth == M) {
			String temp = "";
			for (int i : result) {
				temp += i + " ";
			}
			set.add(temp);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				result[depth] = nums[i];
				visited[i] = true;
				DFS(depth + 1);
				visited[i] = false;
			}
		}
	}
}

• set : 중복되는 수열은 한 개만 출력해야 하지만 숫자는 중복된 숫자가 주어질 수 있으므로 set으로 중복 제거
• LinkedHashSet : Set 이지만 요소의 순서를 보장하는 형태
• visited로 중복된 자릿수의 숫자를 방문하지 않도록 설정
• StringBuilder에 추가하는 대신 Set에 추가 후 한꺼번에 출력
• set.forEach(s -> System.out.println(s)); : set에 있는 모든 요소들 순서대로 출력

---

느낀점

• 파이썬 알고리즘 문제를 한 시간 반동안 풀어내지 못하여 급하게 자바 문제를 풀이했다. 좋게 말하면 유형뽀개기, 나쁘게 말하면 날로먹기도 얼마 남지 않았는지 조금 어려워졌다. 이 정도 되면 유형뽀개기라고 해도 될 듯.
• 그리고 미뤄왔던 자료구조 공부도 포스팅해봐야지 목표는 매 주 한 개 포스팅 하기