보석 쇼핑

• 문제

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

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

• 코드

• 처음 내 코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        HashMap<String, Integer> gemCount = new HashMap<>();
        HashMap<String, Integer> gemCount2 = new HashMap<>();
        int[] answer = new int[2];
        for(int i=0; i<gems.length; i++){
            if(gemCount.get(gems[i]) == null){
                gemCount.put(gems[i], 1);
                gemCount2.put(gems[i], 1);
            }
            else{
                gemCount.replace(gems[i], gemCount.get(gems[i])+1);
                gemCount2.replace(gems[i], gemCount2.get(gems[i])+1);
            }
        }
        
        int[] ansCan = new int[2];
        int end = gems.length;
        int start = 1;
        for(int i=gems.length-1; i>=0 ; i--){
            String curGem = gems[i];
            if(gemCount.get(curGem)-1 == 0){
                end = i+1;
                break;
            }
            else
                gemCount.replace(curGem, gemCount.get(curGem)-1);
        }
        
        for(int i=0; i<gems.length; i++){
            String curGem = gems[i];
            if(gemCount.get(curGem)-1 == 0){
                start = i+1;
                break;
            }
            else
                gemCount.replace(curGem, gemCount.get(curGem)-1);
        }
        
        ansCan[0] = start;
        ansCan[1] = end;
        int diff1 = end-start+1;
        
        int[] ansCan2 = new int[2];
        end = gems.length;
        start = 1;
        
        for(int i=0; i<gems.length; i++){
            String curGem = gems[i];
            if(gemCount2.get(curGem)-1 == 0){
                start = i+1;
                break;
            }
            else
                gemCount2.replace(curGem, gemCount2.get(curGem)-1);
        }
        
        for(int i=gems.length-1; i>=0 ; i--){
            String curGem = gems[i];
            if(gemCount2.get(curGem)-1 == 0){
                end = i+1;
                break;
            }
            else
                gemCount2.replace(curGem, gemCount2.get(curGem)-1);
        }
        

        
        ansCan2[0] = start;
        ansCan2[1] = end;
        int diff2 = end-start+1;
        
        if(diff1 < diff2){
            answer = ansCan;
        }else if(diff1 > diff2){
            answer = ansCan2;
        }else{
            if(ansCan[0] < ansCan2[0])
                answer = ansCan;
            else
                answer = ansCan2;
        }
        
        return answer;
    }
}

 

• 모범답안

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        HashSet<String> set = new HashSet<>();
        for(int i=0; i<gems.length; i++)
            set.add(gems[i]);
        int maxSize = set.size();
        HashMap<String, Integer> gemCount = new HashMap<>();
        int low = 0;
        int high = 1;
        gemCount.put(gems[low], 1);
        int maxLen = gems.length+2;
        int cur_s = 0; int cur_e = 0;
        while(low < high){
            if(gemCount.size() < maxSize && high < gems.length){
                String curGem = gems[high];
                if(gemCount.get(curGem) == null){
                    gemCount.put(curGem, 1);
                }else{
                    gemCount.replace(curGem, gemCount.get(curGem)+1);
                }
                high++;
            }else{
                if(gemCount.size() == maxSize){
                    int tmpLen = high-low+1;
                    if(tmpLen < maxLen){
                        maxLen = tmpLen;
                        cur_s = low;
                        cur_e = high-1;
                    }
                }
                String curGem = gems[low];
                gemCount.replace(curGem, gemCount.get(curGem)-1);
                if(gemCount.get(curGem) == 0)
                    gemCount.remove(curGem);
                low++;
            }
        }
        answer[0] = cur_s+1;
        answer[1] = cur_e+1;
        return answer;
    }
}

• 피드백
  • 맨 처음에 제약조건을 보고 투 포인터 비슷하게 가면 되겠다는데는 접근을 함 
  • 처음 나는 모든 보석들의 빈도 수를 조사하고, 끝에서 마지막 하나가 남는 보석이 등장할 때 까지 지우고, 앞에서 부터 마지막 하나가 남는 보석이 등장할 때 까지 지워서 할 수 있다고 생각을 했다.
  • 근데 테케는 맞을지언정 제출 후 채점은 개털림
  • 모범답안은 모든 보석의 종류를 포함할 수 있는 모든 경우를 조사한다. 투 포인터로 조사해서 O(N)이 걸림, 그리고 이는 확실하게 답안이 나올 수 있는 방법이다.
  • 내 방법은 처음에 발상할때는 맞을 수 있다고 생각했는데.... 다음과 같은 경우를 생각해보자
    • 내 아이디어는 뒤에서 마지막 남는 보석이 등장할 때 까지 테이블을 업데이트하며 앞으로 나아간 뒤 앞에서 뒤로 마지막 남는 보석이 등장할 때 까지 테이블을 업데이트 하는 것이였다. (문제가 틀려서 이 역방향도 구현했으나 역시나 틀림)
    • o~~xo~ox 이러한 경우, 내 방법으로 하면 o~~x가 결과물로 나오지만 정답은 ~xo가 될 것이다. 역방향으로 해도 ~ox가 나오면서 이는 해답이 될 수 없음. 그래서 내 방법은 틀리게 된다.
  • 어떤 그리디한 방법을 생각했을때 이 방법이 맞는지 반드시 다시 생각해보자. 아예 처음부터 제약조건을 만족시킬 수 있는 완전탐색 방법은 없는지 항상 먼저 생각하자.