2020 카카오 인턴십 - 보석쇼핑 java

코딩테스트 연습 - 보석 쇼핑

1. 보석의 가짓수를 찾기

---

모든 종류의 보석을 포함하는 구간을 찾아야 한다. 따라서 일단 보석 배열을 순차탐색해서, 보석이 총 몇 가지 종류로 이루어져 있는지를 찾아야 한다. 간단히 HashMap 을 이용해서 보석의 총 가지수를 구했다. 

int jeweleryCount = 0;

public void getJeweleryCount(String[] gems) {
    HashMap<String, Boolean> hashMap = new HashMap<>();
    for (String gem : gems) {
        if (!hashMap.containsKey(gem)) {
            jeweleryCount++;
            hashMap.put(gem, false);
        }
    }
}

 

2.  가장 짧은 구간 찾기

---

슬라이딩 윈도우를 활용하여 모든 보석을 포함하는 구간을 찾을 수 있다. 일단 가장 먼저 (0,0) 구간을 슬라이딩 윈도우의 시작 범위로 잡는다.

그 다음 슬라이딩 윈도우가 모든 보석을 포함하도록, 윈도우를 한 칸씩 늘려간다. 

public int[] getAnswer(String[] gems) {
    int[] ret = new int[2]; //반환 구간
    HashMap<String, Integer> hashMap = new HashMap<>();
    int count = 1;
    ret[1] = 999999;
    int start = 0;
    int end = 0;
    hashMap.put(gems[0], 1);
    //가장 먼저 슬라이딩 윈도우가 모든 보석을 포함하도록 확장한다.
    while (count < jeweleryCount && end < gems.length - 1) {
    	//윈도우를 오른쪽으로 확장해가며, 보석을 추가한다.
        end++;
        //윈도우가 해당 보석을 포함하지 않고 있으면 보석 종류 추가
        if (!hashMap.containsKey(gems[end]) || hashMap.get(gems[end]) == 0) {
            count++;
            hashMap.put(gems[end], 1);
        } 
        //윈도우가 해당 보석을 포함할 시
        else {
            hashMap.put(gems[end], hashMap.get(gems[end]) + 1);
        }
    }
}

 

슬라이딩 윈도우가 모든 보석을 포함하도록 초기화했으면, 이제 범위를 점차 좁히면 된다.

 

1. 슬라이딩 윈도우의 시작 부분을 start 라고 했을 때, start에 해당하는 보석을 뺐을 때 모든 보석을 포함하지 않으면 윈도우의 끝을 확장시킨다. 

2. 만약 start 보석을 뻈을 때도 모든 보석을 포함하면 해당 보석을 빼고, start 를 1 증가시킨다.

 

while (true) {
    if (end - start < ret[1] - ret[0]) {
        ret[0] = start;
        ret[1] = end;
    }
    //만약 왼쪽 보석을 뺏을 때 모든 보석을 포함하지 않으면
    if (hashMap.get(gems[start]) - 1 == 0) {
        //윈도우를 오른쪽으로 확장할 수 있을 때
        if (end < gems.length - 1) {
            end++;
            hashMap.put(gems[end], hashMap.get(gems[end]) + 1);
        }
        //더 이상 오른쪽으로 확장할 수 없으면 바로 탈출
        else {
            break;
        }
    }
    //왼쪽 보석을 빼도 모든 보석을 포함하면
    else {
        hashMap.put(gems[start], hashMap.get(gems[start]) - 1);
        start++;
    }
}

이 때 슬라이딩 윈도우는 항상 모든 보석을 포함하고 있으므로, 가장 짧거나, 왼쪽에 있는 범위로 계속해서 갱신시켜준다.

 

전체 코드

---

package per.jongho;

import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;

public class JewelryShopping {
    int jeweleryCount = 0;

    public static void main(String[] args) throws IOException {
        JewelryShopping jewelryShopping = new JewelryShopping();
        String[] gems = {"ZZZ", "YYY", "NNNN", "YYY", "BBB"};
        System.out.println(Arrays.toString(jewelryShopping.solution(gems)));
    }

    public int[] solution(String[] gems) {
        getJeweleryCount(gems);
        return getAnswer(gems);
    }

    public int[] getAnswer(String[] gems) {
        int[] ret = new int[2]; //반환 구간
        HashMap<String, Integer> hashMap = new HashMap<>();
        int count = 1;
        ret[1] = 999999;
        int start = 0;
        int end = 0;
        hashMap.put(gems[0], 1);
        //가장 먼저 슬라이딩 윈도우가 모든 보석을 포함하도록 확장한다.
        while (count < jeweleryCount && end < gems.length - 1) {
            end++;
            if (!hashMap.containsKey(gems[end]) || hashMap.get(gems[end]) == 0) {
                count++;
                hashMap.put(gems[end], 1);
            } else {
                hashMap.put(gems[end], hashMap.get(gems[end]) + 1);
            }
        }
        while (true) {
            if (end - start < ret[1] - ret[0]) {
                ret[0] = start;
                ret[1] = end;
            }
            //만약 왼쪽 보석을 뺏을 때 모든 보석을 포함하지 않으면
            if (hashMap.get(gems[start]) - 1 == 0) {
                //윈도우를 오른쪽으로 확장할 수 있을 때
                if (end < gems.length - 1) {
                    end++;
                    hashMap.put(gems[end], hashMap.get(gems[end]) + 1);
                }
                //더 이상 오른쪽으로 확장할 수 없으면 바로 탈출
                else {
                    break;
                }
            }
            //왼쪽 보석을 빼도 모든 보석을 포함하면
            else {
                hashMap.put(gems[start], hashMap.get(gems[start]) - 1);
                start++;
            }
        }
        ret[0]++;
        ret[1]++;
        return ret;
    }

    public void getJeweleryCount(String[] gems) {
        HashMap<String, Boolean> hashMap = new HashMap<>();
        for (String gem : gems) {
            if (!hashMap.containsKey(gem)) {
                jeweleryCount++;
                hashMap.put(gem, false);
            }
        }
    }
}