LV1. 완주하지 못한 선수

문제

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

프로그래머스

 

풀이

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

 

고득점 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 "";
    }

 

이후 풀이인데, Map을 두개 사용하지 않고 하나만 사용하니 효율성도 통과하는 모습을 보여줍니다.

 

 

 

다들 저와같은 실수 하지 마시고 문제 잘 읽고 효율성 잘 체크해봐요!