[프로그래머스] 2020 카카오 인턴십 > 보석 쇼핑 - JAVA

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

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

오늘은 프로그래머스에서 제공한 코딩테스트 문제 중 2020년 카카오 인턴십 문제를 풀어보았다.

이 문제는 Level 3에 해당되며, 슬라이딩 윈도우 알고리즘을 활용해야 한다.

슬라이딩 윈도우 알고리즘의 설명은 따로 작성하여 올리겠다.

가장 먼저 문제의 풀이를 함께 확인해보자.

 

우선 메인 코드에 들어가기 앞서, 변수에 대하여 이야기 해보겠다.

int min = gems.length;

HashSet<String> gemType = new HashSet<>();

for(int i = 0; i<gems.length; i++) gemType.add(gems[i]);

if(gemType.size() == 1) return new int[]{1,1};
if(gemType.size() == min) return new int[]{1, gems.length};

HashMap<String, Integer> map = new HashMap<>();
        
int left = 0, right = 0;
int prev = -1;

우리가 가지는 최소값(min)은 입력받은 보석 배열의 크기로 초기화해준다.

슬라이딩 윈도우 알고리즘에서 사용할 일정한 범위값은 보석 종류의 갯수이다.

따라서 gemType이라는 이름의 HashSet 타입 변수를 설정해준다.

슬라이딩 윈도우 알고리즘에서 사용할 hashMap 타입의 배열을 초기화 해준다.

hashMap에서 보석의 이름을 키값으로 하고, 가장 왼쪽 인덱스와 오른쪽 인덱스 사이에 포함된 각 보석의 갯수를 값으로 갖는다.

슬라이딩 윈도우 알고리즘에서 왼쪽인덱스 값과 오른쪽 인덱스 값을 0으로 초기화 한다.

 

아래의 예시를 들어 함께 보자.

예시 테스트 케이스

map 배열에 size가 보석 타입 갯수와 갖지 않다면 계속하여 right 인덱스 값을 늘려 map 배열에 추가시킨다.

그렇다면 right 인덱스 값이 7이 되었을 때 우리가 원하는 모든 보석을 map 배열에 담았다고 볼 수 있다.

그러나, 우리가 원하는 것은 길이가 가장 짧은 것이다.

그렇다면 우리는 이제부터 left 값을 비교하여 Map에 존재하는 gems[left] 의 갯수가 1을 초과하는지 확인 해야한다.

만약 1을 초과한다면 다음 인덱스 중에 포함되기 때문에 left 값을 증가 시켜준다. left 값이 증가될 때는 right 값이 증가되지 않도록 한다.

또한 같은 right번째 값이 map에 추가 되지 않도록 prev 변수를 이용해준다.

이러한 방법을 계속하여 사용하면 min값을 얻을 수 있다.

이제 완전한 코드를 함께 보도록 하자.

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int min = gems.length;
        HashSet<String> gemType = new HashSet<>();
        for(int i = 0; i<gems.length; i++) gemType.add(gems[i]);
        if(gemType.size() == 1) return new int[]{1,1};
        if(gemType.size() == min) return new int[]{1, gems.length};
        
        HashMap<String, Integer> map = new HashMap<>();
        
        int left = 0, right = 0;
        int prev = -1;
        while(right < gems.length){
            if(prev == -1 || prev != right) {
                map.put(gems[right], map.get(gems[right]) != null ? map.get(gems[right])+1 : 1);
                prev = right;
            }
            if(map.size() == gemType.size()){
                if(map.get(gems[left]) > 1){
                    map.put(gems[left], map.get(gems[left])-1);
                    left++;
                    continue;
                }
                
                if(right - left == gemType.size()-1){
                    answer[0] = left+1; answer[1] = right + 1;
                    break;
                }
                
                if(min > right - left) {
                    min = right - left;
                    answer[0] = left+1; answer[1] = right+1;
                }
            }
            right++;
        }
        return answer;
    }
}