문제링크
해시 자료구조 + 문자열처리 구현 문제 (카카오 기출)
개인적으로 신고 결과 받기와 매우 유사한 문제라고 느꼈다.
자동차 번호 | 입차시간 |
---|---|
0000 | 06:00 |
5961 | 05:34 |
0148 | 07:59 |
자동차 번호 | 누적시간(분) |
---|---|
0000 | 320 |
5961 | 440 |
0148 | 540 |
- 자동차 번호별 자동차의 입차 시간을 저장할 딕셔너리
(해시)
- 자동차 번호별 누적 주차시간을 저장할 딕셔너리
(해시)
위와 같이 두 가지 형태의 딕셔너리를 사용했습니다.
전반적인 로직은
IN
인 경우에는 해당 자동차 번호를 key 값으로입차시간
을 초기화 시켜줍니다.
OUT
인 경우에는 해당 해당 자동차 번호로 입차기록이 있음이 보장되기 때문에 현재출차시간 - 입차시간
을 통해서 누적시간을 초기화 시켜주고 입차기록 값을 공백으로 바꿔줍니다.
반복문을 모두 돌고 난 이후에 입차시간이 공백이 아닌 자동차 번호가 있는 경우에는 23:59 을 기준으로 출차를 시켜주고 OUT과 동일한 로직을 적용시킵니다.
마지막으로 자동차번호를
오름차순으로
요금을 출력해줘야 하기 때문에 정렬을 시켜준다.
swift 풀이
import Foundation
typealias SplitType = (String, String, String)
var map: [String: Int] = [:] // 자동차별 분단위 시간을 저장할 딕셔너리
var inOut: [String: String] = [:] // 자동차별 입/출차 시간을 저장할 딕셔너리
// 문자열을 시간, 차, 입/출차 기준으로 나눠주는 함수
func splitString(_ record: String) -> SplitType {
let splitRecord = record.components(separatedBy: " ")
let time = splitRecord[0]
let car = splitRecord[1]
let mode = splitRecord[2]
return (time, car, mode)
}
//해시맵을 초기화 해주는 함수
func setHashMap(_ records:[String]) {
for record in records {
let s = splitString(record)
map[s.1] = 0
// inOut[s.1] = ""
}
}
//입, 출차 시간을 기준으로 분단위 시간을 계산하는 함수
func calTime(_ inTime: String, _ outTime: String) -> Int {
let splitIn = inTime.components(separatedBy: ":")
let splitOut = outTime.components(separatedBy: ":")
let inH = Int(splitIn[0])!
let inM = Int(splitIn[1])!
let outH = Int(splitOut[0])!
let outM = Int(splitOut[1])!
let time = (outH - inH) * 60 + (outM - inM)
return time
}
// 분단위 시간을 기준으로 요금을 계산하는 함수
func calMoney(_ time: Int, _ fees: [Int]) -> Int {
if time <= fees[0] {
return fees[1]
} else {
let remainTime = time - fees[0]
var unitTimes = remainTime / fees[2]
if remainTime % fees[2] != 0 {
unitTimes += 1
}
return (unitTimes * fees[3]) + fees[1]
}
}
func solution(_ fees:[Int], _ records:[String]) -> [Int] {
setHashMap(records)
for record in records {
let s: SplitType = splitString(record)
if s.2 == "IN" {
inOut[s.1] = s.0 // 입차하는 경우에는 시간을 넣어주기만 하면 된다.
} else {
map[s.1]! += calTime(inOut[s.1]!, s.0) // 츌차하는 경우 기존 입차시간과의 차를 통해 갱신
inOut[s.1] = ""
}
}
// 다 돌고 난 이후에 출차하지 않은 경우에는 23:59을 기준으로 출차를 시켜준다.
for e in inOut {
if e.value != "" { // 출차되지 않은 경우
map[e.key]! += calTime(e.value, "23:59")
inOut[e.key] = ""
}
}
let keySortedDict = map.sorted(by: {$0.0 < $1.0}) // sort 함수의 시간복잡도는 보장되겠지??
var answer: [Int] = []
for key in keySortedDict {
answer.append(calMoney(key.value, fees))
}
return answer
}
c++ 풀이
#include <string>
#include <vector>
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <algorithm>
using namespace std;
unordered_map<string, int> map;
unordered_map<string, string> inOut;
vector<pair <string, int>> v;
// 문자열을 시간, 차, 입/출차 기준으로 나눠주는 함수
tuple<string, string, string> splitString(string record) {
int firstIndex, secondIndex;
firstIndex = record.find(' ');
secondIndex = record.find(' ', firstIndex + 1);
string time, car, mode;
time = record.substr(0, firstIndex);
car = record.substr(firstIndex + 1, secondIndex - firstIndex);
mode = record.substr(secondIndex + 1);
return make_tuple(time, car, mode);
}
// 해쉬맵을 초기화 해주는 함수
void setHashMap(vector<string> records) {
for(int i = 0; i < records.size(); i++) {
tuple<string, string, string> s = splitString(records[i]);
map[get<1>(s)] = 0;
}
}
// 입, 출차 시간을 기준으로 분단위 시간을 계산하는 함수
int calTime(string in, string out) {
int inH, inM, outH, outM;
inH = stoi(in.substr(0, 2));
inM = stoi(in.substr(3, 2));
outH = stoi(out.substr(0, 2));
outM = stoi(out.substr(3, 2));
return (outH - inH) * 60 + (outM - inM);
}
// 시간을 기준으로 요금을 계산하는 함수
int calMoney(int time, vector<int> fees) {
if(time <= fees[0]) {
return fees[1];
} else {
int remainTime = time - fees[0];
int unitTimes = remainTime / fees[2];
if(remainTime % fees[2] != 0)unitTimes += 1;
return (unitTimes * fees[3]) + fees[1];
}
}
vector<int> solution(vector<int> fees, vector<string> records) {
setHashMap(records);
for(int i = 0; i < records.size(); i++) {
tuple<string, string, string> s = splitString(records[i]);
if(get<2>(s) == "IN") {
inOut[get<1>(s)] = get<0>(s);
} else { // OUT 인 경우
map[get<1>(s)] += calTime(inOut[get<1>(s)], get<0>(s));
inOut[get<1>(s)] = "";
}
}
// 다 돌고 난후에 출차하지 않은 경우에는 23:59 기준으로 출차를 시켜준다.
for(auto e : inOut) {
if(e.second != "") {
map[e.first] += calTime(e.second, "23:59");
inOut[e.first] = "";
}
}
for(auto e : map) {
// cout << e.first << ": " << e.second << '\n';
int money = calMoney(e.second, fees);
v.push_back({e.first, money});
}
sort(v.begin(), v.end());
vector<int> answer;
for(int i = 0; i < v.size(); i++) {
// cout << v[i].first << ": " << v[i].second << '\n';
answer.push_back(v[i].second);
}
return answer;
}
사실 이 문제를 카카오 공채 코테에서 풀어봤었는데 그 때는 해시 자료구조를 떠올리지 못하고 벡터를 이용해서 쌩으로 구현했었다ㅠ
그리고 최근부터는 Swift
로도 문제를 풀어보려고 노력하고 있는데 아직까진 c++
로 먼저 풀고 Swift
로 번역하는 수준이다ㅠ
Swift
도 노력해야겠다!