Menu

Subscribe

[JAVA/프로그래머스] 해시_완주하지 못한 선수: 링크드리스트와 해시의 효율성 차이

HEESOO on Programmers

👊 첫 번째 도전

1. 설계

  1. 전체 마라톤 선수 participant를 링크드리스트에 저장한다.
  2. 완주한 선수들의 배열 completion을 처음부터 순회하며 링크드리스트에 동일한 값을 삭제한다.
  3. 마지막 남은 하나를 answer로 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.LinkedList;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        LinkedList people=new LinkedList();
        for(String s:participant){
            people.add(s);
        }
        for(String s:completion){
            people.remove(s);
        }
        if(!people.isEmpty()){
            answer=(String)people.get(0);
            return answer;
        }
        return answer;
    }
}

3. 결과

실행결과 효율성에서 모두 실패를 얻었다.

4. 문제점

링크드리스트보다 더 효율적인 자료구조를 적용해야한다.

(ʃƪ¬‿¬) 두 번째 도전

1. 설계

  1. 해시맵을 선언하여 key는 participant의 이름, value는 기본값이 1이고, 동명이인이 존재할 경우 +1한다.
  2. completion을 순회하며 해쉬맵에 존재할 경우 삭제한다. 이때 동명이인이 있다면 value를 -1하여 한 명만 지운다.
  3. 해쉬맵에 남은 단 한명을 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.HashMap;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> hash=new HashMap<String,Integer>();
        for(String s:participant){
            if(hash.get(s)==null){
                hash.put(s,1);
            }
            else{
                hash.replace(s,hash.get(s)+1);
            }
        }
        for(String s:completion){
            if(hash.get(s)==1){
                hash.remove(s);
            }
            else{
                hash.replace(s,hash.get(s)-1);
            }
        }
        for(String s:hash.keySet()){
            if(hash.get(s)==1){
                answer=s;
            }
        }
        return answer;
    }
}

3. 결과

실행결과 🤟 성공 🤟

👏 해결 완료!

문제를 보자마자 익숙한 링크드리스트가 먼저 떠올랐는데, 앞으로는 해쉬도 염두해두도록 하자.