강의로 돌아가기
sy

테스트는 모두 통과하는데...

테스트는 모두 0.0ms로 통과하는데 효율성테스트는 4개 다 시간 초과로 실패합니다...
결국 다른 방법으로 해결하기는 했는데 궁금증이 남아서요
아래 코드에서 어떤 부분이 효율성에 걸리는 것일까요?

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 프로그래머스 2017 서머코딩 - 기지국 설치
// 2019.02.12~ sy
#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    vector<int> prpg(n, 0);
    int idx = 0;
    for (int i = 0; i < n; ++i) {
        if (i >= stations[idx] - 1 - w) {
            ++prpg[i];
            if (i == stations[idx] - 1 + w) {
                ++idx;
                if (idx == stations.size())
                    break;
            }
        }
    }
    for (int j = 0; j < n;) {
        if (prpg[j])
            ++j;
        else {
            ++answer;
            j += 2 * w + 1;
        }
    }
    return answer;
}
1 개의 답변
YooSangwon

배열 생성 없이 인덱스 값만을 이용해서 O(n)을 만족하도록 생각해보세요.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.