백준 1764 - 듣보잡

C++

1764 번 - 듣보잡

문제

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

접근 방법

명단과 수를 보자마자 Hash Map이 떠올라 적용하였다.
듣도 못한 사람의 명단과 보도 못한 사람의 명단을 함께 받아, Map에 넣는다.
기존에 존재하던 명단의 이름이 발견되면 value값을 1 증가시킨다.
이후 value값이 2인 명단을 찾는다.

구현

unordered_map(Hash Map)을 통하여 입력받는 명단을 저장한다.
이름을 key, 명단의 수를 value로 선언한다.
처음 받는 이름이면 value 값을 1로, 중복되는 이름을 발견시 value를 1증가.

코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int n, m;
unordered_map<string, int> name;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	string temp;
	// 입력
	for (int i = 0; i < n + m; i++) {
		cin >> temp;
		if (name.count(temp) == 0) {			//처음 받는 명단의 이름
			name.insert(make_pair(temp, 1));
		}
		else {									//한번 더 발견
			name[temp]++;
		}
	}
	// 계산
	int count = 0;
	vector<string> result;
	for(auto iter = name.begin(); iter != name.end(); iter++)	//iterator를 사용하여 map을 탐색
		if (iter->second == 2) {								//듣도 보도 못한 이름 발견
			count++;
			result.push_back(iter->first);
		}

	// 출력
	cout << count << "\n";
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result.at(i) << "\n";
	}
	return 0;
}

2022/03/02 Java 풀이

import java.util.*;
import java.util.Map.Entry;
import java.io.*;

public class Main {
	static int n, m, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	Map<String, Integer> map = new HashMap<>();

    	String str;
    	for(int i = 0; i < n + m; i++) {
    		str = br.readLine();
    		map.put(str, map.getOrDefault(str, 0) + 1);	// map에 담는다.
    	}

    	List<Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
		// map의 value가 2이상인 값들은 '듣도보도' 못한 듣보잡이다.
    	int count = 0;
    	List<String> rst = new ArrayList<>();
    	for(Entry<String, Integer> entry : list) {
    		if(entry.getValue() > 1) {
    			count++;
    			rst.add(entry.getKey());
    		}
    	}

    	Collections.sort(rst);	// 사전순 정렬

    	System.out.println(count);
    	for(String r : rst) {
    		System.out.println(r);
    	}

    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

이전에 프로그래머스에서 푼 Map 문제와 비슷하여 쉽게 풀 수 있었다.

개선할 점

탐색으로도 푸는 법을 생각해본다. 바이너리 서치