HashMap, HashSet

프로그래머스 2020 카카오 인턴십 보석 쇼핑을 Java로 풀어보았다.
HashMap과 HashSet을 써본 적이 없어서 처음에 풀었을 때는 정확성 테스트는 다 통과했는데 효율성을 다 틀렸다. 이중 for문을 이용해서 제일 첫 번째 원소부터 뒤의 원소까지 쭉 탐색하며 가장 짧은 구간을 갱신해주는 방식으로 풀었다. 다 풀고 나니 10만 개를 2중으로 돌리면 100억 번이 나온다. 당연히 안 된다. ㅎㅎ

문제 링크만 올려둔다.
https://programmers.co.kr/learn/courses/30/lessons/67258

---

HastSet만 이용해서 풀어보기

그러면 틀린다. 정확성 테스트는 다 통과할 수 있지만 효율성 테스트를 2개 빼고 다 틀리더라.
HastSet만 이용해서 풀었을 때는 투 포인터 알고리즘을 이용해서 풀었는데 좀 하등한 코드가 되어버렸다. low와 high를 움직이며 매번 low와 high 사이에 있는 String[] gems 일부를 HashSet으로 변환하여 사이즈 비교를 했다. 아마도 low와 high를 움직일 때마다 String 배열을 HashSet으로 변환하는 작업이 시간 초과를 유발했던 듯하다.

그렇다면 어떻게 코드 개선을 할 수 있을까?

---

HashMap 이용하기

0번 index부터 for문을 통해 매번 Queue에 gem을 추가해주고, 이 Queue의 선두에 위치한 gem이 HashMap에 중복이 있다면 하나만 남기고 다 제거해주는 작업을 해나간다. 이 작업을 진행하며 HashMap도 보석 종류당 몇 개가 있는지 각각 Key와 Value로 업데이트 해준다.

이에 해당하는 코드는 아래와 같다.

