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

카테고리

탐색, 이분탐색(?)

나만의 카테고리

전체 포함하는 최적해 찾기, 리스트, 맵

문제 링크

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

요점

• Set, Map, LinkedList 등을 활용할 수 있어야 한다.
• 자바 유틸 클래스에서 제공하는 sort 혹은 Collections의 min, max를 사용할 때는 효율 문제를 염두에 둬야한다

참고 지식

• Set 사용법(Java)
• Map 사용법(Java)
• Collections 메소드

풀이 (Java)

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        HashSet<String> gemSet = new HashSet<>();

        for (String gem : gems) {
            gemSet.add(gem);
        }

        int gemSetSize = gemSet.size();

        if (gemSetSize == 1) {
            return new int[]{1, 1};
        }

        HashMap<String, Integer> gemMap = new HashMap<>();
        int maxTerm = 0;
        int answerEnd = 1;
        int answerStart = 1;
        int minGemValue = 0;
        boolean isMinValue = true;
        for (int i = 0; i < gems.length; i++) {
            int beforeGemValue = gemMap.get(gems[i]) != null ? gemMap.get(gems[i]) : 0;

            minFlag = minGemValue == beforeGemValue ? true : false;

            gemMap.put(gems[i], i);
            if (gemMap.size() == gemSetSize) {
                if (isMinValue) {
                    minGemValue = Collections.min(gemMap.values());
                }
                int maxGemValue = i;

                if (maxTerm == 0 || maxTerm > maxGemValue - minGemValue) {
                    answerEnd = maxGemValue;
                    answerStart = minGemValue;

                    maxTerm = maxGemValue - minGemValue;
                }
            }
        }

        return new int[]{answerStart + 1, answerEnd + 1};
    }
}

 
풀이가 깔끔하진 않습니다. isMinValue같은 state를 활용하는 방식을 선호하지는 않지만 코드를 작성하고 나서 효율성 테스트를 통과하려 급하게 생각해낸 방법이였습니다.

기존에는 Collections.min, max를 둘 다 사용해서 maxGemValue, minGemValue를 계산했더니 효율성 테스트를 통과할 수 없었습니다.

따라서 연산을 필요할 때만 할 수 있게 해서 리펙토링 했습니다.

 
 

알고리즘 초보가 정리한 글입니다 더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!