링크
https://www.acmicpc.net/problem/15663
문제 설명
정답률 49.256%
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열
입력 예제
- 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
4 2
9 7 9 1
출력 예제
-
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
-
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
1 7
1 9
7 1
7 9
9 1
9 7
9 9
풀이
기존의 N과 M 시리즈와 비슷하지만 1부터 N까지의 자연수가 아니라 N개의 자연수가 입력값으로 주어지고 자연수가 중복될 수도 있다. 그리고 중복된 수열은 한 번만 출력한다.
중복된 수열을 제외시키기 위해 HashSet을 이용하여 수열을 저장한다. 하지만 HashSet은 순서를 보장하지 않는 자료구조이므로 ArrayList로 변환하는 과정을 거친다. 이때 HashSet의 타입이 String이기 때문에 ArrayList도 String으로 한 뒤 정렬을 한다면 문제의 조건에 맞지 않게된다.
만약 다음과 입력이 주어진다면
3 2
10 10 9
그대로 Collections.sort() 메서드를 이용해 정렬한다면 다음과 같이 정렬된다. 숫자로 보면 10 > 9 이지만 문자열로 봤을 때 10이 아니라 1부터 생각하기 때문에 1 > 9 이 된다.
10 10
10 9
9 10
그래서 다음과 같이 int 배열로 변환하여 정렬한다.
List<int[]> list = new ArrayList<>();
for (String s : set) {
int[] array = Arrays.stream(s.split(" "))
.mapToInt(Integer::parseInt)
.toArray();
list.add(array);
}정렬은 람다를 이용하여 Comparator을 구현해준다.
list.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i] != o2[i]) {
return Integer.compare(o1[i], o2[i]);
}
}
return 0;
});코드
//백준
public class Main {
static int N;
static int M;
static int[] numbers;
static int[] arr;
static boolean[] visited;
static StringBuilder sb;
static HashSet<String> set;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //N개의 자연수
M = Integer.parseInt(st.nextToken()); //수열의 길이
arr = new int[M]; //수열을 담을 배열
visited = new boolean[N];
set = new HashSet<>();
//입력값 초기화
numbers = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
dfs(0);
//HashSet은 순서롤 보장하지 않기 때문에 정렬을 위한 ArrayList 생성
List<int[]> list = new ArrayList<>();
//set을 list로 변환
for (String s : set) {
int[] array = Arrays.stream(s.split(" "))
.mapToInt(Integer::parseInt)
.toArray();
list.add(array);
}
//list의 원소들의 같은 인덱스의 값들을 비교하여 오름차순으로 정렬
list.sort((o1, o2) -> {
for (int i = 0; i < o1.length; i++) {
if (o1[i] != o2[i]) {
return Integer.compare(o1[i], o2[i]);
}
}
//값이 같다면 그대로
return 0;
});
//대괄호 없이 출력
for (int[] ints : list) {
for (int anInt : ints) {
System.out.print(anInt + " ");
}
System.out.println();
}
}
static void dfs(int depth) {
//depth가 수열의 길이와 같을 때
if (depth == M) {
sb = new StringBuilder();
//arr을 문자열로 변환
for (int i = 0; i < arr.length - 1; i++) {
sb.append(arr[i]).append(" ");
}
sb.append(arr[arr.length - 1]);
//set에 저장
set.add(sb.toString());
return;
}
for (int i = 0; i < N; i++) {
//방문하지 않은 수일 때
if (!visited[i]) {
//방문 처리
visited[i] = true;
//해당 깊이의 배열로 할당
arr[depth] = numbers[i];
//depth를 추가하여 재귀 호출
dfs(depth + 1);
//다음 배열을 생성하기 위하여 미방문 처리
visited[i] = false;
}
}
}
}
백엔드