백준 - 숫자 카드 2
구해야 하는 것
- 각 숫자 카드를 몇 개 가지고 있는지
주어진 자료
- 갖고 있는 숫자 카드 개수 = n
- 개수를 구해야 하는 숫자 카드 개수 = m
- 1 <= n <= 500,000
- -10,000,000 <= 숫자 카드에 적혀있는 수 <= 10,000,000
- 1 <= m <= 500,000
조건
- 1 <= 문자열 길이 <= 1,000,000
- 1 <= 폭발 문자열 길이 <= 36
- 모든 폭발이 끝난 후 남아있는 문자가 없으면 "FRULA" 출력
계획 1
- 숫자 카드에 적힌 수를 키로, 개수를 값으로 가지는 맵을 만든다.
- n개의 카드를 입력받아서 맵에 넣는다.
- m개의 카드를 입력받아서, 각 숫자가 맵에 키로 존재하면 값을 출력하고, 없으면 0을 출력한다.
실행 1 → 시간 초과
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 1. 숫자 카드에 적힌 수를 키로, 개수를 값으로 가지는 맵 만듦
Map<Integer, Integer> map = new HashMap<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; i++) {
int key = Integer.parseInt(st.nextToken());
// 2. n개의 카드를 입력받아서 맵에 넣는다.
if(!map.containsKey(key)) { // 맵에 키 존재하지 않으면 값에 1 넣어줌
map.put(key, 1);
} else {
map.put(key, map.get(key) + 1); // 맵에 이미 키 존재하면 기존값에서 1 증가
}
}
// 3. m개의 카드를 입력받아서 각 키에 대한 값을 출력한다.
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < m; i++) {
int key = Integer.parseInt(st.nextToken());
if(!map.containsKey(key)) { // 맵에 키가 존재하지 않으면 0 출력
System.out.print(0 + " ");
} else { // 존재하면 값 출력
System.out.print(map.get(key) + " ");
}
}
System.out.println();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
계획 2
- 숫자 카드에 적힌 수를 키로, 개수를 값으로 가지는 맵을 만든다.
- -10,000,000부터 10,000,000까지 값을 0으로 넣어놓는다.
- n개의 카드를 입력받아서 각 키에 대한 값을 증가시킨다.
- m개의 카드를 입력받아서, 각 숫자키에 대한 값을 출력한다.
실행 2 → 메모리 초과
사실 이건 코드 쓰면서도 비효율적이라고 생각하긴 했음
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 숫자 카드에 적힌 수를 키로, 개수를 값으로 가지는 맵을 만든다.
// 2. -10,000,000부터 10,000,000까지 값을 0으로 넣어놓는다.
Map<Integer, Integer> map = new HashMap<>();
for(int i = -10000000; i <= 10000000; i++) {
map.put(i, 0);
}
// 3. n개의 카드를 입력받아서 각 키에 대한 값을 증가시킨다.
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; i++) {
int key = Integer.parseInt(st.nextToken());
map.put(key, map.get(key) + 1);
}
// 4. m개의 카드를 입력받아서, 각 숫자키에 대한 값을 출력한다.
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < m; i++) {
int key = Integer.parseInt(st.nextToken());
System.out.print(map.get(key) + " ");
}
System.out.println();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
계획 3
계획 2에서 메모리 초과가 발생해서 다시 계획 1에서 속도를 개선할 수 있는 부분이 있는지 찾아봤다.
우선 map.containsKey(key)부분이 시간이 많이 걸리나 싶어서 map.get(key)의 값이 null인지 아닌지로 판단하는 것으로 수정했다. (찾아보니까 containsKey()랑 get() 둘 다 시간복잡도가 O(1)이라서 굳이 수정하지 않아도 되는 부분이었다.)
그리고 for문을 m번 돌면서 매번 출력하게 했던 것도 출력해야 하는 문자열을 StringBuilder로 합친 후 마지막에 한번만 출력하도록 수정했다.
실행 3
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
HashMap<String, Integer> map = new HashMap<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; i++) {
String key = st.nextToken();
if(map.get(key) == null) {
map.put(key, 1);
} else {
map.put(key, map.get(key) + 1);
}
}
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
for(int i = 0; i < m; i++) {
String key = st.nextToken();
// 출력할 문자열을 append로 합치도록 수정
if(map.get(key) == null) {
sb.append(0 + " ");
} else {
sb.append(map.get(key) + " ");
}
}
System.out.println(sb);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
반성
- 여러개를 합쳐서 출력해야 할 때는 꼭
StringBuilder를 사용하자!!!!