숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean[] arr = new boolean[20_000_001]; // 크기를 20,000,001로 변경하여 인덱스 문제 해결
int n = Integer.parseInt(br.readLine());
String[] cards = br.readLine().split(" ");
int m = Integer.parseInt(br.readLine());
String[] numbers = br.readLine().split(" ");
StringBuilder sb = new StringBuilder();
for (String card : cards) {
int c = Integer.parseInt(card);
if (c < 0) c = Math.abs(c) + 10_000_000;
arr[c] = true;
}
for (String number : numbers) {
int no = Integer.parseInt(number);
if (no < 0) no = Math.abs(no) + 10_000_000;
if (arr[no]) sb.append("1").append(" ");
else sb.append("0").append(" ");
}
System.out.println(sb);
}
}
Time: 732 ms
Memory: 133752 KB
숫자 카드의 숫자 인덱스의 값을 true 로 변경하기 위해 boolean 배열을 선언했다. 숫자 값은 -10,000,000 ~ 10,000,000 까지의 범위를 가지기 때문에 음수 처리를 위해 배열의 크기를 20,000,001 로 선언했다. 음수 값이 들어오면 절대 값으로 변환 후 10,000,000 을 더한 인덱스 값에 넣으려고 한다.
처음엔 절대 값으로 변환해야 하는걸 깜빡해서 헤맸다. 그리고 이 풀이를 훨씬 더 간결하고 쉽게 개선할 수 있는데 아래 풀이와 같다.
개선하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<Integer> set = new HashSet<>();
int n = Integer.parseInt(br.readLine());
String[] cards = br.readLine().split(" ");
int m = Integer.parseInt(br.readLine());
String[] numbers = br.readLine().split(" ");
StringBuilder sb = new StringBuilder();
for (String card : cards) set.add(Integer.parseInt(card));
for (String number : numbers) {
if (set.contains(Integer.parseInt(number))) sb.append("1").append(" ");
else sb.append("0").append(" ");
}
System.out.println(sb);
}
}
Time: 864 ms
Memory: 153272 KB
HashSet 을 이용한 풀이인데 속도는 조금 느리긴 해도 간결하고 가독성도 좋다. 그리고 실무에서는 숫자 범위가 정해져서 들어오는게 아니기 때문에 어떤 숫자여도 대응이 가능하다.
돌아보기
항상 작은 실수들을 한다. 이번에 절대 값 변환을 빼먹었다는걸 알아차린건 질문을 작성하면서 알게 됐다. 뭘 놓친건지 모르면 한번 글로 직접 적어보는 것도 큰 도움이 되는 것 같다.
