728x90
오답 노트 & 새로 알게 된 점
해당 문제는 전에 풀었던 카드 놓기와 비슷하지만, 카드 놓기는 중복을 제외한 순열이었다면, 이번 문제는 중복 가능한 순열이다. 그래서 if(visit[i]) continue 구문만 빼준다면 중복 가능한 순열이 된다.
똑같은 방식으로 String형으로 set에 중복 가능한 순열들을 모아놓은 뒤에 list에 Integer형으로 변환하여 저장한다. 그리고 max값을 지정하여 if 조건식을 만족하게 한 뒤 max 값을 출력하면 된다.
하지만 여기서 중요한 부분이 있다. 위와 같이 풀면 perm1만을 포함하는데, 여기서 반례가 생긴다.
14 2
7 8
을 하게 되면, N은 두자리 숫자인데 값은 8이 나와야 한다. 반례가 생기는 것이다. 그래서 perm2라는 메소드를 새로 만들어 N의 숫자 자릿수 - 1을 만족하는 중복순열도 만들어준다. 그래서 perm1, perm2를 실행한 뒤 max 값을 구하면 AC가 나온다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
package BruteForce_Search;
import java.util.*;
import java.io.*;
public class Main {
static int atoi(String str){
return Integer.parseInt(str);
}
static String arr[];
static boolean visit[];
static Set<String> set = new HashSet<>();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<Integer> al = new ArrayList<>();
String sstr = st.nextToken(); //숫자의 길이를 알기 위해 먼저 String으로 받음
int N = atoi(sstr);
int K = atoi(st.nextToken());
arr = new String[K];
visit = new boolean[K];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < K; i++){
arr[i] = st.nextToken();
}
///////////////////////////////////////////////////////입력 끝
perm1("", 0, sstr.length());
perm2("", 0, sstr.length() - 1);
for(String ss : set){
al.add(atoi(ss));
}
int max = Integer.MIN_VALUE;
for(int i = 0; i < al.size(); i++){
int value = al.get(i);
if(value >= max && value <= N) max = value;
}
System.out.print(max);
}
//같은 자리 숫자일 때
static void perm1(String str, int count, int limit){
if(limit == count){
set.add(str);
return;
}
for(int i = 0; i < arr.length; i++){
visit[i] = true;
perm1(str + arr[i], count + 1, limit);
visit[i] = false;
}
}
// 자리 수 - 1 까지 해줘야함.
static void perm2(String str, int count, int limit){
if(limit == count){
set.add(str);
return;
}
for(int i = 0; i < arr.length; i++){
visit[i] = true;
perm2(str + arr[i], count + 1, limit);
visit[i] = false;
}
}
}
|
cs |
728x90
'BOJ(Java)' 카테고리의 다른 글
자바(백준) 13565 침투 (0) | 2021.07.03 |
---|---|
자바(백준) 14501 퇴사 (0) | 2021.07.02 |
자바(백준) 5568 카드 놓기 (0) | 2021.07.01 |
자바(백준) 13164 행복 유치원 (0) | 2021.07.01 |
자바(백준) 20365 블로그2 (0) | 2021.06.30 |