프로그래머스 LEVEL 3(기지국 설치)

사용 언어 : javascript
해결 날짜 : 2022-11-29
해결 방법 :
- 인자로 받는 n의 크기가 200,000,000 이하의 자연수이기 때문에 이 n에 대한 풀이가 아닌 stations에 대한 풀이로 진행해야 겠다고 생각함
- 하나의 기지국의 범위는 (2 * w + 1)이고, 단방향 범위는 (w + 1)임을 착안하여
- stations를 돌며 아래를 구함
  - 현재 기지국의 범위가 닿지 않는 최대값 (end)
  - 현재 기지국이 설치되지 않은 부분의 최소값 (start)
  - 현재 기지국이 설치되지 않은 부분의 범위 (range)
- 범위를 구한 후 start update
- ~~현재 범위가 0보다 작거나 같은 경우, 기지국을 설치할 필요가 없으므로 pass~~
  - 문제 다시 풀 때 변경함, 현재 범위가 큰 경우에만 answer update
- 그 외의 경우 현재 범위에서 설치할 기지국의 개수를 구해 answer에 더함
  - 이 때, 설치할 기지국의 개수는 length를 range로 나눈 값을 올림한 값
- stations을 다 돌고 난 후,
  - start가 n보다 큰 경우는 모든 기지국을 설치한 경우
  - 그 외의 경우 start와 n 사이에 기지국을 또 설치해야 하므로 설치할 기지국의 개수를 answer에 더함
회고 :
- start를 업데이트하는 부분을 for of문의 제일 끝에 배치해서 기지국을 설치할 필요가 없을 때 continue하므로 start를 업데이트하지 못했기 때문에 점수가 계속 낮게 나왔다.
  - 문제 다시 풀 때 변경함
- 또, 단순히 n이 200,000,000 이하의 자연수라는 조건만 보고 n에 대한 풀이는 아예 접어두고 문제를 해결했는데, 다른 사람이 푼 풀이를 보니 하나의 기지국이 (2 * w + 1) 칸을 차지해 최소 3칸을 차지하므로 최대 연산 횟수가 66,666,667회임을 이용해 단순하게 풀어도 됐을 거라고 한다.
- 처음 생각한게 무조건 맞다고 생각하지 말고 깊게 생각하고 문제 풀자..!
재회고 :
- start부터 n까지 반복문 돌리는 형식으로 문제를 다시 풀어 보았다.
- 전체적인 코드는 똑같고, 효율성도 비슷한 것 같은데 처음 풀었던 방식은 stations를 다 돌고 뒤에 설치할 기지국이 남은 경우 똑같은 코드를 다시 작성해야 하기 때문에 비효율적이었다.
- 하지만 다시 풀어본 방식의 코드는 더 남은 stations가 없을 경우에도 반복문이 종료되지 않고 추가로 로직을 작성할 필요 없이 뒷부분을 진행할 수 있어 훨씬 코드 읽기가 간결한 것 같다!

코드

function solution(n, stations, w) {
    let answer = 0;
    let start = 1;
    const range = 2 * w + 1;
    const half = w + 1;

    for (const station of stations) {
        const end = station - half;
        const length = end - start + 1;
        start = station + half;
                
        if (length > 0) answer += Math.ceil(length / range);
    }
            
    if (start <= n) {
        const length = n - start + 1;
        answer += Math.ceil(length / range);
    }

    return answer;
}

추가 풀이 코드

function solution(n, stations, w) {
    let answer = 0;
    let start = 1;
    let station = stations.shift();
    const range = 2 * w + 1;
    const half = w + 1;
        
    while (start <= n) {
        const end = station - half;
        const length = end - start + 1;
        start = station + half;
        station = stations.shift() || n + half;
            
        if (length > 0) answer += Math.ceil(length / range);
    }

    return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges