[Java]HashMap 응용력 키우기2 -두 수의 합과 세 수의 합 그리고 네 수의 합-
1. 문제
n개의 정수가 입력으로 주어지고, 이 중 서로 다른 위치에 있는 두 개의 수를 뽑아 더했을 때 k가 되는 가짓수를 구하는 프로그램을 작성해보세요.
2. 풀이
가장 쉬운 방법은 $O(N^{2})$으로 해결하는 것이다.
배열에 N개의 정수를 모두 저장하고, 2중 for문을 돌아서 모든 쌍을 검사해서 합이 k가 되는지 검사해보는 것이다
하지만 N의 제한이 최대 10만이라면?
당연히 $O(N^{2})$의 알고리즘을 요구하는 문제는 아닐 것이다
합이 k가 되는 두 원소는 어떻게 선택할 수 있을까?
배열에서 한 원소를 골랐을때, 다른 원소는 무조건 k - (이전에 고른 원소)를 골라야할 것이다.
그러므로, HashMap에 배열의 모든 원소의 정보를 저장해두고, 배열에서 한 원소를 고르는 작업을 O(N)에 해결하고,
다른 원소인 k - (이전에 고른 원소)를 고르는 작업은 HashMap에 접근하여 O(1)에 해결한다면, O(N)에 문제를 해결할 수 있을 것이다.
import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] arr = new long[n];
HashMap<Long,Integer> count = new HashMap<>();
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
int answer = 0;
//배열을 처음부터 순회하여 한 원소 arr[i]를 고른다
for(int i = 0; i < n; i++){
// k - arr[i]가 hashmap에 있는지 검사하여, 있다면 그 개수만큼 count
// arr[i] 1가지 * k-arr[i] x개 = x가지 가능하니까
if(count.containsKey(k-arr[i]) == true){
answer += count.get(k-arr[i]);
}
//hashmap에 arr[i]가 있다는 것을 기록해준다.
if(count.containsKey(arr[i]) == false){
count.put(arr[i],1);
} else {
count.put(arr[i],count.get(arr[i])+1);
}
}
System.out.println(answer);
}
}
처음부터 hashmap에 기록하지 않고, 일단 순회해서 hashmap에 바로 접근해서 k - arr[i]의 개수를 더해나가고,
그 다음 hashmap에 arr[i]를 기록한다는 것이 특이한데
hashmap에 arr[i]를 먼저 기록한다면..
arr의 모든 원소가 같은 경우에 처리하는 것이 까다로워진다(실제로 그럼..)
5 6
3 3 3 3 3
사소한 디테일로 자바에서는 변수의 type 설정이 중요한데,
이 문제의 k 제한은 $+-2^{31}$이고 배열 arr의 원소는 $+-10^{9}$이다.
그래서 k-arr[i]가 int범위를 벗어날 수 있어서 ($2*10^{9}$정도일거임)
HashMap의 key를 int보다 큰 long으로 설정한다는 것을 기억해야한다.
3. 문제2
n개의 정수가 입력으로 주어지고, 이 중 서로 다른 세 개의 위치를 골라 각 위치에 있는 세 수를 더했을 때 k가 되는 서로 다른 조합의 개수를 출력하는 코드를 작성해보세요.
4. 풀이
비슷하게 응용하면 될 것 같다
배열에서 두 원소 arr[i], arr[j]를 골랐을 때, 나머지 한 원소는 k - arr[i] - arr[j]를 고르면 된다.
그러다보니 배열에서 두 원소를 고르는 arr[i], arr[j]를 고르는 과정 때문에 $O(N^{2})$이 필요하다.
그래서 n의 제한이 1000으로 두 수의 합 문제보다는 작다
import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] arr = new long[n];
HashMap<Long, Integer> count = new HashMap<>();
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
int answer = 0;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(count.containsKey(k-arr[i]-arr[j]) == true){
answer += count.get(k-arr[i]-arr[j]);
}
}
if(count.containsKey(arr[i]) == false){
count.put(arr[i],1);
} else {
count.put(arr[i],count.get(arr[i])+1);
}
}
System.out.println(answer);
}
}
서로 다른 위치를 고르기 때문에 i는 0부터 n-2까지라면, j는 i+1부터 n-1까지가 된다.
먼저 k-arr[i]-arr[j]의 개수를 hashmap에 찾아서 더해나가고,
j for문을 벗어나면, arr[i]의 개수를 hashmap에 기록해준다
j for문 안에서 arr[j]의 개수를 hashmap에 기록해준다면... 이게 문제가
j for문은 i for문이 돌때마다 n번을 계속해서 도니까... arr[j]가 중복해서 hashmap에 count된다
arr[i]는 한번만 기록해야하니까.. i for문 내에서 기록한다면 1번만 기록될 것
------------------------------------------------------------------------------------------------------------------------------------------
코드를 곱씹어보면서 왜 맞는지 생각을 좀 해보면
5 4
1 2 1 4 -1
i, j가 위와 같이 가리킬때, k - arr[i] - arr[j] = 4 - 1 - 2 = 1이니까, 1이 hashmap에 존재하는지 검사해서 있으면 count해서 더해주는데
없으면 j를 끝까지 이동시켜 나가면서, k - arr[i] - arr[j]가 있는지 검사해서 count해준다.
j for문이 끝나면...
위와 같은 상태가 될거임
그러면 k - arr[i] - arr[j] = 1이고 현재 hashmap에 1이 1개 있으니까, answer = 1이 될거다
이런 식으로 다시 j가 끝까지 이동하면, 다시 hashmap에 arr[i]를 기록하는데..
현재 이 상태에서는 j가 끝까지 가도 4를 만들 수 없으니까...
이러면 k - arr[i] - arr[j] = 1이고 현재 1은 hashmap에 2개가 있다.
그래서 (0,1,2)랑 (0,3,4)랑 (2,3,4) 3개가 세진다
이게 3개의 서로 다른 위치의 수를 고를건데 i,j가 먼저 순회하고 나서, i,j가 끝나면 arr[i]를 hashmap에 기록하는데
그 순간 3번째 인덱스 s가 순회할 위치가 생긴다
그런데 3번째 인덱스의 위치는 for문으로 순회하는게 아니고 hashmap에서 바로 찾아내는게 시간복잡도를 줄이는 핵심
arr[n-1]을 기록안해도 되는건가 생각했는데
서로 다른 세 위치를 고르는 "조합"의 수이면서 3번째 수는 위와 같이 i,j 인덱스의 뒤쪽에 위치하니까... 굳이 안해도 되는것 같기도 하고
아니면 테스트 케이스가 부족한건지
아무튼 근데 코드를 곱씹어보니까 맞는것 같기는 한디.. 뭔가 신기하네 ㄹㅇ
5. 문제3
네 개의 수열 A, B, C, D에서 각각 원소를 하나씩 골라 더하였을 때 합이 0이되는 경우의 수를 구하는 프로그램을 작성해보세요.
6. 풀이
가장 간단한 방법은 4중 for문으로 A,B,C,D 각각에서 하나의 수를 고르고 더해서 0인지 검사해서 경우의 수에 더해주면 되는건데
당연히 허용을 안하겠지
줄여도 a,b,c 고르고 나머지는 k - a - b - c를 hashmap에 찾아서 3중 for문이긴 한데
n 제한이 5000까지라 5000*5000*5000이라 시간안에 통과 못하겠지
-------------------------------------------------------------------------------------------------------------------------------------------
이 문제의 핵심은 A,B 배열과 C,D 배열로 나눠서 생각하는 것이다
A,B 배열에서 구할 수 있는 모든 두 원소의 합 a+b를 hashmap에 기록해두고
C,D 배열에서 각각 C[i], D[j]를 고른다.
그러면 네 수의 합이 0이 될려면... C[i] + D[j] = s일 때, 필요한건 -s이다.
즉 모든 A+B가 기록된 hashmap에서 -s가 존재하는지 검사해서, 존재하면 그 개수만큼 count해주면 된다.
이러한 알고리즘을 "중간에서 만나기(meet in the middle)"라고 부른다.
브루트포스이지만, 브루트포스가 아닌 그런 느낌?
주어진 문제를 절반으로 나눠서, 각 절반에서 구한 문제의 결과를 합쳐서 원래 문제의 정답을 구하는 방법
import java.util.Scanner;
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] A = new int[n];
int[] B = new int[n];
int[] C = new int[n];
int[] D = new int[n];
HashMap<Integer,Integer> ab = new HashMap<>();
for(int i = 0; i < n; i++){
A[i] = sc.nextInt();
}
for(int i = 0; i < n; i++){
B[i] = sc.nextInt();
}
for(int i = 0; i < n; i++){
C[i] = sc.nextInt();
}
for(int i = 0; i < n; i++){
D[i] = sc.nextInt();
}
// A+B의 모든 조합 A[a] + B[b]를 hashmap에 기록해준다
for(int a = 0; a < n; a++){
for(int b = 0; b < n; b++){
int s = A[a] + B[b];
if(ab.containsKey(s) == true){
ab.put(s,ab.get(s)+1);
} else {
ab.put(s,1);
}
}
}
int answer = 0;
// C[c] + D[d] = s를 고르고, 네 수의 합이 0이 되기 위해
// -s를 A[a] + B[b]에서 골라준다.
// A[a] + B[b]는 hashmap에 있으니 -s가 hashmap에 존재하는지 검사해서 개수만큼 count
for(int c = 0; c < n; c++){
for(int d = 0; d < n; d++){
int s = C[c] + D[d];
if(ab.containsKey(-s) == true){
answer += ab.get(-s);
}
}
}
System.out.println(answer);
}
}
근데 A,B배열과 C,D배열로 나눠도 해결이 되는 이유가 뭘까?
A,C와 B,D로 나누는 경우, A,D와 B,C로 나누는 경우... 이런 경우도 분명 있는 것 같은데..?
근데 이건 AB 집합을 한번 써보면 의문이 대충 해결이 된다..
-------------------------------------------------------------------------------------------------------------------
A,B배열에서 A,B 각각의 모든 원소의 합 A[a] + B[b]는...
AB = {A[0]+B[0], A[0]+B[1], A[0]+B[2],.... A[n-1]+B[0], A[n-1] + B[1],.... A[n-1]+B[n-1]}이 들어가 있고...
이제 C,D에서 각각 C[c], D[d]를 골라 C[c]+D[d] = s를 구하고...
-s값을 AB 집합에서 찾을건데.. 찾으면 A[a]+B[b]+C[c]+D[d] = 0
근데 조금 생각해보면
AC = {A[0]+C[0], A[0]+C[1], ... A[n-1]+C[0], A[n-1]+C[1], ... A[n-1]+C[n-1]}이고...
이제 B,D에서 각각 B[b], D[d]를 골라 B[b]+D[d] = s를 구하고...
-s값을 AC 집합에서 찾을건데.. 찾으면 A[a]+C[c]+B[b]+D[d] = 0
결국 (a,b,c,d)를 고르는건 어떻게 하든 똑같은거잖아..!
그러니까 AB와 CD로만 나눠도 (a,b,c,d)를 고르는 모든 경우를 커버하잖아
와 근데 진짜 신기하네 ㅋㅋ
투포인터를 이용한 풀이도 있는데 언젠가 기록하는걸로...
'알고리즘 > 중간에서 만나기' 카테고리의 다른 글
| 중간에서 만나기 테크닉 - 저장하고 검사하는 것이 아니라 검사를 먼저하고 저장하기 (0) | 2024.06.10 |
|---|
