[알고리즘] 보석쇼핑 투포인터 (2020 카카오 인턴십)

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

 이것 또한 결국 못 풀었던 문제였다. 특정 조건을 만족하는 '구간'을 찾아야하는 문제이므로 투포인터기법을 활용해야한다.

 

 만약 투포인터 기법을 활용하지 않고 찾게 된다면 O(N ^ 2)의 시간이 걸리게 된다. 투포인터 기법 활용 시 O(N) 시간 만에 찾을 수 있다.

 

Solution

1. 우선 HashMap을 만들어서 보석의 이름을 키값으로 count라는 객체를 만든다.
2. 이 때 count의 사이즈는 총 보석 종류의 수가 된다.
3. 반복문을 돌린다.
   1. 현재 구간에 포함된 보석 종류의 수를 나타내는 gem_count가 총 보석 종류의 수 total_count와 동일하게 될 때까지 (즉 현재 구간에 모든 보석 종류가 포함될 때까지) end를 증가시키고 count(gem) 또한 1씩 증가시킨다. (이 때 gem_count는 증가시킨 count(gem)이 1일 때 최초방문으로 가정하고 증가시킨다.)
   2. gem_count가 total_count와 같을 때는 start를 증가시킨다. 이와 동시에 count(gem)을 1씩 감소 시킨다. (이 때 gem_count는 감소시킨 count(gem)이 0이 될 때 감소시킨다.)
   3. start 혹은 end를 증가시키고 현재 구간에 모든 종류의 보석들이 포함되어있다면 (gem_count == total_count) 최소 길이 min_length와 비교 후 end-start가 더 짧다면 min_length = end - start 가 된다.
   4. 만약 min_length와 end-start가 같을 때는 start < min_start 인 경우에 min_start = start, min_end = end가 된다.
   5. end가 배열의 끝에 왔고, 더 이상 start를 증가시키기 불가능한 상황일 때 반복문 종료시킨다.

 

import java.util.*;


class Solution {

	public static int[] solution(String[] gems) {
		int[] answer = new int[2];

		HashMap<String, Integer> count = new HashMap<>();

		for(String a : gems)
		{
			count.putIfAbsent(a, 0);
		}

		int total_count = count.size();

		int start = 0, end = 0;

		int min_start = Integer.MAX_VALUE, min_end = Integer.MAX_VALUE;
		int min_length = Integer.MAX_VALUE;

		int gem_count = 0;

		while(end < gems.length || start < gems.length)
		{
			//start 증가
			if(gem_count >= total_count && start <= end)
			{
				count.replace(gems[start], count.get(gems[start])-1);

				if(count.get(gems[start]) == 0)
					gem_count--;
				start++;
			}
			//end 증가
			else if(gem_count < total_count && end < gems.length)
			{
				count.replace(gems[end], count.get(gems[end])+1);

				//첫 방문
				if(count.get(gems[end]) == 1)
					gem_count++;
				end++;
			}


			if(gem_count == total_count)
			{
				//System.out.println(String.valueOf(end-1) + " "+start);
				if(min_length > end - 1 - start)
				{
					min_length = end - 1 - start;
					min_start = start;
					min_end = end - 1;
				}
				else if(min_length == end - 1 - start)
				{
					if(start < min_start)
					{
						min_length = end - 1 - start;
						min_start = start;
						min_end = end - 1;
					}
				}
			}

			if(end == gems.length && gem_count < total_count)
				break;
		}

		answer[0] = min_start+1;
		answer[1] = min_end+1;
		return answer;
	}

}