프로그래머스 - 롤케이크 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=java

프로그래머스

 

너무 어렵게 생각하는걸까? 아이디어를 떠올리는 것이 아직도 미숙하다.

 

레벨2로 평이한 난이도임에도 DP에 꽂혀서 말도안되는 점화식을 찾으려고 노력했다. 반성하자. 안되는 것 같으면 바로 돌아나오는 것도 실력이다. 이 문제는 right left 맵을 나누어서 풀이하는 것이 가장 편하고 쉬운 방법이다.

 

처음엔 모두 right에 값을 넣어두고 0부터 left로 옮겨보는 식으로 풀이하면 O(N) 으로 풀 수 있다. 다만 맵의 삭제연산 같은 부분이 있어 조금 시간이 걸리긴 하지만 틀린 풀이가 아니다.

 

생각을 유연하고 하나에 꽂힌다고 박혀서 나오지 못하는 이상한 습관을 버리자.

 

import java.util.*;
class Solution {
    static HashMap<Integer, Integer> right = new HashMap<>();
    static HashMap<Integer, Integer> left = new HashMap<>();
    
    public int solution(int[] topping) {
        int answer = 0;
        
        for(int i = 0; i < topping.length; i++){
            if(right.containsKey(topping[i])){
                right.replace(topping[i], right.get(topping[i]) + 1);
            }else{
                right.put(topping[i], 1);
            }
        }
        
        for(int i = 0; i < topping.length; i++){
            if(left.containsKey(topping[i])){
                left.replace(topping[i], left.get(topping[i]) + 1);
            }else{
                left.put(topping[i], 1);
            }
            
            right.replace(topping[i], right.get(topping[i]) - 1);
            if(right.get(topping[i]) == 0){
                right.remove(topping[i]);
            }
            
            if(right.size() == left.size()) answer++;
        }
        
        
        
        return answer;
    }
}