[BaekJoon] #10546 - 배부른 마라토너 [Java][C++]

문제 링크

---

1. 아이디어

$N$명이 마라톤에 참여하며 $N - 1$명이 완주했을 때 완주하지 못한 한 명을 찾는 문제로 동명이인이 있을 수 있어서 맵 자료구조를 활용해서 이름을 키, 인원을 값으로 설정해서 참여한 사람을 더하고 완주한 사람을 뺐다. 그러면 맵에서 값이 1인 사람이 유일하게 존재하게 되며 해당 사람이 완주하지 못한 사람이 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        for (int i = 0; i < n - 1; i++) {
            String s = br.readLine();
            map.put(s, map.get(s) - 1);
        }

        for (Map.Entry<String, Integer> e : map.entrySet()) {
            if (e.getValue() == 1) {
                System.out.println(e.getKey());
                return;
            }
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    unordered_map<string, int> mp;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        mp[s]++;
    }
    for (int i = 0; i < n - 1; i++) {
        string s;
        cin >> s;
        mp[s]--;
    }

    for (auto& [k, v] : mp) {
        if (v == 1) {
            cout << k;
            return 0;
        }
    }
}

---