문제 정보
플랫폼 : 백준
분류 : ???
난이도 : 실버4
링크 : https://www.acmicpc.net/problem/10815
시간제한 및 메모리 제한 검증
O(n) 풀이 : 시간제한 ok
boolean[20,000,001] -> 약 9.5mb의 메모리 : 메모리제한 ok
(20,000,001 byte / 1024byte / 1024byte ≒ 9.5mb)
자료형 : +- 1000만 > int 사용
풀이
이거... 무슨 유형인지 모르겠다. 처음에는 분류를 DP로 들어갔는데, DP도 아니고.. 그냥 HashMap이나 Array쓰면 될것 같았다.
이분탐색을 사용해보려고도 했는데, 어차피 메모리에 문제가 없다면? O(nlogn) 보다는 O(n)이 낫다고 생각했다.
그리고 통과했다. (Java 시간 순으로 2등이다. 메모리도 크게 차이 안난다.)
알고리즘
1. boolean[20_000_001]을 선언한다.
-인 애들에게 전부 1000만씩 더해서 0 이상으로 만들 예정이다.
2. 상근이가 가지고있는 카드의 입력을 받아서, arr[카드의 값] = true로 만들어준다.
3. 구분해야 할 카드의 입력을 받아서, arr[카드의 값] == true이면 1을, 아니면 0을 출력한다.
System.out.println을 사용하지 않은 이유는, 해당 메소드를 사용시 매번 버퍼를 비워야 해서 느리다.
BufferedWriter를 쓰지 않은 이유는, IOException처리나 선언이 귀찮았기 때문이다.
String에 + 연산자로 붙이지 않은 이유는, 이후에 포스팅하면 링크 첨부하겠지만, 느리다. 간단하게 얘기하면 +연산을 할 때마다 new String을 호출하기 때문이다.
이러한 이유로 버퍼를 사용하여 한번에 출력하는 StringBuilder를 사용했다.
추가로, 20000001같이 큰 숫자는 1000의 단위로 _를 통해 나눌 수 있다.
위 코드에서 보이듯 20_000_001로 표기할 수 있다.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 1. boolean[20_000_001]을 선언한다.
boolean[] arr = new boolean[20_000_001];
// 2. 상근이가 가지고있는 카드의 입력을 받아서, arr[카드의 값] = true로 만들어준다.
int n = stoi(br.readLine());
String[] input = br.readLine().split(" ");
for(int i = 0; i < n; i++) {
int val = stoi(input[i]) + 10_000_000;
arr[val] = true;
}
// 3. 구분해야 할 카드의 입력을 받아서, arr[카드의 값] == true이면 1을, 아니면 0을 출력한다.
int m = stoi(br.readLine());
input = br.readLine().split(" ");
for(int i = 0; i < m; i++) {
int val = stoi(input[i]) + 10_000_000;
if(arr[val]) sb.append(1);
else sb.append(0);
sb.append(' ');
}
System.out.println(sb);
}
public static int stoi(String str) {return Integer.parseInt(str);}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
