난이도

Silver 4

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력

2
baesangwook
ohhenrie

문제 검토

문제가 간단해보인다.
Set으로 풀어도 되지만 각 키에 대한 카운트를 하면 더 편할 것 같으므로 Map 구조를 사용하겠다.

풀이(python)

Java

import java.util.*;
import java.io.*;
//아이디어:
//HashMap을 사용해서 두번의 체크과정 동안 두번 다 체크된 key값들을 정렬하여 출력한다.
public class Main{
    //HashMap을 받을 변수 선언
    static Map<String,Integer> dic;
    //유동적인 어레이리스트를 선언
    static ArrayList<String> answer;
    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.valueOf(st.nextToken());
     int m=Integer.valueOf(st.nextToken());
     //HashMap과 ArrayList 할당
     dic=new HashMap<>();
     answer=new ArrayList<>();
     //HashMap에 value를 1로 할당
     for(int i=0; i<n; i++){
         st=new StringTokenizer(br.readLine(), " ");
         String tmp=st.nextToken();
         dic.put(tmp,1);
     }
     //만약 키를 갖고 있다면 갖고 있던 수에 +1
     for(int i=0; i<m;i++){
         st=new StringTokenizer(br.readLine(), " ");
         String tmp=st.nextToken();
         if(dic.containsKey(tmp)){
             dic.put(tmp,dic.get(tmp)+1);
         }
     }
     //Map.Entry로 HashMap을 하나씩 받음
     for(Map.Entry<String,Integer> entry:dic.entrySet()){
         //Value가 1보다 크면 두번정도 나온 것이므로 answer리스트에 add
         if (entry.getValue()>1){
             answer.add(entry.getKey());
         }
     }
     //새로운 배열에 형변환
     String[] answers=answer.toArray(new String[0]);
     //배열을 오름차순으로 정렬
     Arrays.sort(answers);
     System.out.println(answers.length);
     for(String s:answers){
         System.out.println(s);
     }
    }
}

#아이디어
#R과 D, 두 개의 함수밖에 존재하지 않으므로 함수에 따라 MODE를 변경해서 왼쪽으로 pop할지 오른쪽에서 pop할지를 결정한다.
#만약 큐기 비면 error를 출력
#시간 복잡도
#reverse로 배열을 거꾸로 돌리지 않고 사용하는 건 pop 밖에 없으니 충분히 가능하다고 보임
#이중 for문이 하나도 없으므로 총 O(n)의 수행시간

걸린 시간

09:47

총평

파이썬에서처럼 defaultdict 같은 자료구조가 없어서 조금 불편했다.
containsKey를 하는 과정을 스킵하고 싶은데 그렇게 하지 않으면 getkey에서 오류가 나기 때문에 어쩔 수 없었다.

그래도 hashable한 값을 탐색하는 과정은 O(1) 밖에 걸리지 않기 때문에 부담이 되지 않을 것 같다.