백준 15663 N과 M (9)
1. 문제 링크
2. 풀이
- 중복값이 포함된 Input을 배열로 받아 정렬하는 로직이 추가되었다.
- 문제의 조건대로 정렬을 한 뒤, before 변수를 사용하여 현재 재귀의 for문에서 이전에 선택된 값을 선택하지 않도록 했다.
- 이후에는 일반적인 순열 로직을 적용하여, 중복값을 피하기 위해 visit을 체크한다.
- Input에 따라 Output 양이 많아져서, StringBuilder를 사용하여 시간을 줄일 수 있다.
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N, M;
static int[] nums;
static int[] candidate;
static boolean[] visit;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nm = br.readLine().split(" ");
N = Integer.parseInt(nm[0]);
M = Integer.parseInt(nm[1]);
nums = new int[N];
visit = new boolean[N];
candidate = new int[M];
String[] line = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
nums[i] = Integer.parseInt(line[i]);
}
Arrays.sort(nums);
permutation(0);
System.out.print(sb);
}
static void permutation(int depth) {
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(candidate[i]).append(" ");
}
sb.append("\n");
return;
}
/**
* nums가 정렬되어있기 때문에 가능한 일이다.
* nums = {1, 1, 7, 9} 로 정렬되어있다고 가정해본다.
* for문에서 현재(i) 선택된 값을 before에 저장 후, 다음 반복에서 접근하는 값(i + 1)과 비교한다.
* 따라서 0번째 1이 선택되면 1번째 1은 넘어가게 된다.
* before가 없다면 (1, 7) (1, 9)가 두 번씩 나오게 된다.
*/
int before = -1;
for (int i = 0; i < N; i++) {
if (!visit[i] && before != nums[i]) {
visit[i] = true;
candidate[depth] = nums[i];
before = nums[i];
permutation(depth + 1);
visit[i] = false;
}
}
}
}
4. 채점 결과
5. 느낀 점
- 처음에는 HashSet<Integer []> 에 나오는 모든 배열을 저장하면서, 현재 set에 동일한 배열이 있는지 비교했다.
- 하지만 이는 시간이 너무 오래 걸렸고, before 변수를 사용해 이전 반복에서 사용한 값을 제외시켰다.
- Output이 많은 경우, StringBuilder를 적극 활용하자
Author And Source
이 문제에 관하여(백준 15663 N과 M (9)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gan/백준-15663-N과-M-9저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)