[Programmers/Java/Lv.1/그리디] 73.덧칠하기

문제 설명

프로그래머스

 

실패한 나의 풀이

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int willPaintCount = section.length; // 3
        boolean[] wall = new boolean[n]; // 벽
        
        // 칠해야할곳을 true로 대입
        for(int i = 0; i < section.length; i++){
            wall[section[i] - 1] = true;
        }
        
        // section.length가 0이 될때까지 (while) 반복
        while(willPaintCount > 0){
            int[] countArr = new int[wall.length - m + 1]; // count5개

            for(int j = 0; j <= wall.length - m; j++){
                int count = 0;
                for(int k = j; k < j + m; k++){ // m개 만큼 고정
                    if(wall[k] == true){
                        count++;
                    }
                    
                }
                countArr[j] = count;
            }
            // 다 돌고나서 {2, 2, 2, 3, 3}
            //          [0] [1] [2] [3] [4]
            // count가 가장 높을때의 k를 기억해야함(만약 count가 같다면 더 큰 k로)
            int max = countArr[0];
            int idx = 0;
            for(int p = 1; p < countArr.length; p++){
                if(max <= countArr[p]){
                    max = countArr[p];
                    idx = p;
                }
            }
            
            // 이제 가장 높은 p를 false로 바꿔주고 
            for(int k = idx; k < idx + m; k++){
                wall[k] = false;
            }
            
            // answer도 1올려줌
            answer++;
            
            // 그리고 section.length를 true에서 false로 바뀐 개수(count)만큼 빼준다.
            willPaintCount -= countArr[idx];
        }
        
        return answer;
    }
}

완전탐색으로 품

 

룰러가 범위를 넘어서도 됐었음, 문제도 잘못 이해함

GPT 풀이법

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int i = 0;
        while (i < section.length) {
            int start = section[i];
            answer++;
			// i 되는 데까지 증가
            while (i < section.length && section[i] < start + m) {
                i++;
            }
        }
        return answer;
    }
}

• section[0] 부터 칠하는게 효율적이다.
• 즉, 칠해야할 첫 번째 부분부터 +m까지 칠하고 또 칠해야할 부분이 있다면 거기서부터 다시 칠함
• 룰러는 section의 길이를 넘어서도 된다.

 

✅ 1회차 칠하기

• 현재 i = 0, 즉 section[0] = 2
• start = 2, 롤러 길이 m = 4니까 → 칠할 범위: 2, 3, 4, 5
• 이 범위에 있는 section 요소 2, 3은 칠해짐
• i는 다음 안 칠해진 구역을 찾기 위해 증가
  section[0] = 2 → OK, 2 < 6 → i++
  section[1] = 3 → OK, 3 < 6 → i++
  section[2] = 6 → X, 6 < 6이 아니므로 중단
• → 즉, 1회차로 2, 3, 4, 5를 칠함 → answer = 1

✅ 2회차 칠하기

• 이제 i = 2, 즉 section[2] = 6
• start = 6, m = 4 → 칠할 범위: 6, 7, 8, 9
• section[2] = 6 → OK, 6 < 10 → i++
• i = 3이 되어 section 끝남 → 반복 종료
• → answer = 2