알고리즘/프로그래머스
프로그래머스 - 2018 KAKAO BLIND RECRUITMENT [1차] 추석 트래픽
시나모온
2020. 4. 29. 00:08
문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/17676
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문자열 처리 + 우선순위 큐 문제
시간을 간편하게 처리하기 위해서 먼저 입력받은 데이터를 전부다 밀리세컨드(ms)로 변환했습니다.
그리고 가장 많이 겹치는 경우는 데이터의 처리시간의 맨 앞이나 끝이 걸치는 부분에 존재할 거라고 생각했습니다. 그래야 하나라도 더 범위 안에 포함 시킬 수 있으니까 (탐욕법)
그래서 문제에서 완료시간을 데이터로 줘서 완료 시점을 기준으로 마지막 데이터 부터 처음 데이터까지, 겹치는 게 몇개나 되는지 카운트 했습니다.
이때, 탐색 시점의 데이터(i번째의 전송 완료 시점)으로부터 1초 이후에 전송을 시작하는 데이터들은 전부 팝하면서 카운트에서 제외했다.
(시작 시점을 저장할 때, 우선순위 큐를 사용하는 게 유리하다. 다른 컨테이너는 매번 그 컨테이너는 전부 순회해야하지만, 우선순위 큐는 최대 값만 살펴보면 된다. 우선순위를 사용하지 않으면 다른 값과 비교하는 연산의 시간 복잡도가 O(N)지만, 우선순위 큐를 사용하면 O(logN)이면 해결된다. 그래서 전체 시간 복잡도가 O(NlogN)이 된다.)
// https://programmers.co.kr/learn/courses/30/lessons/17676
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int solution(vector<string> lines) {
int answer = 0;
vector<int> times(lines.size());
priority_queue<int> pq;
// ms로 변환
for(int i = 0; i < lines.size(); i++) {
int hour = stod(lines[i].substr(11, 2));
int minute = stod(lines[i].substr(14, 2));
double second = stod(lines[i].substr(17, 6));
int secTime = hour * 3600000 + minute * 60000 + second * 1000;
times[i] = secTime;
}
// 끝 데이터부터 처음 데이터 방향으로 탐색
int cnt = 0;
int max = 0;
for(int i = times.size() - 1; i >= 0; i--) {
cnt++;
// 전송 시점을 priority queue에 넣어준다. (priority queue를 쓴 이유는 빠른 탐색을 위해서)
int temp = times[i] - (int)(stod(lines[i].substr(24, lines[i].size() - 25)) * 1000) + 1;
pq.push(temp);
// 거리가 1 넘어가는 건 다 꺼내기
while(!pq.empty()) {
if(times[i] + 1000 <= pq.top()) {
pq.pop();
cnt--;
} else {
break;
}
}
if(cnt > max) max = cnt;
}
answer = max;
return answer;
}