[PCCP] Lv3: 기지국 설치(12979) 해설

문제

- 문제 링크: 기지국 설치

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- n: 전체 범위

- w: 전파의 세기

- 최악의 경우 location이 매번 2w + 1씩 증가하므로 n/(2w+1)번 반복문을 수행

- 최종 시간 복잡도: O(N/W)

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int location = 1; // 현재 탐색하는 아파트의 위치
        int idx = 0; // 설치된 기지국의 인덱스
        
        while (location <= n) {
            // 기지국이 설치된 위치에 도달한 경우
            if (idx < stations.length && location >= stations[idx] - w) {
                location = stations[idx] + w + 1;
                idx++;
            }
            // 기지국이 설치되지 않은 위치인 경우
            else {
                location += 2 * w + 1; // 기지국을 설치하고 해당 범위를 넘어감
                answer++;
            }
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 전체 범위

- W: 전파의 세기

- 최악의 경우 location이 매번 2W + 1씩 증가하므로 N/(2W + 1)번 반복문을 수행

- 최종 시간 복잡도: O(N/W)

def solution(N, stations, W):
    answer = 0
    location = 1 # 현재 탐색하는 아파트의 위치
    idx = 0 # 설치된 기지국의 인덱스
    
    while location <= N:
        # 기지국이 설치된 위치에 도달하는 경우
        if idx < len(stations) and location >= stations[idx] - W:
            location = stations[idx] + W + 1
            idx += 1
        # 기지국이 설치되지 않은 위치인 경우
        else:
            location += 2 * W + 1 # 기지국을 설치하고 해당 범위를 넘어감
            answer += 1
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 전체 범위

- W: 전파의 세기

- 최악의 경우 location이 매번 2W + 1씩 증가하므로 N/(2W + 1)번 반복문을 수행

- 최종 시간 복잡도: O(N/W)

function solution(N, stations, W) {
    let answer = 0;
    let location = 1; // 현재 탐색하는 아파트의 위치
    let idx = 0; // 설치된 기지국의 인덱스
    
    while (location <= N) {
        // 기지국이 설치된 위치에 도달하는 경우
        if (idx < stations.length && location >= stations[idx] - W) {
            location = stations[idx] + W + 1;
            idx += 1;
        } else {
            location += 2 * W + 1; // 기지국을 설치하고 해당 범위를 넘어감
            answer += 1;
        }
    }
    
    return answer;
}

solution 2)

import

solution 3)

import