[프로그래머스] 보석 쇼핑(Java, Level.3)

문제

 어피치가 연속적으로 나열되어 있는 모든 종류의 보석을 쇼핑한다. 

가장 적은 개수를 선택할 수 있는 부분을 인덱스로 구해라  

 

입출력 예 

풀이

너무 어렵다... 다른 방법으로도 풀어볼려고 한다 

다양한 블로그를 참고하여 문제를 풀었다..!  

 

[ 변수 설명 ]

gemCountMap : 어피치가 선택한 보석 종류 및 개수 

selectedGemsQueue : 어피치가 선택한 보석 List

gemSet : 포함하여야 하는 모든 보석의 종류 

 

start : 리스트 시작 번호

size : 리스트의 개수

>> gems의 길이로 설정한 이유는 보석 리스트의 크기와 비교하기 위해서 큰 값이 필요함 

result : 최종 리스트의 시작 번호 

 

 [ 반복문 ]

 

반복문을 통해 gems 배열의 원소를 하나씩 비교한다.

반복문 안의 로직을 3단계로 나눌 수 있다. 

1단계. 보석 선택

2단계. 1번의 보석의 개수가 1개가 되도록 설정

3단계. 최소값을 가지는 보석의 리스트인지 확인 

 

단계별로 하나씩 설명하겠다. 

 

[ 1단계. 보석선택 ] 

1. 큐에 보석 추가 

2. Map에 보석추가 및 개수 설정

 

[ 2단계. 1번의 보석의 개수가 1개가 되도록 설정 ]

1. wile문을 통해 1번 보석의 개수가 1개가 될때까지 반복 

2. firstgem에 1번 보석 저장 

3. firstgem이 보석 List에 존재하는지 확인 

• 3-1. 존재하면 빠져나가기
• 3-2. 존재하지 않으면 4번으로 

4. 1번 보석 삭제 

5. 1번 보석 삭제로 인해 2번 보석이 1번 보석으로 변경 

>> 시작 지점 하나 뒤로 변경

6. 1번 보석 삭제로 인해 Map에 보석 개수 갱신 (-1) 

 

[ 3단계. 최소값을 가지는 보석의 리스트인지 확인 ]

 1. 조건 1 : 모든 보석의 종류를 소유하고 있는지 

• >> 보석 리스트의 보석 종류의 개수 == 소유해야할 보석 종류의 개수 

2. 조건 2. 보석 리스트의 개수 최솟값 구하기 

• >> size : 이전에 가지고 있던 보석 리스트 크기 
• >> selectedGemsQueue.size() : 현재 가지고 있는 보석 리스트 크기

3. result : 최종 시작 지점

4. size : 최소 보석 리스트의 크기 

 

* 3단계의 break?? 

나는 이 조건문 안에서 break를 사용하여 더이상의 작업을 하지 않고 결과값을 반환하면 안되나? 

라는 궁금증이 생겼다. 

 

프로그래머스의 예시 값을 대입하면 모두 성공으로 떴지만, 실제로는 틀렸다고 나오는 케이스들이 있었다. 

그래서 프로그래머스를 둘러보여 케이스들을 확인해봤다. 

 

{ "A", "B", "B", "B", "B", "B", "B", "C", "B", "A" }

 

이 케이스를 잘 보면 마지막 3개를 선택 즉, {8, 11} 값 반환한다. 

하지만, 3단계에서 break를 사용하게 된다면 {1, 7}를 반환하게 된다.

 따라서 뒤에 어떤 배열의 요소들이 기다리고 있을지 모르니 break를 사용하지 않고 확인해여야 한다. 

 

최종  코드

import java.util.*;

 

public int[] s5(String[] gems) {

        System.out.println("보석 쇼핑");

        Map<String, Integer> gemCounthMap = new HashMap<>(); // 어피치가 선택한 보석 종류 및 개수

        Queue<String> selectedGemsQueue = new LinkedList<>(); // 어피치가 선택한 보석

        Set<String> gemSet = new HashSet<>(Arrays.asList(gems)); // 보석 종류

        int start = 0;

        int size = gems.length;

        int result = 0;

        for (String gem : gems) {

            // 1. 보석 선택

            selectedGemsQueue.add(gem);

            gemCounthMap.put(gem, gemCounthMap.getOrDefault(gem, 0) + 1);

            // 2. 1번 보석의 개수가 1개가 될때까지 반복

            while (true) {

                // 2-1. 1번 보석 추출

                String firstgem = selectedGemsQueue.peek();

                // 2-2. 1번 보석 개수 == 1

                if (gemCounthMap.get(firstgem) == 1) {

                    break;

                }

                // 2-3. 1번 보석 개수 > 1

                selectedGemsQueue.poll(); // 1번 보석 삭제

                start++; // 1번 보석 삭제로 인해 2번 보석이 1번으로 변경

                gemCounthMap.put(firstgem, gemCounthMap.get(firstgem) - 1); // 보석의 개수 기록

            }

            // 3. 보석 리스트 확인

            // 3-1. 모든 보석의 종류를 가지고 있는지

            // 3-2. 3-1의 조건을 만족하면서 이전에 선택했던 아이템의 개수(size)가 항상 적도록

            if (gemCounthMap.size() == gemSet.size() && size > selectedGemsQueue.size()) {

                result = start;

                size = selectedGemsQueue.size();

            }

        }

        System.out.println("result + 1 : " + (result + 1));

        System.out.println("result + size : " + (result + size));

        return new int[] { result + 1, result + size };

    }

 

 

프로그래머스 문제

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

프로그래머스