[프로그래머스 / 연습문제 / 자바(JAVA)] 롤케이크 자르기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

[ 요약 ]

시작 시간 : AM 10:38

종료 시간 : PM 12:18

소요 시간(분) : 100분...

 

도전 횟수 (제출 횟수) : 9번 ㅎ

로직 및 풀이 참고 여부 : X

 

[ 풀어보기 ]

정답 풀이

📌 로직

1. 배열로 풀기
   
   • topping의 원소가 1 ~ 10000 까지 있다고 했으므로, 10000개의 공간을 가진 배열 2개를 만들어줌.
   • 각각의 배열이 케이크 한 조각을 뜻함
   • 인덱스 = 토핑 번호- 1 ( 1번 토핑 = 인덱스 0 )
   • 값 = 해당 토핑의 개수
2. 그리고 각각의 케이크가 가진 토핑의 개수를 셀 함수 int n, m을 만들어준다.
3. 일단 1번 조각에 토핑을 다 몰아줌.
4. topping 배열을 차례로 돌면서 2번 조각으로 토핑을 하나씩 옮겨준다.
   • n == m이 되면 answer ++;
   • n < m 이 되면 반복문을 빠져나온다. ( 이 순간부터는 n == m 이 될 일이 없다. )

 

📌 코드

- 이 답안은 제출 답안 중 처음 정답처리된 답안이므로 코드가 지저분합니다... 아래의 개선된 코드를 참고해주세요! 

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        int[] arr1 = new int[10000]; // 케이크 한 조각
        int[] arr2 = new int[10000]; // 케이크 다른 한 조각
        // 인덱스 = 토핑에 매겨진 번호 - 1
        // 값 = 해당 토핑의 개수
        
        int max = 0;
        
        for(int a : topping) {
            arr1[a-1]++;
            max = Math.max(a, max);
        }
        
        int n = 0; // arr1의 토핑 개수
        int m = 0; // arr2의 토핑 개수
        
        for(int i=0; i<max; i++) {
            if(arr1[i] != 0) n++;
        }
        // 토핑이 몇 가지 종류로 구성되어 있는 지 알아내기 위함
        // 가장 큰 토핑번호 == 토핑의 종류 수 라고 여겼더니 실패가 떴었다.
 
        for(int a : topping) {
            
            int temp = arr2[a-1];
            
            arr1[a-1]--;
            arr2[a-1]++; // 토핑을 하나씩 arr2 조각으로 넘겨준다.
            
            if(arr1[a-1] == 0) n--; // arr1 조각에서 토핑 한 종류가 사라지면 n--;
            if(temp == 0 && arr2[a-1] != 0) m++; // arr2 조각에 토핑 한 종류가 새로 생기면 m++;
            
            if(n==m) answer++; // 토핑의 개수가 같으면 answer++;
            if(n<m) break; // arr2 조각의 토핑의 개수가 더 많아지는 순간부터는 for문을 그만 돌아도 됨
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (1.15ms, 81.7MB)
테스트 2 〉	통과 (3.62ms, 78.2MB)
테스트 3 〉	통과 (3.98ms, 76.2MB)
테스트 4 〉	통과 (7.54ms, 80.3MB)
테스트 5 〉	통과 (22.18ms, 127MB)
테스트 6 〉	통과 (21.35ms, 120MB)
테스트 7 〉	통과 (28.38ms, 123MB)
테스트 8 〉	통과 (22.08ms, 125MB)
테스트 9 〉	통과 (12.28ms, 143MB)
테스트 10 〉	통과 (18.09ms, 123MB)
테스트 11 〉	통과 (4.54ms, 81.6MB)
테스트 12 〉	통과 (1.46ms, 87.4MB)
테스트 13 〉	통과 (24.22ms, 130MB)
테스트 14 〉	통과 (25.41ms, 119MB)
테스트 15 〉	통과 (23.94ms, 132MB)
테스트 16 〉	통과 (17.40ms, 134MB)
테스트 17 〉	통과 (23.71ms, 125MB)
테스트 18 〉	통과 (18.03ms, 125MB)
테스트 19 〉	통과 (19.67ms, 136MB)
테스트 20 〉	통과 (12.74ms, 138MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

---

 

코드 개선

📌 개선 방향

1. 토핑 가지 수를 알아내는 방법 개선
   
   • topping을 순회하며 arr1을 구성해줄 때,
   • arr1[a-1] == 0 이면 새 토핑이 추가된다는 뜻이므로, 
   • arr1[a-1] ++ 을 하기 전, arr1[a-1] == 0 이면 n++ 을 해준다
   • 따라서, n을 구하기 위해 필요했던 max 변수도 필요없어진다.
2. arr2에 새 토핑이 추가되는 경우를 판별하는 방법 개선
   • 토핑을 arr1 -> arr2 로 옮긴 다음,
     • arr1[a-1] --; arr2[a-1]++;
   • arr2[a-1] == 1이 된 경우라면 arr2 에 새 토핑이 추가되었다는 뜻.
   • 그러므로 temp 변수를 쓸 필요 없이, arr2[a-1] == 1인 경우 m++ 을 해주면 된다.  

 

📌개선 후 코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        int[] arr1 = new int[10000];
        int[] arr2 = new int[10000];
        
        int n = 0; // arr1이 가지고 있는 토핑 종류의 개수
        int m = 0; // arr2가 가지고 있는 토핑 종류의 개수
        
        // arr1 조각에 토핑 모두 몰아주기
        for(int a : topping) {
            if(arr1[a-1] == 0) n++;
            arr1[a-1]++;
        }

        for(int a : topping) {
            
            // 토핑을 arr1 조각에서 arr2 조각으로 하나씩 옮겨준다.
            arr1[a-1]--;
            arr2[a-1]++;
            
            if(arr1[a-1] == 0) n--; // arr1에 토핑 한 종류가 사라진 경우
            if(arr2[a-1] == 1) m++; // arr2에 토핑 햔 종류가 새로 생긴 경우
            
            if(n==m) answer++; // 토핑 종류의 개수가 같으면 answer++;
            if(n<m) break;
        }
        
        return answer;
    }
}

 

