프로그래머스 기지국 설치(자바)

난이도

---

LV3

 

풀이

---

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        Queue<Integer> sq = new LinkedList<>();
        for(int s:stations) sq.offer(s);
        
        int position = 1;
        while(position<=n){
            if(!sq.isEmpty()&&sq.peek()-w<=position){
                position=sq.poll()+w+1;
            }else{
                answer+=1;
                position+=w*2+1;
            }
        }

        return answer;
    }
}

위 코드로 제출하면 정확성은 통과하는데 효율성을 통과하지 못한다.

 

Queue를 빼고 인덱스 값으로 탐색하도록 바꾸어주었더니 통과하였다.

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int si = 0;
        int position = 1;
        while(position<=n){
            if(si<stations.length&&stations[si]-w<=position){
                position=stations[si]+w+1;
                si+=1;
            }else{
                answer+=1;
                position+=w*2+1;
            }
        }

        return answer;
    }
}

 

 

 

링크

---

https://school.programmers.co.kr/learn/courses/30/lessons/12979?language=java 

프로그래머스