[프로그래머스] 해시 완주하지 못한 선수(Java)

 

🔥DAY +7 (많이 쉬다 돌아온..)

 

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

코딩테스트 연습 - 완주하지 못한 선수

 

> 문제가 보고 싶다면 클릭!

 

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예participantcompletionreturn

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

---

 

🔥 [로직]

검색의 효율을 위해 HashMap을 이용한다. (내가 정리한 HashMap)

1. 마라톤을 완주한 선수들의 이름을 key, 동명이인을 알기 위한 이름별 카운트 수를 value로 하는 HashMap 자료구조를 생성한다.

(이때의 시간복잡도 : O(n))

 

2. 마라톤 참여 선수명단을 차례로 확인하면서 값이 있는경우 1씩 빼주고,

값이 없거나 0인 경우 완주하지 못한 것이기 때문에 그 선수명을 리턴해준다. 

 

🔥 [최종 코드]

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        for(String c : completion) {
            if(map.get(c) == null) {
                map.put(c,1);
            } else {
                map.put(c, map.get(c)+1);
            }
        }
        
        for(String p : participant) {
            System.out.println(map.get(p));
            if(map.get(p) == null || map.get(p) == 0) {
                return p;
            } else {
                map.put(p, map.get(p)-1);
            }
        }
       
        return "";
    }
}

 

🔥 [소감]

문제를 보자마자 의외로 쉽겠는데?라는 생각을 했다. (ㅠㅠ)

ArrayList에서 contains함수를 쓰면 쉽게 리스트끼리의 비교가 가능하기 때문에 주저없이 짰던 것 같다. 

(ㅠㅠ)

//기존 코드 - 효율성 0점

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> cList = new ArrayList(Arrays.asList(completion));
        for(String p : participant) {
            if(cList.contains(p) == false) {
                return p;
                
            } else {
                // System.out.println("포함행");
                cList.remove(p);
            } 
        }
       
        return answer;
    }
}

그런데 효율성이 0점이 나왔다 ㅠㅠ

ㅠㅠ 효율성이 0점이다. 하나라도 맞았다고 해주지..

애초에 효율성이 다 0점이라는게 내가 선택한 ArrayList방식이 잘못된 것 같다는 생각이 들어서 다시 찾아보니..

문제에 떳떳하게 "해시"라고 적혀져있었다.ㅋ 문제를 제대로 봐야하는 이유를 또 한번 몸소 체험한듯..ㅎ

 

Hash에 대해 잘 몰랐고 그 중요도또한 무시하고 있었어서.. 결국 2시간에 걸쳐 해시를 공부했다 ㅠ 공부하면서 시간 효율을 높일 수 있는 최대한 활용하면 좋을 자료구조인지 알게 됐다. 자주 써야지ㅎㅎ

 

또한 다른 사람의 코드를 보면서 map.get(c)가 null일 경우와 아닌경우로 나눴던 기존 코드의 라인을 좀 더 줄일 수 있는 방법도 생각하게 됐는데, getOrDefault 함수를 쓰는게 좋은 것 같다!

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

이렇게! 

---

 

코테 준비를 본격적으로 시작한지 얼마 되지 않아 코드에 미흡한 점이 많을 수 있습니다. 
부족한 점 피드백 주시면 앞으로의 포스팅에 반영하겠습니다! 봐주셔서 정말 감사합니다 :)
-budtree