이번 즐찾 문제는 한 번에 풀었다 뿌듯할지도?!

롤케이크 자르기

링크텍스트

풀이 방법 및 시행 착오

오답 풀이

1. 중복을 삭제해야 하므로 set 사용
2. 이중 for문을 사용하여 형, 동생 나눠서 넣기
   지금 생각해보니 효율성이 안 좋을 만두...
   하지만 처음 풀 때는 set 사용해야 한다는 생각에 갇혀있었음

오답 코드

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
    
        for (int i=1; i<topping.length-1; i++) {
            int[] top_1 = Arrays.copyOfRange(topping,0,i);
            int[] top_2 = Arrays.copyOfRange(topping,i,topping.length);
            
            HashSet<Integer> set_1 = new HashSet<>();
            HashSet<Integer> set_2 = new HashSet<>();
            
            for (int num_1:top_1) {
                set_1.add(num_1);
            }
            
            for (int num_2:top_2) {
                set_2.add(num_2);
            }

            if(set_1.size() == set_2.size()) {
                answer++;
            }
        }
        
        return answer;
    }
}

100점 만점에 10점~

ㅇㅋ 이중 for문이 문제군. 하지만 달리 방법이 떠오르지 않았다.
그러다 예전에 풀었던 구명보트 문제가 생각났다.
구명보트 문제도 효율성 오류가 났었던 기억이 난다.
그 문제는 무게순으로 정렬한 후, 무거운 순으로 촥촥 빼냈었던... 그런 기억이 스쳐 지나갔다.
그런 맥락(?)으로 다시 풀어봤다

정답 풀이

1. 토핑 종류당 갯수를 이용하기 위해 map사용
   1-1. 이때 형 토핑 map, 동생 토핑 map 따로 생성
2. 동생한테 모든 토핑 몰아주기
3. 동생한테서 하나씩 뺏어서 형한테 넣어주기
   3-1. 동생 토핑에서 1개 남아있는 토핑을 뺏어서 형한테 주면 동생 토핑은 0이 된다. 그러므로 동생 map에서 key 자체를 삭제해준다.
4. 동생 토핑 갯수랑 형 토핑 갯수 같아지면 answer++;

정답 코드

//이중 for문을 활용한 set은 시간 초과
//map 사용
import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        //형 토핑 map
        HashMap<Integer, Integer> map_1 = new HashMap<>();
        
        //동생 토핑 map
        HashMap<Integer, Integer> map_2 = new HashMap<>();
        
        //동생한테 몰아주기
        for(int n:topping) {
            map_2.put(n,map_2.getOrDefault(n,0)+1);
        }
        
        //형이 하나씩 뺏기
        for(int n:topping) {
            
            //동생한테 1개 남은 걸 형한테 주면 동생한테서 토핑 제거
            if(map_2.get(n)==1) {
                map_2.remove(n);
            }
            else {
                //동생 토핑 뺏기
                map_2.put(n,map_2.getOrDefault(n,0)-1);
            }
            
            //형한테 토핑 추가
            map_1.put(n,map_1.getOrDefault(n,0)+1);
            
            //형이랑 동생이랑 토핑 갯수가 같다면
            if(map_1.size() == map_2.size()) {
                answer++;
            }
        }
        
        return answer;
    }
}

정답~bb
중복을 제거해야 한다는 생각에 막연하게 set에 사로 잡혀 있었다.
하지만 map으로 풀 수 있다는 점을 배웠다.
이전까지는 공식처럼 외워서 풀었었는데 조금 더 유연한 사고가 필요할 듯 하다.

---

롤케이크 먹고 싶다