[BOJ] 15663 N과 M(9)(Java)

15663번: N과 M (9)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예제

입력

3 1
4 4 2

4 2
9 7 9 1

4 4
1 1 1 1

 

출력

2
4

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

1 1 1 1

 

풀이

접근

기존에 N과 M 시리즈에서 중복된 수열을 빼는 문제였다.

처음에 접근은 이전과 동일하게 N개 중에서 M개를 뽑고, 그에 해당 되는 String 값을 HashSet에 넣어 중복을 제거해주면 되지 않을까 했다.

그러나 Set에 들어갈때 어떠한 이유인지 순서가 바뀌면서 들어갔고, 출력이 다르게 나왔다.

자료를 찾아보니, HashSet이 순서가 보장되지 않아서 그런 것이였다. LinkedHashSet을 사용했으면 순서가 보장되어 처리가 잘 되었다.

아래는 매번 list를 돌면서 중복된게 있는지 확인하는 방법으로 푼 버전이고,
위에는 LinkedHashSet을 사용해 푼 버전이다. 확연한 시간차이가 보인다.

 

그래서 두 번째 방법으로 Set을 List로 변환하여 Collections.sort로 정렬하여 출력하였지만, String의 정렬은 int형 정렬과 달라서 값이 다르게 나오는 경우가 존재하였다.

 

마지막 방법으로 M개를 뽑아서 String answer로 만들때, 정답을 담아두는 List를 한번 돌면서 중복된게 있는 지 확인하고 중복된게 없다면 넣어주는 방식으로 수정하여 풀었다.

 

넣을 때 마다 List를 순회해야하므로 시간초과가 날까 걱정 했지만, N과 M의 범위를 보고 그냥 진행하여 풀었다.

코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj15663_N과M_9_ArrayList {
	static ArrayList<String> list;
	static boolean[] visited;

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];

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

		// end init

		list = new ArrayList<>();
		visited = new boolean[N];
		Arrays.sort(arr); // 사전 순으로 증가하는 순서로 출력하기 위해 정렬
		seq(0, M, "", arr);

		StringBuilder sb = new StringBuilder(); // sout을 한 번만 쓰기 위해 StringBuilder 사용

		for (String s: list)
			sb.append(s).append("\n");

		System.out.println(sb);
	}

	static void seq(int depth, int M, String answer, int[] arr) {
		if (depth == M) {
			String str = answer.trim(); // 결과가 될 String
			if (!list.contains(str)) // 현재 리스트에 중복된게 없다면 추가
				list.add(str);
			return;
		}

		for (int i = 0; i < arr.length; i++) {
			if(visited[i]) // 중복된 자기자신은 빼기 위해 방문 체크
				continue;

			visited[i] = true;
			seq(depth+1,M,answer + " " + arr[i], arr);
			visited[i] = false;
		}
	}
}

 

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class Boj15663_N과M_9_LinkedHashSet {
	static LinkedHashSet<String> lhs;
	static boolean[] visited;

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];

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

		// end init

		lhs = new LinkedHashSet<>();
		visited = new boolean[N];
		Arrays.sort(arr); // 사전 순으로 증가하는 순서로 출력하기 위해 정렬
		seq(0, M, "", arr);

		StringBuilder sb = new StringBuilder(); // sout을 한 번만 쓰기 위해 StringBuilder 사용

		for (String lh : lhs)
			sb.append(lh).append("\n");

		System.out.println(sb);
	}

	static void seq(int depth, int M, String answer, int[] arr) {
		if (depth == M) {
			lhs.add(answer.trim()); // 결과가 될 String
			return;
		}

		for (int i = 0; i < arr.length; i++) {
			if(visited[i]) // 중복된 자기자신은 빼기 위해 방문 체크
				continue;

			visited[i] = true;
			seq(depth+1,M,answer + " " + arr[i], arr);
			visited[i] = false;
		}
	}
}

배운점

1. 자료구조의 선택만으로도 시간을 많이 줄일 수 있다.
2. Set = 중복제거로만 알고있었는데, 어떤 Set을 쓰냐에 따라 삽입, 삭제, 순서 등 다양한 부분이 결정나니 항상 체크해가며 공부해야할 것 같다.