문제에서 정해진 규칙이 유지되는지 검사하는 함수(check)와 배열에 기둥/보를 설치 및 삭제하는 작업을 하는 함수(build)를 작성
기둥과 보 2가지 구조물만 가지므로 비트 연산으로 해당 위치에 구조물의 존재를 파악
설치할 때는 설치 위치에 대해서만 조건을 검사하면 되지만, 삭제할 때는 삭제 후 주변 구조물에 대해 조건을 만족하는지 검사해야 하므로 check함수를 여러 번 호출해주어야 함
작업별 조건
기둥 설치: 설치할 위치가 바닥/보 또는 왼쪽에 보 또는 아래에 기둥
보 설치: 설치할 위치에 기둥 또는 오른쪽에 기둥 또는 양쪽에 보
기둥 삭제: 삭제후 (x-1,y+1), (x,y+1) 위치에 있는 보/기둥에 대해 위의 조건들을 각각 검사
보 삭제: 삭제후 (x-1,y), (x+1,y)에 있는 보 또는 (x,y), (x+1,y)에 있는 기둥의 조건을 각각 검사
정답 코드
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> structure;
bool check(int y, int x, int build_type) {
bool ret = true; // 경계에 아무것도 없는 경우 삭제/설치 가능하므로 기본은 true
// 기둥 설치 또는 삭제 시 해당 위치에 기둥이 있으면
if ((structure[y][x] & 1) or build_type == 0) {
// 바닥이거나 아래에 기둥이 있거나, 양 끝에 보가 하나 있으면 true
if (y == 0 or (y > 0 and (structure[y-1][x] & 1)) or
(structure[y][x] & 2) or (x > 0 and (structure[y][x-1] & 2)))
ret = true;
else ret = false;
}
// 보 설치 또는 삭제 시 해당 위치에 보가 있으면
if ((structure[y][x] & 2) or build_type == 1) {
// 양 끝에 기둥이 하나 있거나, 양 끝 모두 보가 있으면 true
if ((structure[y-1][x] & 1) or (structure[y-1][x+1] & 1) or
(x > 0 and (structure[y][x-1] & 2) and (structure[y][x+1] & 2)))
ret = true;
else ret = false;
}
return ret;
}
void build(vector<vector<int>>& build_frame) {
for (auto& v : build_frame) {
int x = v[0], y = v[1], a = v[2];
if (v[3]) {
if (check(y, x, a))
structure[y][x] |= 1 << a;
} else {
structure[y][x] ^= 1 << a;
if (a == 0) { // 기둥 삭제 후 조건 검사
if (check(y+1, x, -1))
if (x == 0 or (x > 0 and check(y+1, x-1, -1)))
continue;
} else { // 보 삭제 후 조건 검사
if (check(y, x, -1) and check(y, x+1, -1))
if (x == 0 or (x > 0 and check(y, x-1, -1)))
continue;
}
structure[y][x] |= 1 << a;
}
}
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
structure = vector<vector<int>> (n+2, vector<int> (n+2,0));
build(build_frame);
for (int x = 0; x < n+1; x++) {
for (int y = 0; y < n+1; y++) {
if (structure[y][x] & 1) answer.push_back({x, y, 0});
if (structure[y][x] & 2) answer.push_back({x, y, 1});
}
}
return answer;
}
a와 b가 s에서부터 합승해서 도착한 지점을 x 라고 할 때 cost[s][x] + cost[x][a] + cost[x][b] 가 최소가 되는 x를 찾으면 된다.
x가 s일 경우 두 사람은 완전히 합승하지 않는 것이고 x가 a나 b일 경우 둘 중 한 명의 도착지점까지의 거리 중에 다른 한 명의 도착지점이 있는 것 (경로가 겹쳐진 것)
결국 모든 지점 쌍에 대해 최소 비용을 계산해야 하는데 n의 최대 크기가 200이기 때문에 플로이드-와샬로 모든 쌍에 대해 비용을 계산할 수 있음
주의할 점: 요금 f는 1 이상 100,000 이하인 자연수이므로 200 * 200 * 100000 = 4 * 1e9 가 되는데 중간 계산 결과가 정수형을 넘을 수 있으므로 자료형으로 long을 써야 함
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
long cost[n][n];
const long INF = 1e9;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cost[i][j] = i == j ? 0 : INF; // 비용 배열 초기화
for (auto& v : fares)
cost[v[0]-1][v[1]-1] = cost[v[1]-1][v[0]-1] = v[2];
// 플로이드-와샬 알고리즘
for (int k = 0; k < n; k++) { // 매 거쳐갈(via) 지점마다 비용을 갱신
for (int u = 0; u < n; u++) {
if (cost[u][k] == INF) continue;
for (int v = 0; v < n; v++)
cost[u][v] = min(cost[u][v], cost[u][k] + cost[k][v]);
}
}
// 최소 비용 계산
long answer = INF;
for (int i = 0; i < n; i++)
answer = min(answer, cost[s-1][i] + cost[a-1][i] + cost[b-1][i]);
return answer;
}
문제 설명: 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs가 매개변수로 주어질 때, 시청자들의 누적 재생시간이 가장 많이 나오는 곳에 공익광고를 삽입하려고 합니다. 이때, 공익광고가 들어갈 시작 시각을 구해서 return 하도록 solution 함수를 완성해주세요. 만약, 시청자들의 누적 재생시간이 가장 많은 곳이 여러 곳이라면, 그 중에서 가장 빠른 시작 시각을 return 하도록 합니다.
play_time의 최대 시간을 초단위로 계산해보면 99*3600 + 59*60 + 59 = 359,999 로 배열의 크기가 크지 않음을 알 수 있음
따라서 모든 시간을 초 단위로 바꾼 뒤 매 로그마다 재생된 구간에 사람 수를 카운트해서 슬라이딩 윈도우로 O(N)만에 가장 빠른 시각을 구할 수 있음
주의할 점: 최대 로그 개수만큼 모든 구간이 재생되면 360000 * 300000 으로 32비트를 초과하므로 long long 자료형을 써야 함
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// 시간 문자열을 초 단위로 변환하는 함수
int timeToSeconds(const string& time) {
int hours = (time[0]-'0')*10 + (time[1]-'0');
int minutes = (time[3]-'0')*10 + (time[4]-'0');
int seconds = (time[6]-'0')*10 + (time[7]-'0');
return hours*3600 + minutes*60 + seconds;
}
string solution(string play_time, string adv_time, vector<string> logs) {
int seconds[360000];
memset(seconds, 0, sizeof(seconds));
for (auto& l : logs) {
int start = timeToSeconds(l);
int end = timeToSeconds(l.substr(9));
for (int i = start; i < end; i++)
seconds[i]++; // 끝 시간은 포함되지 않으므로 제외하고 재생 사람 수를 카운트
}
int playTime = timeToSeconds(play_time);
int advTime = timeToSeconds(adv_time);
int startTime = 0;
ll sum = 0, maxSum;
// 첫 광고시간동안 재생한 사람 수 누적합 계산
for (int i = 0; i < advTime; i++) sum += seconds[i];
maxSum = sum;
// 한 칸씩 윈도우를 옮기면서 최댓값 탐색
for (int i = advTime; i < playTime; i++) {
sum = sum - seconds[i-advTime] + seconds[i];
if (sum > maxSum) {
startTime = i-advTime+1; // 최댓값이면 시작 시각 저장
maxSum = sum;
}
}
// 초 단위를 다시 문자열 포맷으로 변환
string answer;
int times[3] = {startTime / 3600, (startTime % 3600) / 60, (startTime % 3600) % 60};
for (int i = 0; i < 3; i++) {
int a = times[i] / 10, b = times[i] % 10;
answer.push_back(a + '0');
answer.push_back(b + '0');
if (i < 2) answer.push_back(':');
}
return answer;
}
