[프로그래머스] 보석 쇼핑 (Java)

https://campus.programmers.co.kr/courses/15436/lessons/132825

프로그래머스

투포인터

 

 

시작점 lt와 끝점 rt를 주고

끝점이 이동하면 끝점+1을 해주고

rt=1

시작점이 이동하면 시작점+1을 해준다

lt=1

 

접근 방법

 

1. 일단 hashset을 사용해 주어진 보석의 종류를 파악하도록 한다 진열장의 보석은 같은 종류가 있을 수도 있으므로 중복을 피하기 위해 set을 이용

 

2.보석의 종류를 파악하고 나서 보석의 종류와 개수를 담을 hashmap을 생성한다.

 

3. 먼저 map에 해당 보석이 있는 경우 기존 개수에 +1 해주거나 없으면 1을 넣어준다. 그리고 탐색범위를 넓히기 위해 right+1 해준다.

 

4. 계속 늘려가던 중 map의 크기와 set의 크기가 같은 경우(map에 모든 보석 종류가 존재하는 경우) 거리, 시작, 끝을 변수에 담아준다.

 

5. 또한, 처음 위치도 오른쪽으로 이동해야 하기 때문에 첫 번째 보석 개수를 줄여주고(-1) 개수가 0인 경우 없으므로 map에서 제거해줍니다. 그 후 left+1 하여 오른쪽으로 이동한다.

 

6. 범위를 늘려가던 중 right가 배열 크기와 같아진 경우 끝에 다다른 것이므로 while문에서 빠져나온다.

 

7. answer배열에 시작 원소와 끝 원소를 넣어준 후 return

 

 

 

getOrDefault

Java 8에서 추가된 Collection API 함수들 중 일부이다.

• V getOrDefault(Object Key, Object defaultValue)
• 찾는 key가 존재한다면 찾는 key의 value를 반환하고 없거나 null이면 default 값을 반환한다.
•  

import java.util.HashMap;

public class practice {
	public static void main(String arg[]) {
    
        String [] abc = { "A", "B", "C" ,"C"}; 
        HashMap<String, Integer> hm = new HashMap<>(); 
        
        for(String key : abc) {
        	hm.put(key, hm.getOrDefault(key, 0) + 1); 
        }
        System.out.println("출력 결과 : " + hm); 
        // 출력 결과 : {A=1, B=1, C=2} 
     } 
}

 

package level3;

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

public class JewerlyShopping {
    
    public static void main(String[] args) {
        String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};

        Solution sol = new Solution();
        System.out.println(Arrays.toString(sol.solution(gems)));
    }

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

           

            HashSet<String> set = new HashSet<>(); //진열장에 있는 보석을 담을 set 생성

            for (String s : gems) {  //for문을 사용하여 모석종류를 set에 담아줌
                set.add(s);
            }

            int n = gems.length;  //진열장의 길이

            int distance = Integer.MAX_VALUE;
            //범위
            int left = 0;
            int right = 0;

            //정답
            int start = 0;
            int end = 0;

            HashMap<String, Integer> map = new HashMap<>();  //보석과 보석의 개수를 담을 map 생성

            while (true) {

                if (set.size() == map.size()) {  //보석이 종류의 개수와 진열장에 담은 보석의 개수가 같을경우 진열장에서 보석을 담다 모든 보석을 담는경우
                    // 범위 좁히기
                    map.put(gems[left], map.get(gems[left])-1);

                    if (map.get(gems[left]) == 0) {  
                        map.remove(gems[left]);
                    }
                    left++;
                } else if (right == n) { //범위를 최대로 줄인상태에서 right가 최대일때
                    break; 종료
                } else {
                    //right 오른쪽으로 이동
                    //set에 해당하는 보석들을 다 찾아야함
                    //해당 보석의 개수 +1
                    map.put(gems[right], map.getOrDefault(gems[right], 0) + 1);  //투포인트 오른쪽으로 이동
                    right++;  //범위를 늘리기 & 범위를 모두 늘린상태에서 투포인트 right를 최대로
                }

                if (map.size() == set.size()) {  //보석이 모두 담긴 상태에서
                    if (right-left < distance){  //범위를 줄이기
                        distance = right-left;
                        start = left+1;
                        end = right;
                    }
                }

            }//while

            answer[0] = start;  //투포인트 최소 시작점
            answer[1] = end;    //투포인트 최대 

            return answer; 반환
        }
    }
}

생각해야할것

모든 종류의 보석을 담은 최대범위에서 최소범위로 줄이는 것을 생각할 것 (투포인트)