for(String gem: gems){
       q.add(gem);
       hm.put(gem, hm.getOrDefault(gem,0)+1);
       
       while(true){
                String tmp = q.peek();
                if(hm.get(tmp)>1){
                    hm.put(tmp, hm.get(tmp)-1);
                    q.poll();
                    tmp_start++;
                }
                else    break;
            }
       ...

이 HashMap의 size가 보석 전체 종류를 담은 HashSet의 size와 일치할 때는 start index 값을 현재 index 값으로 갱신해주며 Queue의 size가 곧 구간의 길이를 의미하므로 recent min_distance보다 더 작은 Queue의 size면 min_distance도 갱신해주면 된다.

이에 해당하는 코드는 아래와 같다.

if(hm.size()==kinds.size() && min_distance>q.size()){
           min_distance = q.size(); // 구간 길이 갱신해주기
           start = tmp_start; // 시작점 갱신해주기
       }

위의 두 작업은 for문을 통한 전체 String[] gems 배열을 탐색하는 동안 함께 이루어지는 작업이다. 합쳐주면 아래와 같은 코드다.

for(String gem: gems){
       q.add(gem);
       hm.put(gem, hm.getOrDefault(gem,0)+1);

       while(true){
           String tmp = q.peek();
           if(hm.get(tmp)>1){
               hm.put(tmp, hm.get(tmp)-1);
               q.poll();
               tmp_start++;
           }
           else    break;
       }

       if(hm.size()==kinds.size() && min_distance>q.size()){
           min_distance = q.size();
           start = tmp_start;
       }
   }

---

전체 코드는 아래와 같다.

int[] solution(String[] gems) {
        HashSet<String> kinds = new HashSet<>(Arrays.asList(gems));
        HashMap<String, Integer> hm = new HashMap<>();
        Queue<String> q = new LinkedList<>();

        if(kinds.size()==1) return new int[]{1,1};

        int start=0, tmp_start=0;
        int min_distance = Integer.MAX_VALUE;

        for(String gem: gems){
            q.add(gem);
            hm.put(gem, hm.getOrDefault(gem,0)+1);

            while(true){
                String tmp = q.peek();
                if(hm.get(tmp)>1){
                    hm.put(tmp, hm.get(tmp)-1);
                    q.poll();
                    tmp_start++;
                }
                else    break;
            }

            if(hm.size()==kinds.size() && min_distance>q.size()){
                min_distance = q.size();
                start = tmp_start;
            }
        }

        return new int[]{start+1, start+min_distance};
    }

오늘 배운 것

1. HashSet은 Set Interface 의 구현체 중 하나다.
2. HashMap은 Map Interface 의 구현체 중 하나다.
3. 위 두 줄로 요약하긴 너무 짧지만 다 쓰자니 길어서 나중에 자료구조에 대해 공부한 걸 정리하는 글을 작성해봐야겠다.

---

2022.03.01 재시도 ( 실패 )

다시 풀었는데 또 틀렸다. 효율성 테스트를 4개밖에 통과하지 못했고 기존 풀이로는 도저히 안 될 것 같아서 다른 사람 풀이를 참고했다.

처음에 풀었던 이중 for문 풀이는 최대 입력 개수만 생각해봐도 몇십억 번 도는 거 알 수 있으니까 진즉에 풀이 방향을 바꿨어야 하는데 아직도 하수 짓을 한다... 그래 나는 하수니까

투 포인터를 이용해서 왼쪽 커서와 오른쪽 커서를 옮겨가며, 오른쪽 커서가 마지막 지점을 때리면 멈추도록 했다. 그럼 아무리 for문이 많이 돌아봤자 최대 10만 번밖에 안 도니까 효율성 테스트도 문제 없다.

커서 이동

왼쪽 커서를 이동시킬 때 현재 구간이 모든 보석의 종류를 다 커버할 때만 실행해주는 것이 주요했던 것 같다.
만약 모든 종류를 다 커버하지 못하는데 왼쪽 커서를 이동시키게 되면 아무런 의미없는 구간만을 만들어내게 되기 때문이다.

아래는 내가 제출한 코드다.

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.HashMap;

public class Jewelry {
    static HashSet<String> types = new HashSet<>();
    static HashMap<String, Integer> map = new HashMap<>();

    static int[] solution(String[] gems) {
        getTypes(gems);
        int typeSize = types.size();
        if(typeSize==1) return new int[]{1, 1}; // 종류 하나밖에 없으면 바로 (1,1) 리턴

        int gemsLen = gems.length;
        if(typeSize==gemsLen) return new int[]{1, gemsLen}; // 종류 수랑 전체 보석 개수 똑같으면 처음부터 끝까지 바로 반환

        int start=0, end=0; // 정답용
        int left=0, right=0; // 검사용
        int len = Integer.MAX_VALUE;

        while(true){
            if(map.size()==typeSize){
                map.put(gems[left], map.get(gems[left])-1);
                if(map.get(gems[left])==0)
                    map.remove(gems[left]);
                left++; // 왼쪽 커서 옮겨주기
            }
            else if(right==gemsLen) // 끝까지 갔으면 종료
                break;
            else
                map.put(gems[right], map.getOrDefault(gems[right++], 0) + 1); // 오른쪽 커서 옮겨주기

            if(right-left < len && map.size()==typeSize){ // 새로운 구간 찾으면 갱신해주기
                len = right - left;
                start = left + 1; // 0부터가 아니라 1부터니까 1 추가
                end = right; // 오른쪽 커서는 이미 한 칸 커졌으니까 놔둠
            }
        }

        return new int[]{start, end};
    }

    static void getTypes(String[] gems){
        types.addAll(Arrays.asList(gems));
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] gems = {"A", "B" ,"B", "C", "A", "B", "C", "A","B","C"};
        int[] answer = solution(gems);
        bfw.write(answer[0] + " " +answer[1]);
        bfw.close();
    }
}

---

역시 제자리 걸음. 좀 더... 절박하게 하자. 제발...!