공부 기록

문제 조건 

1. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 연속된 구간을 찾아서 구매
2. 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 리턴

연속된 구간을 보는 것이기 때문에 투 포인터를 사용하여 풀면 된다고 생각했다.

진열대 위치를 쭉 훑으면서 맵에 저장되어있는 보석의 수가 1보다 크면 시작 위치를 하나씩 땡기는 방법으로 생각하고 문제를 풀었다. 

import java.util.*;
class Solution {
	public int[] solution(String[] gems) {
		int[] answer = new int[2];

		HashMap<String, Integer> selects = new HashMap<String, Integer>();
		HashSet<String> allGems = new HashSet<String>();

		int length = gems.length;
		answer[0] = 1;
		answer[1] = length;

		for (int i = 0; i < length; i++) {
			allGems.add(gems[i]);
		}
		int size = allGems.size();

		int start = 0;
		for (int end = 0; end < length; end++) {
			selects.put(gems[end], selects.getOrDefault(gems[end], 0) + 1);

			while (selects.getOrDefault(gems[start], 0) > 1) {
				selects.replace(gems[start], selects.get(gems[start]) - 1);
				start++;
			}

			if (selects.size() == size && answer[1] - answer[0] + 1 > end - start + 1) {
				answer[1] = end + 1;
				answer[0] = start + 1;
			}
		}

		return answer;
	}
}

연속된 수들 중 부분합이 S 이상인 최소 길이를 구하면 되므로 투 포인터를 활용하여 풀어본다

부분 합이 sum보다 작을 때에는 오른쪽 인덱스를 가리키는 포인터를 오른쪽으로,

sum보다 클 때에는 왼쪽 인덱스를 가리키는 포인터를 오른쪽으로 옮긴다.

부분합의 가장 작은 길이를 구해야 하므로 while문을 돌면서 min 값을 업데이트 해준다.

import java.util.*;
import java.io.*;

public class Main {
	public static int n;
	public static long sum;
	public static int arr[];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		sum = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}

		int leftIndex = 0;
		int rightIndex = leftIndex;
		int ans = n + 1;
		long subSum = arr[leftIndex];
		while (leftIndex <= rightIndex) {
			if (subSum < sum) {
				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else if (subSum == sum) {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				subSum -= arr[leftIndex];
				leftIndex++;
			}
		}

		if (ans > n) {
			ans = 0;
		}
		System.out.println(ans);

	}
}