Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 플로이드-와샬
- dfs
- java
- 시뮬레이션
- Network
- 투 포인터
- 알고리즘
- 백트래킹
- CS
- swea
- 구현
- 이분탐색
- 문자열
- Effective Java
- Kotlin
- 스택
- 후니의 쉽게 쓴 시스코 네트워킹
- mst
- JUnit 5
- 백준
- 그리디
- 에라토스테네스의 체
- BFS
- 동적계획법
- 위상정렬
- 세그먼트 트리
- 유니온 파인드
- 프로그래머스
- 수학
- 완전탐색
Archives
반갑습니다!
[프로그래머스] 셔틀버스 본문
풀이
이 문제를 풀기 위해서는 우선 문자열을 모두 숫자로 바꿔서 시간을 표현해야한다. 하지만 시간과 분을 따로 나눠서 처리하면 비교하기가 어렵기 때문에 1시간은 60분으로 변환하여 모든 시간을 분으로 처리하였다. 그리고 프렌즈를 빨리 도착한 순서대로 정렬한다. 콘이 가장 늦게 버스를 탈 수 있는 시간을 구하는 문제이므로 결국 콘이 마지막 버스를 마지막 순서로 탈 수 있는지를 확인하면 된다. 따라서 프렌즈를 모두 순서대로 버스에 태우고, 마지막 버스가 가득 찬 경우는 마지막에 탄 프렌즈보다 1분 일찍와서 타면 되고, 마지막 버스가 콘이 타지 않았음에도 여유가 있다면 버스 도착 시간에 콘이 오면 된다.
코드
C++
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int time_to_int(string& t) {
int h = stoi(t.substr(0, 2));
int m = stoi(t.substr(3, 2));
return h * 60 + m;
}
string time_to_string(int h, int m) {
string hour = to_string(h);
string minute = to_string(m);
if (hour.length() == 1) hour = '0' + hour;
if (minute.length() == 1) minute = '0' + minute;
return hour + ":" + minute;
}
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
vector<int> table;
// 모든 시간을 분으로 변경
for (string t : timetable)
table.push_back(time_to_int(t));
// 도착 순서가 빠른 순서대로 정렬
sort(table.begin(), table.end());
int bus = 9 * 60; // 버스 출발 시간
int ans = 0;
int idx = 0; // 버스 탑승할 프렌즈의 인덱스
for (int i = 0; i < n; i++) {
int count = 0; // 버스에 탑승한 인원
for (int j = idx; j < table.size(); j++) {
// 버스에 정원이 남아있을 때
if (table[j] <= bus) {
count++;
idx++;
}
// 버스의 정원이 다 찬 경우
if (count == m) break;
}
// 마지막 버스일 때
if (i == n - 1) {
// 버스에 정원이 다 차지 않은 경우, 버스 도착하는 시간에 콘이 도착하면 된다
if (count < m) ans = bus;
// 버스의 정원이 다 찬 경우, 콘은 마지막에 탄 프렌즈보다 1분 먼저오면 탈 수 있다.
else ans = table[idx - 1] - 1;
break;
}
bus += t; // 다음 버스가 오는 시간
}
answer = time_to_string(ans / 60, ans % 60);
return answer;
}
Java
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int timeToInt(String time) {
int h = Integer.parseInt(time.substring(0, 2));
int m = Integer.parseInt(time.substring(3, 5));
return h * 60 + m;
}
public String timeToString(int h, int m) {
String hour = String.valueOf(h);
String minute = String.valueOf(m);
if (hour.length() == 1) hour = "0" + hour;
if (minute.length() == 1) minute = "0" + minute;
return hour + ":" + minute;
}
public String solution(int n, int t, int m, String[] timetable) {
String answer = "";
ArrayList<Integer> table = new ArrayList<>();
// 모든 시간을 분으로 변경
for (String time : timetable)
table.add(timeToInt(time));
// 도착 순서가 빠른 순서대로 정렬
Collections.sort(table);
int bus = 9 * 60; // 버스 출발 시간
int idx = 0; // 버스 탑승할 프렌즈의 인덱스
int ans = 0;
for (int i = 0; i < n; i++) {
int count = 0; // 버스에 탑승한 인원
for (int j = idx; j < table.size(); j++) {
// 버스에 정원이 남아있을 때
if (table.get(j) <= bus) {
count++;
idx++;
}
// 버스의 정원이 다 찬 경우
if (count == m) break;
}
if (i == n - 1) {
// 버스에 정원이 다 차지 않은 경우, 버스 도착하는 시간에 콘이 도착하면 된다
if (count < m) ans = bus;
// 버스의 정원이 다 찬 경우, 콘은 마지막에 탄 프렌즈보다 1분 먼저오면 탈 수 있다.
else ans = table.get(idx - 1) - 1;
break;
}
bus += t; // 다음 버스가 오는 시간
}
answer = timeToString(ans / 60, ans % 60);
return answer;
}
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 14891 톱니바퀴 (0) | 2020.05.08 |
---|---|
[백준] 14890 경사로 (0) | 2020.05.08 |
[프로그래머스] 네트워크 (0) | 2020.05.07 |
[프로그래머스] 타겟 넘버 (0) | 2020.05.07 |
[SWEA] 2383 점심 식사시간 (0) | 2020.05.07 |