

알고리즘 분류
- 자료 구조
- 정렬
- 이분 탐색
- 해시를 사용한 집합과 맵
일단 내가 푼 방법은 HashMap이다.
N개 주어진 숫자 카드 각각 몇 개 있는지를 알아야 하기 때문이다.
HashMap 사용
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(st.nextToken());
int cnt = map.getOrDefault(num, 0);
cnt++;
map.put(num, cnt);
}
StringBuilder sb = new StringBuilder();
int M = Integer.parseInt(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int ansNum = Integer.parseInt(st2.nextToken());
sb.append(map.getOrDefault(ansNum, 0) + " ");
}
System.out.println(sb.toString());
}
}
근데 처음에는 귀찮아서 StringBuilder 안쓰고 그대로 print로 출력했는데
시간제한에 걸렸다. 웬만해서는 StringBuilder 쓰는게 나을듯..
이진탐색 사용
찾아보니 이진탐색으로 푼 사람이 많은 것 같았다.
따라서 이 방법도 공부해봤다.
원래 이진탐색은 값이 일치하면 true or false를 리턴하는 구조였다.
(중앙값과 찾고자 하는 값)
그러나 이번 문제는 연속으로 중복된 값이 몇 번 입력됐는지 찾아야 하기 때문에
찾고자 하는 값의 인덱스 범위를 구해야 한다.
이때 lower_bound와 upper_bound의 개념을 사용한다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
sb.append(upperBound(arr, num) - lowerBound(arr, num)).append(" ");
}
System.out.println(sb.toString());
}
static int lowerBound(int[] arr, int num) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (num <= arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
static int upperBound(int[] arr, int num) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (num < arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
'Languages > Java' 카테고리의 다른 글
[BOJ 길라잡이/Java] 9일차 #1874 스택 수열 (0) | 2025.03.21 |
---|---|
[BOJ 길라잡이/Java] 8일차 #9012 괄호 (0) | 2025.03.19 |
[BOJ 길라잡이/Java] 8일차 #10867 중복 빼고 정렬하기 (0) | 2025.03.18 |
[BOJ 길라잡이/Java] 7일차 #11651 좌표 정렬하기 2 (0) | 2025.03.17 |
[BOJ 길라잡이/Java] 7일차 #11650 좌표 정렬하기 (0) | 2025.03.17 |


알고리즘 분류
- 자료 구조
- 정렬
- 이분 탐색
- 해시를 사용한 집합과 맵
일단 내가 푼 방법은 HashMap이다.
N개 주어진 숫자 카드 각각 몇 개 있는지를 알아야 하기 때문이다.
HashMap 사용
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(st.nextToken());
int cnt = map.getOrDefault(num, 0);
cnt++;
map.put(num, cnt);
}
StringBuilder sb = new StringBuilder();
int M = Integer.parseInt(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int ansNum = Integer.parseInt(st2.nextToken());
sb.append(map.getOrDefault(ansNum, 0) + " ");
}
System.out.println(sb.toString());
}
}
근데 처음에는 귀찮아서 StringBuilder 안쓰고 그대로 print로 출력했는데
시간제한에 걸렸다. 웬만해서는 StringBuilder 쓰는게 나을듯..
이진탐색 사용
찾아보니 이진탐색으로 푼 사람이 많은 것 같았다.
따라서 이 방법도 공부해봤다.
원래 이진탐색은 값이 일치하면 true or false를 리턴하는 구조였다.
(중앙값과 찾고자 하는 값)
그러나 이번 문제는 연속으로 중복된 값이 몇 번 입력됐는지 찾아야 하기 때문에
찾고자 하는 값의 인덱스 범위를 구해야 한다.
이때 lower_bound와 upper_bound의 개념을 사용한다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(st.nextToken());
sb.append(upperBound(arr, num) - lowerBound(arr, num)).append(" ");
}
System.out.println(sb.toString());
}
static int lowerBound(int[] arr, int num) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (num <= arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
static int upperBound(int[] arr, int num) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (num < arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
'Languages > Java' 카테고리의 다른 글
[BOJ 길라잡이/Java] 9일차 #1874 스택 수열 (0) | 2025.03.21 |
---|---|
[BOJ 길라잡이/Java] 8일차 #9012 괄호 (0) | 2025.03.19 |
[BOJ 길라잡이/Java] 8일차 #10867 중복 빼고 정렬하기 (0) | 2025.03.18 |
[BOJ 길라잡이/Java] 7일차 #11651 좌표 정렬하기 2 (0) | 2025.03.17 |
[BOJ 길라잡이/Java] 7일차 #11650 좌표 정렬하기 (0) | 2025.03.17 |