프로그래머스 - 기지국 설치

programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

 

내가 작성한 풀이

public int solution(int n, int[] stations, int w) {
        // - 전체 n만큼 순회한다
        // 		- 현재 위치가 전파 범위가 아닌 경우 w 만큼 이동한 위치에 기지국을 설치한다
        //			- 설치한 후에, 전파 범위가 끝나는 지점의 다음 위치부터 다시 기지국 설치작업을 진행하면 된다.
        //		- 현재 위치가 전파 범위인 경우는 전파 범위 밖으로 벗어난 다음위치부터 다시 기지국 설치작업을 진행하면 된다.
		
        int answer = 0;
        int spreadCheck = 1;
        
        Map<Integer, Integer> spread = new HashMap<>();
        
        for (int i=0; i<stations.length; i++) {
        		spread.put(stations[i], stations[i]);
        		for (int j=1; j<=w; j++) {
        			spread.put(stations[i]+j, stations[i]);
        			spread.put(stations[i]-j, stations[i]);
        		}
        }
        
        while (spreadCheck <= n) {
        		Integer station = spread.get(spreadCheck);
	        	if (station == null) {
	        		spreadCheck += (w*2+1);
	        		answer++;
	    		} else {
	    			spreadCheck = station + w+1;
	    		}
        }
        
        return answer;
    }

 

제출하니 정확성 테스트는 다 통과되지만 효율성 테스트에서 실패 된다..

 

 

모범 답안 케이스

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++;
			} else {
				position += w * 2 + 1;
				answer++;
			}
		}
		
		return answer;
    }

 

정확성, 효율성 테스트 무난하게 통과!

 

 

Tip. 

자바에서는 Object 타입보다는 Primitive 타입을 선언해서 사용하는 것이 더 빠르다.

 

효율성 높이는 방법

- Loop 개선

- 적절한 데이터 구조 사용

- 불필요한 오브젝트 제거