[자료구조] 백준 - 듣보잡

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

1764번: 듣보잡

 

-문제해설

문제는 듣도못한 사람과 보도못한 사람이 겹치는 사람의 수와 이름을 출력하는 것이다.

 

듣도못한 사람이 3

홍길동

김길동

박길동

보도못한 사람이 4

홍길동

박길동

이길동

정길동

 

이라고하면 이름은 사전순으로 출력해야 하므로

2

박길동

홍길동

이 된다.

 

이를 위해 처음에 해시맵 hs1에 ( 키: 이름, 값: 1 ) 로 듣도못한 사람들을 삽입한다.

 

그리고 arr ArrayList를 만들고 보도못한 사람들을 입력받는데

hs1에 보도못한사람들을 삽입한다. 이때 이미 있는 사람들의 경우 값을 1에서 2로 증가시킨다.

이를 위해서 hs1.put( tmp, hs1.getOrdefault( tmp, 0 ) + 1 ); 코드를 이용한다.

tmp는 보도못한사람을 입력받아 저장하는 문자열이다.

 

hs1.getOrdefault( tmp, 0 ) + 1 는 hs1의 키 중에 tmp가 있으면 그 값에 +1,

없으면 0 + 1을 해서 키를 만들어라. 라는 명령이다. 이를 hs1에 put시킨다.

 

그리고 조건문으로 hs1.get( tmp ) > 1인 경우, 즉 tmp 키의 값이 2이상인 경우 tmp를 arr에 삽입한다.

 

그리고 arr을 사전순으로 정렬한 뒤 출력해준다.

 

 

근데 생각해보니 HashSet을 이용해서 간단하게 풀 수 있을 것 같아서 HashSet으로 풀어봤고 시간이 단축됐다.

듣도못한 사람을 입력받아 삽입하고

 

보도못한 사람이 입력될 때 조건문으로 hs1.contains( tmp ) 가 참일 경우 arr에 tmp를 넣어준다.

 

그리고 정렬하고 출력하면 정답이다.

 

 

 

파이썬의 경우 집합자료형 set을 이용하고 집합 연산자인 & 교집합을 이용하면 쉽게 풀 수 있다.

 

 

-자바( 해시맵 사용 )

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.HashMap;
import java.util.StringTokenizer;

public class BJ1764 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		
		HashMap<String, Integer> hs1 = new HashMap<String, Integer>();
		for( int i=0; i<n; i++ ) hs1.put( br.readLine(), 1 );
		
		ArrayList<String> arr = new ArrayList<String>();
		int ans = 0;
		for( int i=0; i<m; i++ ) {
			String tmp = br.readLine();
			hs1.put( tmp, hs1.getOrDefault( tmp, 0 ) + 1 );
			if( hs1.get(tmp) > 1 ) {
				arr.add( tmp );
				ans++;
			}
		}
		Collections.sort( arr );
		
		StringBuffer sb = new StringBuffer();
		for( int i=0; i<arr.size(); i++ ) sb.append( arr.get(i) ).append( "\n" );
		
		System.out.println( ans+"\n"+sb );
	}
}

 

-자바( 해시셋 사용 ) 더 빠름

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.HashSet;
import java.util.StringTokenizer;

public class BJ1764_1 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		
		HashSet<String> hs = new HashSet<String>();
		for( int i=0; i<n; i++ ) hs.add( br.readLine() );
		
		ArrayList<String> arr = new ArrayList<String>();
		int ans = 0;
		String tmp = "";
		StringBuffer sb = new StringBuffer();
		for( int i=0; i<m; i++ ) {
			tmp = br.readLine();
			if( hs.contains( tmp ) ) {
				ans++;
				arr.add( tmp );
			}
		}
		
		Collections.sort( arr );
		for( int i=0; i<arr.size(); i++ ) sb.append( arr.get(i) ).append( "\n" );
		System.out.println( ans+"\n"+sb );
	}
}

 

 

-파이썬

import sys
n, m = map( int, input().split() )

nList = sys.stdin.read().splitlines()
a = set( nList[:n] )
b = set( nList[n:] )
res = list( a & b )
res.sort()
print( str( len(res) )+"\n"+"\n".join( i for i in res ) )