전체 탐색과 시뮬레이션의 차이
- 시뮬레이션은 수행해야 하는 과정이 모두 나와있는 문제
- 전체 탐색은 모든 패턴을 조사해야 하는 것과 그것을 필요로 하는 문제
전체 탐색의 형태로 다음과 같은 것이 있다.
- 모든 패턴을 찾고 가장 좋은 답을 찾는 것
- 모든 패턴을 찾고 조건을 충족하는 패턴이 몇 개인지 찾는 것
답이 같은 두 문제여도 어떠한 작업을 수행할지 적혀있으면 시뮬레이션 문제이고, 없으면 전체 탐색 문제이다.
5-1. 즐거운 파티
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
화이트씨는 다재다능한 사람입니다. 그래서 그에게는 친구가 많습니다. 하지만 불행하게도 그의 친구들은 다재다능하지 않습니다. 각각의 친구는 2가지 주제에만 관심이 있고 다른 주제로 이야기하는 것을 싫어합니다.
그래서 파티를 개최할 때마다 모두가 즐겁게 파티를 보내려면 어떤 친구를 초대할지가 큰 문제입니다. 화이트씨는 그 동안의 경험으로 초대된 친구 모두가 공통의 흥미 있는 화제가 있을 때 파티를 즐긴다는 것을 알았습니다.
문자열 배열 first, second가 주어집니다. 화이트씨의 i번째 친구가 흥미 있는 화제는 first[i]와 second[i]입니다. 즐거운 파티가 되려면 화이트씨가 초대할 수 있는 친구는 최대 몇 명인지 리턴하세요
[클래스와 함수 정의]
class : InterestingParty
method : public int bestInvitation(String[] first, String[] second)
[제약조건]
* first : 1~50개의 요소를 갖는 배열이다.
* second : first와 같은 크기의 배열이다.
* first, second 공통 : 각 요소는 1~15개의 문자이며, 각 문자는 영어 소문자이고, i번째 요소 first[i]와 second[i]의 내용은 다르다.
[입력데이터와 출력 데이터]
//0.
String[] first = {"fishing", "gardening", "swimming", "fishing"};
String[] second = {"hunting", "fishing", "fishing", "biting"};
//1.
String[] first = new String[]{"variety", "diversity", "loquacity", "courtesy"};
String[] second = new String[]{"talking", "speaking", "discussion", "meeting"};
//2.
String[] first = new String[]{"snakes", "programming", "cobra", "monty"};
String[] second = new String[]{"python", "python", "anaconda", "python"};
//3.
String[] first = new String[]{"t", "o", "p", "c", "o", "d", "e", "r", "s", "i", "n", "g", "l", "e", "r", "o", "u", "n", "d", "m", "a", "t", "c", "h", "f", "o", "u", "r", "n", "i"};
String[] second = new String[]{"n", "e", "f", "o", "u", "r", "j", "a", "n", "u", "a", "r", "y", "t", "w", "e", "n", "t", "y", "t", "w", "o", "s", "a", "t", "u", "r", "d", "a", "y"};
나의 답
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
public class InterestingParty {
public int bestInvitation(String[] first, String[] second){
//두 배열을 하나로 합친 배열을 만든다
String[] result = new String[first.length + second.length];
System.arraycopy(first, 0, result, 0, first.length);
System.arraycopy(second, 0, result, first.length, second.length);
//배열에서 중복되는 값에 대해 그룹핑하여 카운트를 value로 담은 map을 반환한다.
Map<String, Long> map = Arrays.stream(result).collect(Collectors.groupingBy(f -> f, Collectors.counting()));
//map의 value중 가장 큰 값을 추출한다.
return Collections.max(map.values()).intValue();
}
}
import ex2.InterestingParty;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
//1.
String[] first = {"fishing", "gardening", "swimming", "fishing"};
String[] second = {"hunting", "fishing", "fishing", "biting"};
//2.
first = new String[]{"variety", "diversity", "loquacity", "courtesy"};
second = new String[]{"talking", "speaking", "discussion", "meeting"};
//3.
first = new String[]{"snakes", "programming", "cobra", "monty"};
second = new String[]{"python", "python", "anaconda", "python"};
//4.
first = new String[]{"t", "o", "p", "c", "o", "d", "e", "r", "s", "i", "n", "g", "l", "e", "r", "o", "u", "n", "d", "m", "a", "t", "c", "h", "f", "o", "u", "r", "n", "i"};
second = new String[]{"n", "e", "f", "o", "u", "r", "j", "a", "n", "u", "a", "r", "y", "t", "w", "e", "n", "t", "y", "t", "w", "o", "s", "a", "t", "u", "r", "d", "a", "y"};
InterestingParty interestingParty = new InterestingParty();
System.out.println(interestingParty.bestInvitation(first,second));
}
}
문제 해설
위 문제는 모든 주제에 대해 몇 명의 사람이 관심을 갖고 있는지 확인하고 최댓값을 리턴한다.
- 화재를 순서대로 선택한다.
- 해당 화제에 몇 명이 흥미가 있는지 조사한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class InterestingParty {
public int bestInvitation(String[] first, String[] second){
int i, j;
int ans = 0;
for(i = 0; i < first.length; i++) {
int f = 0;
int s = 0;
for(j = 0; j < first.length; j++) {
if(first[i].equals(first[j])) f++;
if(first[i].equals(second[j])) f++;
if(second[i].equals(first[j])) s++;
if(second[i].equals(second[j])) s++;
}
ans = Math.max(f, ans);
ans = Math.max(s, ans);
}
return ans;
}
}
응용기술 - 불필요한 반복문 삭제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class InterestingParty {
public int bestInvitation(String[] first, String[] second){
HashMap<String, Integer> dic = new HashMap<String, Integer>();
for(int i = 0; i < first.length; i++) {
dic.put(first[i], 0);
dic.put(second[i], 0);
}
for(int i = 0; i < first.length; i++) {
dic.put(first[i], dic.get(first[i])+1;
dic.put(second[i], dic.get(second[i])+1;
}
int ans = 0;
for(String key: dic.keySet()) {
ans = Math.max(ans, dic.get(key));
}
return ans;
}
}
5-2. 암호
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
TSA는 새로운 암호화 시스템을 개발했습니다. 이 시스템은 암호화하려고 숫자 리스트를 입력받습니다.
여러분은 TSA의 비밀 정보 수사원입니다. 암호화 과정에서 중요한 부분을 구현하는 것이 여러분의 일입니다. 여러분은 입력 리스트에서 1개의 값을 선택하고 값을 1 증가시킵니다. 이때 리스트 내부의 모든 숫자 곱이 가장 커져야 합니다.
int[] numbers 형태로 숫자 배열 주어질 때 곱의 최댓값을 리턴하세요. 리턴 값이 2⁶²를 넘는 문제는 나오지 않을 것을 보장합니다.
[클래스와 함수 정의]
class : Cryptography
method : public long encrypt(int[] numbers)
[제약조건]
* numbers : 2~50개의 요소가 있는 배열이며 각 요소의 값은 1~1000이다.
* 리턴값 : 2⁶²를 넘지 않는다.
[입력데이터와 출력 데이터]
//0.
int[] numbers = {1,2,3}
//1.
numbers = new int[]{1,3,2,1,1,3}
//2.
numbers = new int[]{1000, 999, 998, 997, 996, 995}
//3.
numbers = new int[]{1, 1, 1, 1}
나의 답
1
2
3
4
5
6
7
8
9
10
11
12
public class Cryptography {
public long encrypt(int[] numbers) {
//배열을 정렬한다.
Arrays.sort(numbers);
//가장 작은 값에 1을 더하고, 배열의 모든 요소를 곱한다.
long result = numbers[0] + 1;
for (int i = 1; i < numbers.length; i++){
result *= numbers[i];
}
return result;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
public static void main(String[] args) {
//0. 결과 12
int[] numbers = {1,2,3};
//1. 결과 36
numbers = new int[]{1,3,2,1,1,3};
//2. 결과 986074810223904000
numbers = new int[]{1000, 999, 998, 997, 996, 995};
//3. 결과 2
numbers = new int[]{1, 1, 1, 1};
Cryptography cryptography = new Cryptography();
System.out.println(cryptography.encrypt(numbers));
}
}
문제 해설
- +1 하는 숫자를 정한다.
- 모든 곱을 계산하고 최댓값을 선택한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Cryptography {
public long encrypt(int[] numbers) {
long ans = 0;
for(int i = 0; i < numbers.length; i++) {
long temp = 1;
for(int j = 0; j < numbers.length; j++) {
if(i == j) temp *= (numbers[j] + 1);
else temp *= numbers[j];
}
ans = Math.max(ans, temp);
}
return ans;
}
}
응용 기술
이번 문제는 가장 작은 숫자에 +1 하면 된다. 최솟값은 정렬을 사용하여 간단히 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
public class Cryptography {
public long encrypt(int[] numbers) {
long ret = 1;
Arrays.sort(numbers);
numbers[0]++;
for(int i = 0; i < numbers.length; i++) {
ret *= numbers[i];
}
return ret;
}
}