LV1. 완주하지 못한 선수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=java

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

오랜만에 굳은 머리 풀겸 프로그래머스를 켰습니다.

고득점 kit 해쉬 문제입니다.

마라톤 참여자인 participant가 존재하고 완주자인 completion이 존재합니다.

주의해야 할 점은 동명이인이 있다는 점 입니다.

private String solution(String[] participant, String[] completion) {
        Map<String, Integer> runner = new HashMap<>();
        Map<String, Integer> winner = new HashMap<>();
        for (String s : participant) {
            runner.put(s, runner.getOrDefault(s, 0) + 1);
        }

        for (String s : completion) {
            winner.put(s, winner.getOrDefault(s, 0) + 1);
        }

        for (String s : participant) {
            if(winner.getOrDefault(s,0) != runner.get(s)) return s;
        }

        return "";
    }

처음 풀이입니다.

입출력은 맞지만 효율성에서 틀린 문제입니다.

10만개가 최대여서 시간 효율성인 3N = 300_000개를 생각했었는데 공간효율성은 제가 미쳐 생각하지 못해서 조금 헤맸었습니다.

private String solution(String[] participant, String[] completion) {
        Map<String, Integer> runner = new HashMap<>();
        for (String s : participant) {
            runner.put(s, runner.getOrDefault(s, 0) + 1);
        }

        for (String s : completion) {
            runner.put(s, runner.get(s)-1);
        }

        for (String s : runner.keySet()) {
            if (runner.get(s)!=0) return s;
        }

        return "";
    }