[프로그래머스 Level 3] 기지국 설치(C++)

코딩테스트 연습 - 기지국 설치 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

보자마자 순차 탐색해야겠다 했는데 입력이 2억이길래 바로 접고 다른 방법을 생각했다. 주어진 station의 시작 지점과 끝지점을 vector에 저장한해놓고 for문으로 1부터 n까지 탐색하는데 만약 i가 station의 시작지점보다 작으면 station 하나를 세워야 하고 i의 값에 w*2를 더해주면 된다. 만약 점프 뛴 i가 station의 시작지점보다 크면 다음 station의 시작지점을 기준으로 두고 i의 값은 이전 station의 끝 지점으로 이동해준다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> v;

int solution(int n, vector<int> stations, int w)
{
	int answer = 0;
	for (int i = 0; i < stations.size(); i++) {
		v.emplace_back(stations[i] - w, stations[i] + w);
	}
	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (v.size()-1 < c) {
			i = i + w * 2;
			answer++;
			continue;
		}
		if (v[c].first > i) {
			i = i + w * 2;
			answer++;
		}
		else {
			i = v[c].second;
			c++;
		}
	}
	cout << answer;
	return answer;
}