🦾 오늘의 컨디션 및 특이사항(개인 일정 등)
- 수면 시간
- 7시간
- 학습 시간
- 14 : 00 ~ 16 : 00
- 특이사항
📑 세부 학습 내용
📅 스케쥴
- 2시간 코딩테스트 및 풀이 리뷰
- 총 2시간
✏️ 코딩 테스트
- 1 SOLVE 및 깃허브 커밋
- 프로그래머스 -
17678 - 문제 유형 :
그리디 알고리즘,시뮬레이션/구현 - https://github.com/oneplast/ProgrammersCT/commit/7efa5ed2c5defed9c01944b247007e7686ae1e19
🔨 트러블 슈팅
- 최초 풀이
class Solution {
public String solution(int n, int t, int m, String[] timetable) {
Arrays.sort(timetable);
String startTime = "09:00";
int passCnt = 0;
int capacity = 0;
int saveIdx = 0;
int[] busTime = splitTime(startTime);
for (int i = 0; i < timetable.length; i++) {
int[] crewTime = splitTime(timetable[i]);
if (shouldTake(busTime, crewTime, capacity, m)) {
++capacity;
} else if (capacity < m) {
capacity = 0;
if (++passCnt >= n) {
break;
}
startTime = getNextTime(busTime, t);
busTime = splitTime(startTime);
saveIdx = i;
}
}
int idxTotal = getTotalMinute(timetable[saveIdx]);
int startTotal = getTotalMinute(startTime);
if (idxTotal > startTotal) {
int[] splitTime = splitTime(startTime);
String hour = String.format("%02d", splitTime[0]);
String minute = String.format("%02d", splitTime[1]);
return hour + ":" + minute;
} else if (idxTotal == startTotal) {
idxTotal -= 1;
String hour = String.format("%02d", idxTotal / 60);
String minute = String.format("%02d", idxTotal % 60);
return hour + ":" + minute;
} else {
return timetable[saveIdx];
}
}
private boolean shouldTake(int[] busTime, int[] crewTime, int capacity, int m) {
if (crewTime[0] < busTime[0] ||
(crewTime[0] == busTime[0] && crewTime[1] <= busTime[1])) {
return capacity < m;
}
return false;
}
private int[] splitTime(String time) {
String[] timeBits = time.split(":");
int hour = Integer.parseInt(timeBits[0]);
int minute = Integer.parseInt(timeBits[1]);
return new int[]{hour, minute};
}
private String getNextTime(int[] busTime, int t) {
int hour = busTime[0];
int minute = busTime[1];
int upCnt = 0;
minute += t;
if (minute >= 60) {
upCnt = minute / 60;
minute %= 60;
}
hour += upCnt;
hour = Math.min(hour, 24);
return hour + ":" + minute;
}
private int getTotalMinute(String time) {
int[] splitTime = splitTime(time);
return splitTime[0] * 60 + splitTime[1];
}
}
- 풀이 실패
- 아이디어 :
- 조건에 맞춰 시간 분할, 분으로 분할, 시간 비교 등 여러 메서드를 만들고,
Crew탑승 시간 배열을 정렬한 후, 탑승 가능한 최소 IDX를 구하여 버스 시간과 비교하여 값 추출
- 조건에 맞춰 시간 분할, 분으로 분할, 시간 비교 등 여러 메서드를 만들고,
- 종합적으로 로직 자체가 꼬이고 코드도 난잡하여 수정 부분을 찾기에도 어려움이 있었음
- 해당 방법으로 풀이 포기
- 최종 풀이
class Solution {
public String solution(int n, int t, int m, String[] timetable) {
int[] crewArr = Arrays.stream(timetable)
.mapToInt(this::getTotalMinutes)
.sorted()
.toArray();
int busTime = getTotalMinutes("09:00");
int crewIdx = 0;
for (int i = 0; i < n; i++) {
int capacity = 0;
while (crewIdx < crewArr.length && crewArr[crewIdx] <= busTime && capacity < m) {
++crewIdx;
++capacity;
}
if (i == n - 1) {
if (capacity < m) {
return getCalTime(busTime);
} else {
return getCalTime(crewArr[crewIdx - 1] - 1);
}
}
busTime += t;
}
return "";
}
private int getTotalMinutes(String time) {
String[] splitTimes = time.split(":");
return Integer.parseInt(splitTimes[0]) * 60 + Integer.parseInt(splitTimes[1]);
}
private String getCalTime(int totalMinutes) {
int hour = totalMinutes / 60;
int minute = totalMinutes % 60;
return String.format("%02d:%02d", hour, minute);
}
}
- 기존 아이디어 접근은 좋았고, 조건들만 보다 정확하게 구현하여 문제 해결
- 기존 로직 중, 분 총합을 계산하는
getTotalMinutes()메서드와, 해당 분 총합으로 HH:mm을 구하는getCalTime()메서드 생성 - 외부 반복문은 셔틀 운행 횟수만큼만 지정하고, 내부에서
While문을 활용하여crewArr배열에서 검사 수행- 조건에 맞는 최소 Idx(인덱스) 계산 및 탑승 승객 수용량 계산
- 매 반복마다 셔틀 운행 횟수에 따른 셔틀 운행 시간 갱신
- 결국 원하는 건 마지막 셔틀 버스까지 진행했을 때의 값이므로, 마지막 셔틀 버스를 기준으로 수용량이 남았으면 버스 출발 시간에만 도착하면 되므로 버스 출발 시간을, 수용량이 가득 찼으면 최소 인덱스의 승객보다는 1초 빠른 시간을 반환
- 시간복잡도
O(N * logN)crewArr의 정렬 시간복잡도 :O(N * logN)- 해당 시간복잡도가 최악의 경우
- 최종 시간복잡도
O(N * logN)
💡 어려웠던 것 || 알게 된 것
- 금일은 없음
기록