일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- DirectX11
- UnrealEngine4
- UnrealEngine5
- RVO
- 2294
- 프로그래머스
- Frustum
- algorithm
- directx
- C
- GeeksForGeeks
- 언리얼엔진5
- 줄 세우기
- RootMotion
- C++
- 1563
- Programmers
- 오블완
- IFileDialog
- softeer
- UE5
- Unreal Engine5
- baekjoon
- winapi
- const
- NRVO
- DeferredRendering
- 티스토리챌린지
- 팰린드롬 만들기
- 백준
- Today
- Total
Game Develop
[Algorithm] Programmers :: 호텔 대실 본문
https://school.programmers.co.kr/learn/courses/30/lessons/155651
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
bool visited[1001] = { false };
void DFS(string endTime, int index, vector<vector<string>>& book_time)
{
int curEndTime = stoi(endTime.substr(0, 2)) * 60 + stoi(endTime.substr(3, 2)) + 10;
int minEndTime = 1000000;
int minIndex = 1000000;
for (int i = index + 1; i < book_time.size(); ++i)
{
int nextStartTime = stoi(book_time[i][0].substr(0, 2)) * 60 + stoi(book_time[i][0].substr(3, 2));
int nextEndTime = stoi(book_time[i][1].substr(0, 2)) * 60 + stoi(book_time[i][1].substr(3, 2));
if (!visited[i] && nextStartTime >= curEndTime)
{
if (curEndTime < minEndTime)
{
minEndTime = curEndTime;
minIndex = i;
}
}
}
if (minIndex == 1000000) return;
visited[minIndex] = true;
DFS(book_time[minIndex][1], minIndex, book_time);
}
int solution(vector<vector<string>> book_time)
{
int answer = 0;
sort(book_time.begin(), book_time.end());
for (int i = 0; i < book_time.size(); ++i)
{
if (!visited[i])
{
++answer;
visited[i] = true;
DFS(book_time[i][1], i, book_time);
}
}
return answer;
}
|
cs |
최소한의 방만 이용해서 모든 예약을 소화하는 문제이다.
일단 시작시간을 기준으로 정렬 후, DFS로 나머지것들을 탐색하면서 현재 선택한 시작시간이 '기준시간의 종료시간+10'보다는 크면서, 종료시간이 제일 짧은것을 알아낸다음 해당 인덱스로 DFS를 진행하는 방식으로 했다.
사실 결국 나머지것들을 전부 검사하는거라서.. 시간효율은 좋지않을거라 생각했다.
실제로 통과는 했다만,효율은 좋지않았다. 통과라도 한 이유는 인풋크기가 1000밖에 안되서 그렇다.
이런 문제유형처럼, 공통된부분을 어떻게해야 효율적으로 알 수 있을까.. 해서 구글링하니까 누적합이라는 방법이 있다고 한다. 정말 쉽고 간단한데 효율적이다. 이제서라도 알아서 다행일 정도...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int solution(vector<vector<string>> book_time)
{
int answer = 0;
int arr[1451] = { 0 };
for (int i = 0; i < book_time.size(); ++i)
{
int start = stoi(book_time[i][0].substr(0, 2)) * 60 + stoi(book_time[i][0].substr(3));
int end = stoi(book_time[i][1].substr(0, 2)) * 60 + stoi(book_time[i][1].substr(3)) + 10;
arr[start] += 1;
arr[end] += -1;
}
int sum = 0;
for (int i = 0; i < 1451; ++i)
{
sum += arr[i];
answer = max(answer, sum);
}
return answer;
}
|
cs |
처음코드같은 경우 40ms도 나오기도 하는데, 누적합으로풀면 최대 0.2ms로, 압도적인 시간차이가 난다.
보통 기본적인 누적합의 경우, 범위의 시작부분에 +1을하고 '끝부분+1'의 부분에 -1을 하는데, 이번문제의 경우 '끝부분+1'부분이 아니라 그냥 끝부분에 -1을 체크한다.
왜냐하면 문제에서 대실이 끝난다음 10분간 청소를 한다고 한다.
대신 청소가 끝나자마자 해당 방을 이용할 수 있다.
즉, '대실 끝시간 +10'시간일 때 바로 방을 대여할 수 있다. 끝남과 동시에 바로 대여가 가능한게 문제의 조건이기 때문에 끝부분+1 에 -1을 체크하는게 아니라 그냥 끝부분에 -1을 체크해도 되는것이다.
'Algorithm > Programmers' 카테고리의 다른 글
[Algorithm] Programmers :: 혼자서 하는 틱택토 (0) | 2023.06.16 |
---|---|
[Algorithm] Programmers :: 미로 탈출 (0) | 2023.06.15 |
[Algorithm] Programmers :: 뒤에 있는 큰 수 찾기 (0) | 2023.06.13 |
[Algorithm] Programmers :: 숫자 변환하기 (0) | 2023.06.13 |
[Algorithm] Programmers :: 시소 짝꿍 (0) | 2023.06.13 |