10816 숫자 카드 2

코딩을 하고 이 문제를 보니 굳이 이진탐색으로 분류해 놓은 이유가 궁금했다. 이 문제는 구현의 느낌이 좀 강하고, 다양한 풀이법이 있다.

 

이 문제의 핵심은 음수의 처리이다. 백준 온라인 저지에서 맞은사람 순위표에서 많은 분들의 코드를보니  그 부분은 정말 다양하게 처리가 되었다.

 

본 문제는 시간 복잡도가 높은 편이다. 50만개의 데이터를 순회하며 개수를 확인해야 하기 때문이다. 당연히 O(1)인 배열의 사용이 가장먼저 떠올랐다.

 

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int N,M;
	static int[] A;
	static int[] countPlus = new int[10000001];
	static int[] countMinus = new int[10000001];
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		A = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
			if(A[i]<0) {
				countMinus[A[i]*(-1)]++;	
			}
			else {
				countPlus[A[i]]++;
			}
		}
		
		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int seek = Integer.parseInt(st.nextToken());
			if(seek<0)sb.append(countMinus[seek*(-1)]+" ");
			else sb.append(countPlus[seek]+" ");
		}
		bw.write(sb.toString());
		bw.flush();
		

	}

}

 

내 코드는 지금 당장 얼마든지 다듬을 수 있지만 계속 알고리즘을 풀며 문제를 풀음과 동시에 좋은 코드를 작성하기 위해 노력할 것이므로 남겨두자. 그 이유는 후에 내 부족했던 부분을 보면 성장의 느낌이 많이 나기 때문이다.

 

꾸준함은 쉬워보이지만 가장 어렵고 누구도 꾸준함을 이길 수 없다.