[코딩테스트 #2] 완주하지 못한 선수(해시) level1 - java

프로그래머스에 있는

https://programmers.co.kr/learn/courses/30/lessons/42576    문제이다. 

 

처음에 해당 문제를 읽었을 때 참여자(participant)와 완주자(complection)를 비교하여 참여자의 목록에서 완주자의 이름을 하나씩 빼는 방법을 생각했었다.

 

그래서 

 

1. 참여자 리스트에서 완주자를 하나씩 빼고 결국 남은 하나가 완주하지 못한 사람이라고 생각하여 코딩을 했다.

 

결과는 50점

 

정확성은 100%였지만 효율성부분에서 0%를 받았다.

 

효율성이란 부분이 뭘까? 속도적인 측면에 문제라고생각했다.

2. 처음에 참여자 리스트에서 완주자를 하나씩 뺀거를 반대로 완주자 리스트에서 참여자 리스트를 비교하여 

완주자 리스트에 없는 사람이 들어오면 그사람이 낙오자라고 생각하고 코딩했다.

 

하지만 결과는 똑같이 50점

 

슬슬 막막해졌다. 그래서 검색을 좀 해봤고 새로운 배열을 채워넣는 방식으로 해보라는 추천을 받았다.

 

3. 세 번째로 시도한 방법은 새로운 arraylist를 만들고 참여자와 완주자를 비교하여 하나씩 채워넣었다. 동명이인이 나오면 동명이인을 처리하는 로직을 만들어 해결하였고 

 

결과는 60점 효율성 테스트 5개 중 하나를 통과했다.

 

 

4. 먼저 해결한 친구가 효율성문제는 처음 문제 해결방법을 생각하기 힘들다며 힌트를 줬는데 Sort를 해보라는 것이었다.

 

그래서 생각을 해보니 다음 그림처럼 문제를 해결할 수 있을 거 같았다.

 

 

정렬 후 비교

이런식으로 정렬해서 비교를 한다면 이중 반복문을 쓰지 않고도 한 번의 반복문으로 찾아낼 수 있을 거 같았다.

 

그래서 작성한 코드가 바로 이 것

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;


class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        int i = 0;
        
        ArrayList <String> arrayList = new ArrayList<>(Arrays.asList(participant));   // array list로 변환
        ArrayList <String> arrayList2 = new ArrayList<>(Arrays.asList(completion));   // array list로 변환
    
        Collections.sort(arrayList);
        Collections.sort(arrayList2);
    
        while(true){
                if(arrayList2.get(i).equals(arrayList.get(i))){
                    // 같으면 다음으로가야되는데
                } else{
                    return arrayList.get(i);
                }
                if(i == arrayList2.size()-1){
                    return arrayList.get(i+1);
                }
                i++;
            }

      
    }
}

arraylist로 변환한 배열을 sort하는 내장 메소드를 이용하여 해결하였다.

 

 

뿌듯

 

문제를 해결하고 다른 분들의 답을 봤다.

 

제일 위에 있던 것이 HashMap을 이용한 거였는데 hashmap자체를 내가 잘 안쓰다보니 처음봤을 때 코드가 이해가 가지않았다. 

 

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

 

 

이게 해당 코드인데 너무 대단해 보였다. 

이 분이 한 코드를 분석해보면 HashMap 객체를 만들고 반복문을 통해 hashmap에 키값으로 이름을 밸류값으로 값이 존재할 때는 그 값을 없으면 0을 넣고 거기에 +1을 한다. 

 

그럼 처음 hash맵에는 {A, 0} {B, 0}  ... 이런식으로 채워지다가 동명이인이 발견되면 hashmap은 중복저장이 되지 않기 때문에 {A, 1} {B, 0} 이 될 것이다. 이렇게 동명 이인의 수만큼 숫자가 상승하게 되고 처음 참여자를 전부 저장하고 나면

 

{A, 10} {B, 5} {C, 0}  ... 이런식으로 구성이 될 것이다.

 

완주자의 for을 돌리면 위와 마찬가지로 숫자가 -1씩 동명이인의 수에 따라 진행되고 전부 수행되면

 

{A, 0} {B, 0} {C, 1}  ... 이것처럼 하나의 key 값만 value를 1 가지게 될 것이다.

 

그 값을 조회해서 return해주면 끝.

 

너무 훌륭했다. 

 

나도 hashmap에 대한 활용을 나중에 해봐야겠다.