[백준] 10816 - 숫자 카드 2 (java)
zl존석동
·2022. 1. 24. 18:17
백준 10816번 숫자 카드 2 자바 풀이
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
문제 간단 요약
숫자 중복이 가능한 숫자 카드들이 50만개 이하로 주어진다.
찾아야 할 숫자 목록도 50만개 이하로 주어진다.
주어진 숫자카드에 찾아야 할 숫자가 몇 개 있는지를 출력한다.
주의점
최악의 경우 숫자카드가 50만개 주어지고
찾아야 할 숫자 목록도 50만개가 주어질 수 있다.
기본적으로 숫자카드 50만개에 대해 반복을 돌면서 찾아야 할 숫자 하나하나에 대해 비교를 해야한다.
제한 시간이 1초이기 때문에 한 번의 비교에 2000번 이상 연산하면 안된다고 이해했다!
나의 풀이 1 - Map
Map으로 풀면 더럽게 쉽다.
카드의 숫자를 Key로 하고 그 숫자의 개수를 Value 로 설정해 Map에 넣어주고 찾기만 하면 된다.
풀이는 생략!
나의 풀이 1 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int len = Integer.parseInt(br.readLine());
//존재하는 숫자카드의 숫자들을 맵에 저장
Map<Integer, Integer> map = new HashMap<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < len; i++) {
int key = Integer.parseInt(st.nextToken());
map.put(key, map.getOrDefault(key, 0) + 1);
}
br.readLine();
// 주어진 숫자 배열
int[] resultArr = Arrays.stream(br.readLine().split(" ")).mapToInt(v->Integer.parseInt(v)).toArray();
StringBuilder sb = new StringBuilder();
// 주어진 숫자에 대한 숫자 카드를 몇 개 가지고 있나
Arrays.stream(resultArr).forEach(v -> sb.append(map.getOrDefault(v,0)).append(" "));
System.out.println(sb.toString());
}
}
나의 풀이 2 - Binary Search
기존의 이분 탐색처럼 활용하려고 해도 문제에서는 해당되는 값에 대한 개수를 요구하고 있다.
1. 해당값을 이분 탐색으로 찾고 앞뒤로 같은 값의 수를 탐색하여 구한다?
- 효율적이어 보일 수 있지만 안된다.
- 50만개 입력이 주어지고 모든 숫자가 다 같다고 생각하면 시간 복잡도가 O(n) + O(log2(N)) 이 되지 않을까?
- 물론 모든 값이 같다면 이분탐색 자체가 의미가 없어질 것이기에 결국 탐색을 위한 시간 복잡도는 O(n) 이 될 것이다.
- 알고리즘 스터디 팀원의 풀이를 참고해 그렇게 풀어보았는데 70% 대에서 시간초과가 났다.
2. 해당 값으로 시작하는 인덱스와 해당 값보다 큰 것들 중 가장 작은 수의 인덱스를 이용
- 하나의 값에 대해 이분 탐색을 두번 시행하여 O(log2(N)) * 2 가 되지 않을까 생각한다.
다음과 같은 입력이 들어왔을 때
| InputArray |
| [6 , 3 , 3 , 10 , 10 , 10 , 3 , -10 , 7 , 3] |
이분 탐색을 하기 때문에 당연히 정렬을 먼저 해주어야 한다.
| Sort(InputArray) |
| [-10 , 3 , 3 , 3 , 3 , 6 , 7 , 10 , 10 , 10] |
여기서 만약 3의 개수를 찾아야 한다면
3이 시작하는 인덱스와 3보다 크지만 가장 작은 6에 대한 인덱스들을 각각 구한다.
두 인덱스의 차가 3이라는 값의 개수인 5 - 1 = 4 를 나타내며 문제의 요구에 대한 답이다.
과정 1. 해당 값으로 시작될 때의 인덱스 찾기
3의 개수를 구해야 한다고 생각해보자. 여기서 구해야 하는 위치는 -10 바로뒤에 있는 3의 위치이다.
초기 상태는 다음과 같을 것이다.
val(M) = 6 > 3 으로 M 부터 R 까지의 값은 필요없다.
R 을 M 으로 설정해주고 M 을 다시 구한다.
val(M) = 3 으로 찾아야 하는 값과 같다 하더라도 정답이 될 수는 없다.
현재의 관심사는 3으로 시작하는 부분의 위치이고
val(M)이 3이고 그 뒤로는 3이있던 다른 값이 있던 알 바가 아니며 앞에 3이 더 있는지 없는지 아직 알 수 없다.
R 을 M 으로 땡겨와 준다.
아직까지는 val(M) 이 3이라 하더라도 우리는 알 수 있지만 컴퓨터는 처음으로 나온 3인지 알 수 없다.
R 을 M으로 다시 땡겨온다.
이제 val(M) < 3 으로 개수를 찾아야 하는 값보다 작아졌다.
이 때는 L 을 M + 1 로 설정해준다.
M 에 위치하는 값보다 찾아야 하는 값이 클 경우 M 위치를 포함해 앞에 있는 것들에 대한 정보는 필요없어지게 되기 때문이다.
R == L 이되는 시점. 즉 이분탐색을 끝 마쳤을 때 L 의 위치를 리턴하면 된다. => 1
과정 2. 해당 값보다 크면서도 가장 작은 값의 인덱스 구하기
여기서는 6에 대한 위치를 구해야 한다!
val(M) = 6 > 3 이다.
이미 3보다 큰 값이 M 에 위치하기 때문에 6보다 더 큰 값들에 대해서는 관심이 없어진다.
R 을 M 으로 설정!
val(M) = 3 = 찾아야 하는 값이다.
우리가 찾고 싶은 것은 찾아야하는 3보다 바로 큰 값의 위치이다.
앞에서 시작하는 위치를 찾는 로직과 유사하지만 다른 것은 M을 기준으로 어디에 관심이 있는지이다.
앞에서는 가장 맨 앞에 있는 3에 관심이 있었기에 val(M) == 3 이라 하더라도 R 을 땡겨왔지만
여기서는 val(M) > 3 인 것 중 최소값에 관심이 있기에 L 을 M 보다 1개 큰 쪽으로 땡겨와야 한다.
val(M) 이 여전히 3과 같다.
이때 L 을 M + 1의 위치로 땡겨주면 L == R == M == 6의 위치가 되고
결과적으로 L 의 위치를 리턴하면 찾아야 하는 값보다 크지만 가장 작은 값의 위치를 얻을 수 있다. => 5
과정 3. 각 인덱스의 차 구하기
과정 2의 결과 - 과정 1의 결과 = 5 - 1 = 4 로 3이 4개 존재함을 구할 수 있다.
찾아야 하는 값이 없다면?
결국 위의 과정1과 과정2의 로직은 찾아야 하는 값이 중앙 인덱스에 나타났냐 아니냐의 차이만 있다.
따라서 요구하는 값이 존재하지 않으면 같은 로직을 돌고 같은 인덱스를 리턴하여 0 이라는 결과를 얻게 될 것이다.
나의 풀이 2 코드
Map 으로는 5분도 안걸려서 풀었는데
두 부분으로 나누어서 이분탐색을 한다는 것을 생각하는데 좀 오래걸려서 어려웠던 것 같다.
메소드 이름이 거지같긴 하지만 각각 위의 과정1 과 과정2 라고 생각하면 될 것 같다!
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
// 숫자카드2 이분탐색으로 풀기
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int count1 = Integer.parseInt(br.readLine());
StringTokenizer st1 = new StringTokenizer(br.readLine());
int[] have = new int[count1];
for (int i = 0; i < count1; i++) {
have[i] = Integer.parseInt(st1.nextToken());
}
int count2 = Integer.parseInt(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
int[] correct = new int[count2];
for (int i = 0; i < count2; i++) {
correct[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(have);
int[] result = new int[count2];
for (int i = 0; i < count2; i++) {
int currentValue = correct[i];
int countOfCurrentValue =
getMinIndexGreaterThanCurrentValue(currentValue, have)
- getMaxIndexLessThanCurrentValue(currentValue, have);
result[i] += countOfCurrentValue;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
sb.append(result[i]).append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static int getMaxIndexLessThanCurrentValue(int curVal, int[] arr) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (curVal <= arr[mid]) {
right = mid;
continue;
}
left = mid + 1;
}
return left;
}
public static int getMinIndexGreaterThanCurrentValue(int curVal, int[] arr) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (curVal < arr[mid]) {
right = mid;
continue;
}
left = mid + 1;
}
return left;
}
}
'알고리즘 & 자료구조 > 백준' 카테고리의 다른 글
| [백준] 2447 별 찍기 - 10 (java) (0) | 2022.03.13 |
|---|---|
| [백준] 5692 팩토리얼 진법 (java) (0) | 2022.03.05 |
| [백준] 3079 입국 심사 (java) (0) | 2022.02.18 |