📌 개선 후 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.61ms, 84.9MB)
테스트 2 〉	통과 (3.58ms, 81.4MB)
테스트 3 〉	통과 (4.54ms, 82.1MB)
테스트 4 〉	통과 (19.02ms, 74.2MB)
테스트 5 〉	통과 (14.98ms, 118MB)
테스트 6 〉	통과 (20.97ms, 120MB)
테스트 7 〉	통과 (16.44ms, 143MB)
테스트 8 〉	통과 (25.78ms, 137MB)
테스트 9 〉	통과 (10.77ms, 139MB)
테스트 10 〉	통과 (10.39ms, 139MB)
테스트 11 〉	통과 (2.47ms, 81MB)
테스트 12 〉	통과 (1.03ms, 73.7MB)
테스트 13 〉	통과 (27.62ms, 121MB)
테스트 14 〉	통과 (15.47ms, 134MB)
테스트 15 〉	통과 (27.79ms, 136MB)
테스트 16 〉	통과 (19.92ms, 123MB)
테스트 17 〉	통과 (23.87ms, 138MB)
테스트 18 〉	통과 (15.92ms, 142MB)
테스트 19 〉	통과 (15.43ms, 140MB)
테스트 20 〉	통과 (10.42ms, 137MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

코드 가독성도 좋아졌고, 실행 속도도 미약하게나마 개선되었다.

 

---

[ 오답 노트 ]

 

오답 1

📌 오답 코드

배열 대신 Set을 사용했다. Set이 중복을 허용하지 않는다는 성질을 이용하고자 했음.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        Set<Integer> set1 = new HashSet<>(); // 케이크 조각1
        Set<Integer> set2 = new HashSet<>(); // 케이크 조각2
 
        loop : for(int i=0; i<topping.length; i++) {
            set1.add(topping[i]); // 조각1에 토핑 i을 추가한다.
            set2.remove(topping[i]); // 조각2에 토핑 i가 있다면, 제거한다.

            for(int j=i+1; j<topping.length; j++) {
                set2.add(topping[j]); // 남은 토핑들을 조각 2에 추가한다.
                if(set1.size() < set2.size()) continue loop;
                    // 만약 조각2에 있는 토핑 수가 더 크면
                    // 아래 사항을 진행하지 않고 다음 토핑으로 넘어감
            }
 
            if(set1.size() == set2.size()) answer++;
            	// 케이크 조각에 올려진 토핑 개수가 같으면 answer++;
            if(set1.size() > set2.size()) break;
            	// set1 케이크의 토핑 수가 더 크다 = for문 벗어남
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (268.10ms, 125MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (121.84ms, 146MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (2278.16ms, 415MB)
테스트 10 〉	통과 (2139.71ms, 433MB)
테스트 11 〉	통과 (41.79ms, 89.9MB)
테스트 12 〉	통과 (591.87ms, 203MB)
테스트 13 〉	실패 (시간 초과)
	...
테스트 20 〉	실패 (시간 초과)

채점 결과
정확성: 30.0
합계: 30.0 / 100.0

 

📌 오답 이유

1. 효율성 테스트 오답 이유
   • 이중 for문.
     • 외부의 for문은 topping.length 만큼 반복하고,
     • 내부의 for문은 최악의 경우 topping.length - i 만큼 반복한다.
     • 최악의 경우 이중 루프의 시간 복잡도는 O(N^2). 입력 배열의 크기가 커질 수록 너무 많은 시간이 소요될 수 밖에...
   • arr1에 add를해주고 arr2에 remove를 해준 뒤 또 다시 arr2에 남은 토핑을 채워넣은 이유는,
     • arr1로 옮기고 arr2에 남은 토핑 중에도,
       arr1로 옮겨진 토핑과 같은 종류의 토핑이 있을 수도 있기 때문이었다. 
     • set은 중복을 허용하지 않기 때문에 arr2에도 남아있어야 하는 토핑종류여도 remove하면 지워져버림.
     • 하지만 이 for문 때문에 생략할 수 있는 작업이 계속 반복되는 느낌...

 

📌 개선하기

1. 효율성 테스트 오답 개선
   • Set이 아닌 배열로 만들자.
     • 토핑의 종류는 배열의 인덱스로 구분, 값을 그 종류 토핑의 개수로 계산해서 구현해보자.
     • 그리고 arr1에서 값이 0이 아닌 요소의 개수 == arr2에서 값이 0이 아닌요소의 개수 면 answer++ 

 

 

---

오답 2

📌 오답 코드

이번엔 배열을 사용해보았다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        int max = 0;
        for(int a : topping) max = Math.max(max, a);

        int[] arr1 = new int[max];
        int[] arr2 = new int[max];
        
        for(int a : topping) arr1[a-1]++;

        for(int a : topping) {
            int n = 0;
            int m = 0;
            
            // arr1 -> arr2 옮기기
            arr1[a-1]--;
            arr2[a-1]++;
            
            // arr1과 arr2의 토핑 개수 세기
            for(int b : arr1) if(b!=0) n++;
            for(int b : arr2) if(b!=0) m++;
    
            if(n<m) break;
            if(n==m) answer++;
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (29.48ms, 78.9MB)
테스트 2 〉	통과 (1589.29ms, 82.1MB)
테스트 3 〉	통과 (27.68ms, 80.3MB)
테스트 4 〉	통과 (5.13ms, 79.7MB)
테스트 5 〉	통과 (23.74ms, 124MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (333.19ms, 122MB)
테스트 10 〉	통과 (183.87ms, 140MB)
테스트 11 〉	통과 (11.91ms, 83.4MB)
테스트 12 〉	통과 (348.42ms, 78.4MB)
테스트 13 〉	실패 (시간 초과)
		...
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	통과 (7721.19ms, 119MB)

채점 결과
정확성: 50.0
합계: 50.0 / 100.0

 

📌 오답 이유

1. 효율성 테스트 오답 이유
   • 역시... for문.
   • 토핑을 arr1 에서 arr2로 옮길 때마다,
     • arr1의 처음부터 끝까지 순회하며 토핑의 개수를 세고
     • arr2의 처음부터 끝까지 순회하며 토핑의 개수를 세고...
   • 매우 비효율적임. 

 

📌 개선하기

1. 효율성 테스트 오답 개선
   • for문 밖에서 int n과 m을 선언해주자.
     • n에는 토핑 종류의 개수, m은 0으로 시작
     • arr1[a-1] -- ; arr2[a-1] ++; 후에, arr1[a-1]이 0이 되면 n--, arr2[a-1]이 0을 벗어나면 m++을 하자.

---