항해 99 13일차 TIL( 덧칠하기 / 프로그래머스)

문제         

프로그래머스

1 번째 시도   

알고리즘 설명

• 칠해야 하는 벽에 위치를 unpainting[] 배열에 저장.
• 1m씩 전진하며 페인팅 해야하는지 확인 
• true라면 페인팅 하고 롤러크기 만큼 다음 인덱스들 false 해주기

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        
        int result =0;
        boolean[] unpainting = new boolean[n];
        
        for(int s : section) {
            unpainting[s] = true;
        }
        
        for(int i =0 ; i < n; i++) {
            if(unpainting[i] == true) {
                for(int j =0; j < m ; j++) {
                    if(i+j< n) {
                        unpainting[i+j] = false;
                    }
                }
                result++;
            }
        }
        return result;
    }
}

3개 중 2개는 성공했지만 ArrayIndexOutOfboundsException이 떴다

배열을 사용하는 곳을 잘 살펴봐야겠다.

        
        for(int s : section) {
            unpainting[s] = true;
        }

이부분이 문제이다. section안에 있는 숫자는 index가 아니라 벽의 번호이다. 

요즘 인덱스랑 탐색해야 하는 물건 번호랑 많이 헷갈리는 것 같다..

조심해야겠다.

2 번째 시도  

import java.util.*;

class Solution {
    public int solution(int n, int m, int[] section) {
        
        int result =0;
        boolean[] unpainting = new boolean[n];
        
        for(int s : section) {
            unpainting[s-1] = true;
        }
        
        for(int i =0 ; i < n; i++) {
            if(unpainting[i] == true) {
                for(int j =0; j < m ; j++) {
                    if(i+j < n) {
                        unpainting[i+j] = false;
                    }
                }
                result++;
            }
        }
        return result;
    }
}

남의 코드

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;

        int start = section[0];
        answer++;

        for (int item : section) {
            if (start + m > item) {
                continue;
            }

            start = item;
            answer++;
        }

        return answer;
    }
}

내 로직보다 훌씬 간단하다.

나의 코드는 기계가 벽을 1m씩 탐색하여 칠해야 하면 칠한 거고

이분은 사람이 눈으로 보고 칠해야 하는 부분을 바로 가서 칠한 거다.

당연히 속도는 이분이 빠를 수밖에 없다.

 

나처럼 자료구조 식으로 생각하는 것도 좋은데 인간이 판단을 내리는 근거를 코드로 짤 수 있다면 후자가 낫다.