[1주차] 1. 기지국 설치

내가 푼 코드 및 문제 설명

https://yummy0102.tistory.com/302

[JAVA] Summer/Winter Coding(~2018) 기지국 설치

 

---

이제 강사님의 문제 해설 및 풀이 꿀팁을 정리해보겠다!

 

 

문제 해설

우선 이 문제는 탐욕법(Greedy)로 푸는 문제다

그 이유는 우선 알고리즘 설명하고 하겠다

 

문제 풀이 순서

1. 아파트 전체를 1동부터 끝까지 순회한다

2. 현재 위치에 있는 아파트가 전파 범위내에 있는지 확인한다

3. 만약 전파 범위에 없다면 일단 기지국을 설치하고 본다 -> 뒤에 기지국이 있든 없든 일단 설치함 (greedy)

이 때 전파 범위가 최대가 되도록 기지국을 설치한다

4. 기지국을 설치했다면, 기지국의 유효 범위가 끝나는 지점부터 다시 순회를 시작한다

5. 만약 이미 기지국이 설치되어 있어서 현재 아파트가 전파 범위내에 있다면, 해당 기지국의 영향이 끝나는 범위로 이동하여 다시 순회한다

 

 

아래는 코드이다

우선 첫번째는 효율성을 고려하지 않고 짠 코드!

 

별로인 코드)

import java.util.LinkedList;
import java.util.Queue;

public class Step3_1_bad {
    static 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) { //1동부터 끝까지 모든 아파트 순회
            if(!sq.isEmpty() && sq.peek()-w <= position) { // 만약 현재 아파트가 이미 설치된 기지국의 영향 범위 내에 있는 경우
                position = sq.poll() + w + 1; // 해당 기지국의 영향 범위가 끝나는 위치로 이동
            } else { // 현재 아파트에 전파가 없는 경우 -> 기지국 설치!
                answer++;
                position += 2 * w + 1; // 설치한 기지국의 범위가 끝나는 위치로 이동
            }

            position++; // 다음 아파트로 이동
        }

        return answer;
    }
}

여기서는 설치된 기지국을 큐에 넣고 하나씩 빼오는 방식으로 구현했다

이는 알고리즘은 맞지만 효율성 부분에서 통과하지 못한다😅

 

이 때!! 자바에서 효율성을 높이기 위한 꿀팁이 있다!!

 

효율성 높이기

1) Loop를 개선한다

2) 적절한 데이터 구조를 사용한다

3) 불필요한 Object를 제거한다

 

위 문제에서는 불필요한 Object인 큐를 사용했다

자바에서는 Object보다는 Primitive를 사용하는 게 훨씬 효율성이 좋다고 한다!

그래서 큐 대신 stations 배열에 접근하는 인덱스를 선언하여 사용했다

아래는 이를 바탕으로 개선된 코드!

 

좋은 코드)

import java.util.LinkedList;
import java.util.Queue;

public class Step3_1_good {
    static public int solution(int n, int[] stations, int w) {
        int answer = 0; // 설치할 기지국의 개수

        // 기존에 설치된 기지국들을 조회하기 위한 인덱스 선언
        int si = 0;

        int position = 1; // 현재 위치에 있는 아파트
        while(position <= n) { //1동부터 끝까지 모든 아파트 순회
            if(si < stations.length && stations[si]-w <= position) { // 만약 현재 아파트가 이미 설치된 기지국의 영향 범위 내에 있는 경우
                position = stations[si] + w + 1; // 해당 기지국의 영향 범위가 끝나는 위치로 이동
                si++;
            } else { // 현재 아파트에 전파가 없는 경우 -> 기지국 설치!
                answer++;
                position += 2 * w + 1; // 설치한 기지국의 범위가 끝나는 위치로 이동
            }

            position++; // 다음 아파트로 이동
        }

        return answer;
    }
}

 

 

---

오 이렇게 강의 들으니까 좀 이해가 되고 정리하니까 공부한 느낌이 팍팍나긴 하는데...

어느 세월에 모든 문제를 이렇게 정리할 지 좀 막막하긴 하다😂

그래도 일단 ㄱ!