[프로그래머스]보석쇼핑_Java

--문제--

https://programmers.co.kr/learn/courses/30/lessons/67258

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

 

--문제 접근--

문제의 조건

1. 연속적으로 나열된 보석을 모든 종류의 보석을 구매하는 것.

2. 만약 길이가 같다면 번호 순서가 더 낮은걸 출력

 

문제의 조건 1을 보고 생각해냈던 것이 

1번부터 시작해서 1번의 조건을 만족하는 길이를 먼저 찾습니다.

그 이후에 1번부터 하나씩 빼 봤을 때에 1번을 빼봅니다. 그러다가 보석이 1개뿐이라 만약 못 뺄 환경에 있을 때는 조금 더 보석을 찾으러가 봅니다. 이런 식으로 알고리즘을 짜 봤습니다.

그리고 다른 주의할 점은

맨 처음 보석의 개수를 알아내는 점입니다. 이 점의 방법은 hashset 방법과 ArrayList에 중복을 확인하면서 넣는 방법이 있는데 저는 ArrayList의 방법을 사용하였습니다.

조건 2는 최신화를 무조건 길이가 작을 때만 하면 해결이 됩니다.

--코드--

package Level3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class 보석쇼핑 {
	public static void main(String[] args) {
		String[] temp= {"A","B","B","B","B","B","B","C","B","A"};
		System.out.println(Arrays.toString(solution(temp)));
	}
	public static int[] solution(String[] gems) {
        int[] answer = {0,0};
        ArrayList<String> result=new ArrayList<>();
        //이과정은 중복을 제거하는 과정..
        for(String x :gems) {
        	if(!result.contains(x))result.add(x);
        }
        HashMap<String, Integer> hs=new HashMap<>();
        int idx=0;
        //처음부터 끝까지산다고가정했을때 처음으로 조건을 만족하는 길이 구하는과정 돌면서 카운트하는과정
        while(true) {
        	if(!hs.containsKey(gems[idx]))hs.put(gems[idx],1);
        	else hs.put(gems[idx],hs.get(gems[idx])+1);
        	if(hs.size()==result.size())break;
        	idx++;
        }
        int start=0;
        int end=idx;
        int ans_start=0;
        int ans_end=idx;
        int ans=idx;//일단은 조건을 만족하는 길이.
        out: while(end<gems.length) {
        	String temp=gems[start];
        	//-1해도 0보다크다는건 2개이상 존재하다는 의미. 
        	if(hs.get(temp)-1>0) {
        		start++;//-1을해주고 다음을 보러가기.
        		hs.put(temp, hs.get(temp)-1);
        		//답을 최신화해주는 과정 조건에서 길이가 같다면 번호순서대로나열이라 무조건 작은것들만 최신화
        		if(end-start<ans) {
        			ans_start=start;
        			ans_end=end;
        			ans=end-start;
        		}
        	}//-1했는데 0이라는건 제외하면 안된다는의미니 조금 더 둘러보러가기
        	else if(hs.get(temp)-1==0) {
        		
        		end++;
        		//여기서 end==gems.length라는건 이미 다보고 없다는 의미
        		if(end==gems.length)break out;
        		hs.put(gems[end], hs.get(gems[end])+1);
        	}
        }
        answer[0]=ans_start+1;
        answer[1]=ans_end+1;
        return answer;
    }
}