[BOJ]15666 N과 M(12).java
1.문제
2.코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* Author : YoungSeo Jeon
* Date : 2021-09-13
* Description : 백준 15666
*/
public class Main{
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int M, N ;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
arr = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++)
arr[i] = Integer.parseInt(st.nextToken());
//정렬
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
permutation(sb,0,0);
bw.flush();
br.close();
bw.close();
}
public static void permutation(StringBuilder sb,int n,int curr) throws IOException {
if(n == N) {
bw.write(sb.substring(0,sb.length()-1)+"\n");
return ;
}
for(int i=curr; i<M; i++) {
if(i>=1&& (arr[i]==arr[i-1])) continue;
//끝 원소보다 작은게 오면 순열에 넣지 않는다.
if(i>=1 && sb.lastIndexOf(" ")!=-1) {
sb.setLength(sb.length()-1);
int temp = Integer.parseInt(sb.substring(sb.lastIndexOf(" ")+1));
sb.append(" ");
if(temp>arr[i]) continue;
}
sb.append(arr[i]+" ");
permutation(sb,n+1,curr);
sb.setLength(sb.length()-1);
if(sb.lastIndexOf(" ")!=-1) {
sb.setLength(sb.lastIndexOf(" "));
sb.append(" ");
}else {
sb.setLength(0);
}
curr++;
}
}
}
3.Review
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* Author : YoungSeo Jeon
* Date : 2021-09-13
* Description : 백준 15666
*/
public class Main{
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int M, N ;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
arr = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++)
arr[i] = Integer.parseInt(st.nextToken());
//정렬
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
permutation(sb,0,0);
bw.flush();
br.close();
bw.close();
}
public static void permutation(StringBuilder sb,int n,int curr) throws IOException {
if(n == N) {
bw.write(sb.substring(0,sb.length()-1)+"\n");
return ;
}
for(int i=curr; i<M; i++) {
if(i>=1&& (arr[i]==arr[i-1])) continue;
//끝 원소보다 작은게 오면 순열에 넣지 않는다.
if(i>=1 && sb.lastIndexOf(" ")!=-1) {
sb.setLength(sb.length()-1);
int temp = Integer.parseInt(sb.substring(sb.lastIndexOf(" ")+1));
sb.append(" ");
if(temp>arr[i]) continue;
}
sb.append(arr[i]+" ");
permutation(sb,n+1,curr);
sb.setLength(sb.length()-1);
if(sb.lastIndexOf(" ")!=-1) {
sb.setLength(sb.lastIndexOf(" "));
sb.append(" ");
}else {
sb.setLength(0);
}
curr++;
}
}
}
분명 한번에 성공했다 생각했는데 조건이 하나 빠져있었다.
오름차순으로 모두 정렬되는것이 중요한것 같다.
이 문제 역시 전 문제를 고쳐서 만들었다.
Author And Source
이 문제에 관하여([BOJ]15666 N과 M(12).java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hakka_ame/BOJ15666-N과-M12.java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)