문제

문제 링크

접근

• n이 크기 때문에 시간복잡도 O(n)이하으로 맞추어야 한다.
• 처음에는 아래 코드로 0.0x수준으로 정확성 테스트를 통과하였지만, 효율성 테스트를 하나도 통과하지 못했다...
• 다시 읽어보니 stations가 오름차순으로 정렬되어 있는 것을 확인하였고, 인덱스 연산에 이를 반영하였다.

// 정확성 테스트 통과 but 효율성 테스트 시간초과 코드
class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        boolean[] r = new boolean[n];
        
        for (int i : stations) {
            r[i-1] = true;
            for (int j = 1; j <= w; j++) {
                if (i + j - 1 < n) r[i+j-1] = true;
                if (i - j - 1 >= 0) r[i-j-1] = true;
            }
        }
        
        int prev = 0;
        for (int i = 0; i < n; i++) {
            if (r[i]) {
                if (prev != 0) answer++;
                prev = 0;
                continue;
            }
            
            if (prev == w) {
                prev = 0;
                answer++;
                i += w;
                continue;
            }
            
            prev++;
        }
        
        if (prev != 0) answer++;

        return answer;
    }
}

풀이

// 정답 풀이
class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0, sIdx = 0, i = 1;

        while (i <= n) {
            if (sIdx < stations.length && i >= stations[sIdx] - w) {
                i = stations[sIdx] + w + 1;
                sIdx++;
                continue;
            }
            
            i += 2 * w + 1;
            answer++;
        }

        return answer;
    }
}