[알고리즘/자바] 백준 N과 M(9)
문제링크 : https://www.acmicpc.net/problem/15663
체감 난이도 : 中
🤔풀이
- input() : (static) N, M, 입력받은 수열 arr, 방문 배열 visited을 초기화
- makeAnswers() : 재귀순열, arr에 있는 N개의 수들 중 M개를 선택했을 때 answers Set에 저장
- printAnswers() : answers Set의 answer들을 공백을 기준으로 split 하여 String배열로 만들고 그 배열들을 arrs 리스트로 collect → '사전 순으로 증가하는 순서'로 만들기 위해 Comparator 오버 라이딩
- Set 사용 : 중복되지 않는 수열을 만들기 위해서 set 사용
- Comparator 오버 라이딩 : 알아서 정렬되게 TreeSet 사용했더니 문자열이라 오름차순이 아닌 ex ) "11" < "6" 순으로 정렬함. (21%쯤에서 실패)
→ 직접 Comparator 오버 라이딩하는 방법 사용
- Comparator 로직 : o1배열(왼)텍스트과 o2배열(오)의 원소들을 순서대로 비교하다가 원소가 같지 않으면 그 원소의 대소 관계를 비교한다.
(return값 <= 0 이면 그대로, return값 > 0 이면 자리 변경)
📃작성코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ15663_N과M9 {
static FastReader scan = new FastReader();
static int N, M;
static String[] arr;
static boolean[] visited;
static Set<String> answers = new HashSet<>();
public static void main(String[] args) {
input();
makeAnswers(0, 0, visited, "");
printAnswers();
}
private static void printAnswers() {
List<String[]> arrs = answers.stream()
.map(str -> str.split(" "))
.collect(Collectors.toList());
Collections.sort(arrs, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
for (int i = 0; i < M; i++) {
if (!o1[i].equals(o2[i])) {
if (Integer.valueOf(o1[i]).compareTo(Integer.valueOf(o2[i])) < 0) {
return -1;
}
return 1;
}
}
return 0;
}
});
for (String[] arr : arrs) {
System.out.println(String.join(" ", arr));
}
}
static void makeAnswers(int dept, int choice, boolean[] visited, String str) {
if (dept == M) {
answers.add(str);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
String chosen = arr[i];
visited[i] = true;
makeAnswers(
dept + 1, choice + 1, visited, str.equals("") ? chosen : str + " " + chosen);
visited[i] = false;
}
}
}
static void input(){
N = scan.nextInt();
M = scan.nextInt();
arr = new String[N];
visited = new boolean[N];
Arrays.fill(visited, false);
for (int i = 0; i < N; i++) {
arr[i] = scan.next();
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
Author And Source
이 문제에 관하여([알고리즘/자바] 백준 N과 M(9)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@961210eee/알고리즘자바-백준-N과-M9
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- Set 사용 : 중복되지 않는 수열을 만들기 위해서 set 사용
- Comparator 오버 라이딩 : 알아서 정렬되게 TreeSet 사용했더니 문자열이라 오름차순이 아닌 ex ) "11" < "6" 순으로 정렬함. (21%쯤에서 실패)
→ 직접 Comparator 오버 라이딩하는 방법 사용 - Comparator 로직 : o1배열(왼)텍스트과 o2배열(오)의 원소들을 순서대로 비교하다가 원소가 같지 않으면 그 원소의 대소 관계를 비교한다.
(return값 <= 0 이면 그대로, return값 > 0 이면 자리 변경)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ15663_N과M9 {
static FastReader scan = new FastReader();
static int N, M;
static String[] arr;
static boolean[] visited;
static Set<String> answers = new HashSet<>();
public static void main(String[] args) {
input();
makeAnswers(0, 0, visited, "");
printAnswers();
}
private static void printAnswers() {
List<String[]> arrs = answers.stream()
.map(str -> str.split(" "))
.collect(Collectors.toList());
Collections.sort(arrs, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
for (int i = 0; i < M; i++) {
if (!o1[i].equals(o2[i])) {
if (Integer.valueOf(o1[i]).compareTo(Integer.valueOf(o2[i])) < 0) {
return -1;
}
return 1;
}
}
return 0;
}
});
for (String[] arr : arrs) {
System.out.println(String.join(" ", arr));
}
}
static void makeAnswers(int dept, int choice, boolean[] visited, String str) {
if (dept == M) {
answers.add(str);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
String chosen = arr[i];
visited[i] = true;
makeAnswers(
dept + 1, choice + 1, visited, str.equals("") ? chosen : str + " " + chosen);
visited[i] = false;
}
}
}
static void input(){
N = scan.nextInt();
M = scan.nextInt();
arr = new String[N];
visited = new boolean[N];
Arrays.fill(visited, false);
for (int i = 0; i < N; i++) {
arr[i] = scan.next();
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
Author And Source
이 문제에 관하여([알고리즘/자바] 백준 N과 M(9)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@961210eee/알고리즘자바-백준-N과-M9저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)