[Programmers] 보석 쇼핑

문제

 

2020 카카오 인턴십 > 보석 쇼핑

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

 

 

아이디어

 

이번 문제는 최적화하는 방법이 가장 중요하게 생각될 아이디어로 보입니다.

 

기본적으로 gems의 배열 크기가 최대 100,000까지 존재할 수 있기 때문에 DFS, BFS와 같은 알고리즘을 사용하면 시간이나 메모리가 펑펑 터지게 됩니다.

 

최대로 가능한 시간 복잡도는 O(nlogn) 정도이기 때문에 최대한 반복문 한 번만 사용하여 문제를 푸는 방법을 생각해야 됩니다.

 

제가 생각한 방법은 다음과 같습니다.

 

1. 결과로 나오게 될 구간 값을 [left, right]라고 가정하고 left, right값 모두 0부터 시작

2. right값을 증가시키며 보석 개수를 증가

3. 만약 모든 종류의 보석이 포함되는 구간이 되면 right값 증가를 중단하고 left값을 증가시키며 보석 개수를 감소

4. 모든 종류의 보석이 포함되는 구간에서 벗어나거나 left값이 right값보다 커지면 left값 증가를 중단

5. right가 gems배열의 최대 길이에 도달할 때까지 2~4를 반복

 

위의 방법을 사용하며 보석 종류를 카운팅 했던 방법은 만약 보석 개수를 증가시켰는데 보석 개수가 1개이면 새로운 종류가 추가된 것이라고 생각했고, 만약 보석 개수를 감소시켰는데 보석 개수가 0개이면 한 종류의 보석이 모두 사라졌다고 생각했습니다.

 

말씀드린 모든 상황을 코드로 구현하면 다음과 같습니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Map<String, Integer> map = new HashMap<String, Integer>(); // 현재 범위에 포함된 보석의 개수를 저장하는 map
        for(int i=0; i<gems.length; i++) {
        	map.put(gems[i], 0); // 보석의 개수를 모두 0으로 초기화
        }
        
        int total = map.size(); // 전체 보석종류 개수
        int count = 0; // 현재 보석종류 개수
        int left = 0; // 현재 범위의 가장 왼쪽 인덱스
        int right = 0; // 현재 범위의 가장 오른쪽 인덱스
        int res[] = new int[2];
        res[1] = Integer.MAX_VALUE; // 구간의 길이를 가장 크게 만들기 위해 MAX값으로 초기화
        
        while(right < gems.length) { // 가장 오른쪽 인덱스값이 gems배열의 끝에 도달할때까지 반복
        	String gem = gems[right];
        	map.put(gem, map.get(gem)+1); // 보석 개수 추가
        	
        	if(map.get(gem) == 1) { // 새롭게 추가된 보석인 경우
        		count++; // 보석종류 개수도 추가
        	}
        	
        	if(count == total) { // 현재 보석종류 개수와 전체 보석종류 개수가 동일할 경우
        		while(left <= right) { // 왼쪽 인덱스가 오른쪽에 인덱스에 도달할때까지 반복
        			if(res[1] - res[0] > right - left) { // 저장되어 있던 구간의 길이보다 더 짧을 경우
        				res[1] = right+1;
        				res[0] = left+1;
        			}
        			
        			left++;
        			map.put(gems[left-1], map.get(gems[left-1])-1); // 좌측 범위가 오른쪽으로 이동되었기 때문에 기존에 있던 위치의 보석은 개수 빼기
        			if(map.get(gems[left-1]) == 0) { // 해당종류의 보석이 모두 사라졌을 경우
        				count--; // 보석종류 개수 차감
        				break; // 현재 보석종류 개수와 전체 보석종류 개수가 동일하지 않으므로 break
        			}
        		}
        	}
        	
        	right++;
        }
        
        return res;
    }
}

 

 

 

읽어주셔서 감사합니다.