[이분탐색, 자료구조] 백준 - 숫자 카드 2

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

10816번: 숫자 카드 2

 

-문제해설

처음에 자바로 이분탐색으로 풀었는데 아무리해도 시간초과가 나왔다.. ㅠ

결국 해시맵을 이용한 풀이로 바꿔서 풀었다. 이 외에도 n의 입력값들을 배열의 인덱스로 설정한 뒤 푸는 방법도 존재한다.

 

파이썬은 배열 인덱스에 입력값을 추가하는 방법으로 풀었다.

이때 숫자의 범위가 -10,000,000 ~ 10,000,000이므로 배열의 크기는 20,000,001 이 되어야 한다.

그리고 입력값을 집어넣을 때는

배열명[10,000,000+입력값] += 1 로 넣어줘야 한다.

 

추가적으로 파이썬은 Counter라는 모듈을 이용해서 더 빠르고 간단하게 풀 수 있다.
Counter를 이용한 풀이는 백준의 hsh0322님의 코드를 참고하였다.

 

 

-자바( 이분탐색 코드 : 시간초과 )

package dataStructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BJ10816 {
	
	private static int chkSearch( int target, ArrayList<Integer> nr ) {
		int ans = 0;
		int start = 0;
		int end = nr.size()-1;

		while( true ) {
			if( start > end ) break;
			if( start == end && nr.get(start) != target ) break;
			
			int mid = (start+end)/2;
			
			if( nr.get(mid) == target ) {
				ans++;
				nr.remove( mid );
				end = nr.size()-1;
				continue;
				
			} else if( nr.get(mid) < target ) start = mid + 1;
			else end = mid;
		}
		
		return ans;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		StringTokenizer st;
		
		//n입력 및 nrr 배열 설정
		int n = Integer.parseInt( br.readLine() );
		ArrayList<Integer> nrr = new ArrayList<Integer>(n);
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) nrr.add( Integer.parseInt( st.nextToken() ) );
		
		Collections.sort( nrr );
		
		//m입력 및 입력값에 대한 이분탐색 실시	
		int m = Integer.parseInt( br.readLine() );
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<m; i++ ) {
			ArrayList<Integer> arr = new ArrayList<Integer>(nrr);
			sb.append( chkSearch( Integer.parseInt(st.nextToken()), arr ) + " " );
		}
			
		System.out.println( sb );
	}
}

-자바( 해시맵 이용 )

package dataStructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BJ10816_1 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		StringTokenizer st;
		
		//n입력 및 해시맵 선언
		int n = Integer.parseInt( br.readLine() );
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) {
			int a = Integer.parseInt( st.nextToken() );
			//해시맵 키 중에 a가 있으면 a키값+1, 없으면 1로 put
			hm.put( a, hm.getOrDefault(a, 0)+1 );
		}
		
		int m = Integer.parseInt( br.readLine() );
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<m; i++ ) {
			int a = Integer.parseInt(st.nextToken());
			//hm해시맵에 a키가 있으면 a키의 값을 sb에 append하고 없으면 0을 append한다.
			if( hm.containsKey( a ) ) sb.append( hm.getOrDefault( a, 0 ) + " " );
			else sb.append( 0 + " " );
		}
		System.out.println( sb );
	}
}

 

 

 

-파이썬( 배열 인덱스 이용한 풀이 )

import sys
line = sys.stdin.readline

n = int( line() )
nrr = [ 0 for _ in range( 20000001 ) ]

tmp = list( map( int, line().split() ) )
for i in tmp: nrr[10000000+i] += 1

s = ""
m = int( line() )
tmp2 = list( map(int, line().split()) )
for i in range( m ):
    if nrr[ 10000000+tmp2[i] ] != 0: s += str( nrr[ 10000000+tmp2[i] ] ) + " "
    else: s += "0 "
    
print( s )

 

-파이썬( Counter 모듈 이용한 풀이 )

import sys
from collections import Counter
line = sys.stdin.readline
n = line()
nrr = line().split()
m = line()
mrr = line().split()

c = Counter( nrr )
print( ' '.join( str(c[i]) if i in c else '0' for i in mrr ) )