[ 프로그래머스 주차 요금 계산 (Lv2) ] (C++)

프로그래머스의 주차요금계산(Lv2) 문제이다.

 

[ 문제풀이 ]

문제에서 필요한 정보들을 구하는 과정과 이를 통해 정답을 도출하는 과정까지 순차적으로 진행해보자.

#1. 필요한 정보

먼저 이 문제에서의 정답을 구하기 위해서는 "각 차량별로 주차되어 있던 모든 시간의 합"을 알아야 한다.

왜냐하면, 하나의 차가 입차하고 출차하는 과정을 여러번 할 수도 있기 때문에 각각의 차량들이 주차되어 있었던 시간들의 누적합을 구해야 한다.

이 정보들은 우리에게 'records' 라는 매개변수에 저장되서 주어지게 된다. records안에는 [ 입차or출차시간 / 차량번호 / 입차or출차 ] 이 3가지 정보가 하나의 String 형태로 주어지게 된다. 그럼 각각을 어떻게 관리를 했는지 부터 이야기해보자.

 

#1 - 1) 차량번호

먼저, 차량번호에 대해서 이야기를 해보자. 본인은 간편하게 관리를 하기 위해서 문자열로 주어지는 차량번호를 int형으로 변환해서 관리를 해 주었다. 이 때, 차량번호를 단순 int형으로 변환을 시킨 것은 아니다. 예를 들어서 '1234'라는 차량번호가 있으면 이 "1234"라는 문자열을 int형으로 변환해서 '1234'로 표현한 것은 아니라는 것이다.

본인은 가장 처음 입력되는 차량부터 '1번'을 기준으로 순차적으로 번호를 매핑해 주었다. 이를 위해서 자료구조 map을 사용해주었다. 사실, 이렇게 까지 할 필요는 없지만, 조금이나마 실행시간에 있어서 탐색 시간을 줄이기 위해서 이와 같이 진행을 해 주었다. "1234"를 '1234'로 바꿀 때와, "1234"를 '1번'으로 바꿀 때와 어떤 차이가 있는지는 밑에서 보다 구체적으로 이야기 해보자. 결과적으로 본인은 문자열로 주어지는 차량의 번호를 '1'부터 순차적으로 번호를 증가시키면서 int형으로 매핑시켜 주었다.

동시에 ! int형으로 변환되어 있는 차량의 원래 번호를 저장해주는 과정도 진행해 주었다.

예를 들면, "1234" 라는 String형태로 주어진 차량 번호를 '1'이라는 int형 숫자로 mapping을 시켜 주었지만, 반대로 '1'이라는 숫자만 보고도 이 '1'번 차량은 "1234"라는 번호를 가지고 있는 차라는 것 또한 저장을 해 주었다는 것이다.

왜 굳이 바꾸고 또 바꾸고 이 모든 것을 저장했을까 ?? 밑에서 보다 구체적으로 이야기 하겠지만, 간략하게만 이야기를 해보자면 우리가 결과적으로 구해야 하는 값이 "차량 번호가 작은 자동차부터 청구할 주차요금" 이기 때문이다.

즉 ! "1234"라는 차량 번호를 '1'번으로 매핑 시킨 후, 이 '1'번으로만 문제를 해결하다보면 최종적으로 다시 이 '1'번이 "1234" 라는 사실을 모를 수가 있고 결과적으로 최종 정답을 도출하는데 문제가 발생할 수 있기 때문이다.

이 부분에 대해서는 아래쪽에서 보다 구체적으로 이야기해보자.

 

#1 - 2) 입차 / 출차

두 번째는 입차와 출차에 대한 정보이다. 본인은 입차와 출차에 대한 정보를 stack을 이용해서 관리해 보았다.

먼저, stack은 배열의 형태로 선언을 해 주었는데, 배열의 Index번호를 차량의 번호로 관리하기 위해서 선언해 주었다.

그럼 배열은 총 몇 칸짜리 배열을 만들어야 할까 ?? 차량번호 최대 "9999"가 될 수 있기 때문에 아마도 10,000칸이 필요하게 될 것이다. 하지만 본인은 1000칸만 만들어 주었다. 왜 그럴까 ?? #1 - 1)에서 이야기 했듯이, 본인은 차량번호를 그대로 관리하는 것이 아닌 1번부터 순차적으로 매핑시켜서 관리를 해 주었다고 이야기를 하였다. 그렇기 때문에 차량의 최대번호를 기준으로 배열의 칸을 설정할 이유는 없었는데, 그렇다면 왜 하필 크기가 1,000인 배열일까 ?? 바로 records의 최대 크기가 1,000이기 때문이다. 우리에게 주어지는 records에서 모든 차량의 입차 정보만 주어져있고 1,000개의 차량 모두 번호가 다르다고 가정을 해본다면 우리는 결국 1,000개의 차량을 1번부터 mapping 시켜야 하는 경우가 발생할 것이고 이 경우 차량 번호의 최댓값은 1,000이 될 것이기 때문이다. 그렇기 때문에 1,000칸짜리 배열을 가지는 stack을 선언해 주었다.

stack에는 해당 차량의 "입차 시간"을 저장해 주었다. 예를 들어서 "3번으로 매핑된 차량이 00:00에 입차" 하게 된다면, stack[3].top() = "00:00" 이 되는 것이다.

그렇다면, 이 3번으로 매핑된 차량의 출차 정보가 나오게 된다면 ?? 주차된 시간을 구해야 한다.

주차된 시간은 어떻게 구할 수 있을까 ?? 출차시간 - 입차시간을 하면 된다.  입차시간은 stack[3] 에 저장되어 있을 것이다. 이런식으로 입차 시간을 관리하기 위해서 stack을 사용해 주었다.

 

#1 - 3) 시간 변환

마지막으로 시간에 관한 부분이다. 이 문제에서는 시간이 "HH:MM" 의 형태로 주어지게 된다. 그리고 주차요금을 계산하기 위해서 주어지는 정보들(fees)를 보게 되면, 모두 '분 단위'로 주어지게 된다. 그래서 본인은 "HH:MM"의 형태로 주어져있는 시간을 분으로 통일시켜 주었다. HH * 60 + MM 을 통해서 하나의 분으로 통일 후 모든 계산을 진행해 주었다.

 

지금까지 이야기한 부분들을 코드로 확인해 보자.

int totalTime[1010];	// 각 차량별, 주차 누적 시간을 저장하기 위한 변수
int totalCarNum;		// 전체 차량의 갯수를 저장하기 위한 변수
int carList[1010];		// int형으로 mapping된 차량번호를 원래 차량번호로 변환하기 위한 변수.
map<string, int> carNum_Map;	// string형태의 차량번호를 int형으로 mapping 시키기 위한 변수

void findEntranceTime(vector<string> records) {
	int num = 1;
	stack<int> carStack[1010];
	for (auto str : records) {
		stringstream streamStr(str);
		string stime;
		string scarNum;
		string state;
		streamStr >> stime >> scarNum >> state;
		
		if (carNum_Map[scarNum] == 0) {
			carList[num] = stoi(scarNum);
			carNum_Map[scarNum] = num++;
		}

		int time = invertTime(stime);

		if (state == "IN") {
			carStack[carNum_Map[scarNum]].push(time);
		} else {
			int entranceTime = carStack[carNum_Map[scarNum]].top();
			int resultTime = time - entranceTime;
			totalTime[carNum_Map[scarNum]] += resultTime;
			carStack[carNum_Map[scarNum]].pop();
		}
	}

	for (int i = 1; i < num; i++) {
		if(carStack[i].empty() == true) {
			continue;
		}
		
		int resultTime = invertTime("23:59") - carStack[i].top();
		totalTime[i] += resultTime;
		carStack[i].pop();
	}

	totalCarNum = num;
}

본인은 위와 같이 구현을 해 보았다. 위의 코드에서 totalTime[] 이라는 변수 말고는 모두 #1 - 1 ~ 3) 에서 이야기 했던 부분들이라서 이 변수에 대해서만 간단하게 이야기 해 보겠다. totalTime[A] = B 라는 것은, "차량 번호가 A인 차량의 누적 주차 시간은 B분 입니다."를  의미한다. 물론 여기서 'A'의 값도 #1 - 1)에서 진행했던 1번부터 mapping된 차량의 번호가 index번호로 들어가게 된다.

위의 코드에서 line16 ~ 19)를 보게되면 차량의 번호를 num이라는 변수로 mapping 시키는 부분이 있는데 이 부분이 #1 - 1)에서 이야기 했던 차량 번호를 1부터 증가시키면서 int형으로 변환 시키는 과정이다.

line23 ~ 30)은 입차와 출차 시에 대한 부분을 구현한 것인데, 입차 시에는 stack에 단순히 시간을 넣어주는 과정만, 출차 시에는 이 stack에 들어 있는 입차 시간을 이용해서 주차 시간을 계산하는 과정을 구현한 것이다.

마지막으로 , line33 ~ 41)에서 보면 출차에 대해서 한번 더 구현해 놓은 것인데 위의 코드가 필요한 이유는 출차 시간이 주어지지 않는 경우가 존재하기 때문이다. 출차 시간이 주어지지 않는 경우에는 "23:59"에 출차했음을 의미한다고 문제에서 제시 되어 있다. 따라서, stack이 비어있지 않다는 것은, 해당 차량의 입차 시간만 있고 출차 정보가 없다는 것을 의미하고 이 경우에는 23:59를 기준으로 주차 시간을 계산해 주었다.

 

#2. 정답 구하기

정답을 구하는 과정은 문제에서 제시되어 있는 대로 구하면 된다.. 별다른 특별한 방법을 사용하지도 않았고 문제에서 제시한 대로 계산식 대로 계산만 해 주었다. 그런데 ! 여기서 아까 위에서 이야기 했던, 차량의 번호를 1번부터 mapping 시키는 이유에 대해서 조금 더 이야기 해보자.

만약, 위에서 이야기 했던 1번 부터 mapping 시키는 과정 없이 그냥 차량번호를 그대로 int형으로 변환만 시켜서 진행했다고 가정해보자. 예를 들어서 "1234"라는 차량번호를 '1234'라고 변환해서 문제 해결을 진행했다고 가정해 보는 것이다.

그럼, 우리는 주차 누적 시간들을 저장하기 위해서 위의 코드에서 사용된 totalTime[] 이라는 변수를 10,000칸을 만들고 진행을 해도 문제가 전혀 없을 것이다. 그럼 1111 ~ 9999 까지의 차량 중에서 딱 10대가 문제의 입력으로 주어졌다고 가정해보자. 우리는 이 10 대를 위해서 배열을 10,000칸을 선언해서 0번 Index부터 999번 Index까지는 사용하지도 않을 것이고, 이 10대의 차량을 위해서 1111 부터 9999까지 모두 탐색을 해봐야 한다. 그렇다면, 존재하는 차량의 번호들만 별도의 Vector와 같은 자료구조에 넣어서 관리를 한다면 ?? 예를 들어서 vector에 존재하는 차량번호인 { "1234", "2345", "3456", "4567" ,"5678" .... } 이런식으로 저장해놓고 Vector에서 하나씩 빼오면서 해당 Index만 탐색을 하게 된다면 이 문제는 해결되지 않을까 ??

충분히 해결될 것이고 저렇게 하지 않아도 애초에 크게 문제가 발생하지는 않을 것이다. 그런데 저 10대의 차량을 위해서 10,000칸을 선언해야 하는 것 자체가 약간의 낭비라고 생각을 했다. 그래서 본인은 이러한 낭비를 줄이기 위해서 그리고 이를 통해서 탐색 시간을 줄이기 위해서 int형 숫자 1번부터 차량을 순차적으로 mapping 시킨 것이다.

 

최종적으로는 별도의 Vector를 선언 후, Vector에 <전체 주차 시간 , 차량의 원래 번호> 를 저장해서 정렬 후 전체 주차 시간만 빼내서 정답을 도출하였다. 이 과정에서 "차량의 원래 번호" 가 필요하기 때문에 #1 - 1)에서 string형태의 4자리 차량 번호를 1번부터 순차적으로 증가하는 번호로 매핑시키는 과정과 동시에, 이 번호가 의미하는 차량의 원래 번호 또한 저장을 한 것이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <sstream>
#include <cmath>
#include <stack>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;
 
int totalTime[1010];
int totalCarNum;
int carList[1010];
map<string, int> carNum_Map;
 
bool Cmp(pair<int, int> A, pair<int, int> B) {
    return A.second < B.second ? true : false;
}
 
int invertTime(string time) {
    string sHour = time.substr(0, 2);
    string sMinute = time.substr(3, 2);
    int hour = stoi(sHour) * 60;
    int minute = stoi(sMinute);
    return hour + minute;
}
 
void findEntranceTime(vector<string> records) {
    int num = 1;
    stack<int> carStack[1010];
    for (auto str : records) {
        stringstream streamStr(str);
        string stime;
        string scarNum;
        string state;
        streamStr >> stime >> scarNum >> state;
        
        if (carNum_Map[scarNum] == 0) {
            carList[num] = stoi(scarNum);
            carNum_Map[scarNum] = num++;
        }
 
        int time = invertTime(stime);
 
        if (state == "IN") {
            carStack[carNum_Map[scarNum]].push(time);
        } else {
            int entranceTime = carStack[carNum_Map[scarNum]].top();
            int resultTime = time - entranceTime;
            totalTime[carNum_Map[scarNum]] += resultTime;
            carStack[carNum_Map[scarNum]].pop();
        }
    }
 
    for (int i = 1; i < num; i++) {
        if(carStack[i].empty() == true) {
            continue;
        }
        
        int resultTime = invertTime("23:59") - carStack[i].top();
        totalTime[i] += resultTime;
        carStack[i].pop();
    }
 
    totalCarNum = num;
}
 
vector<int> findAnswer(vector<int> fees) {
    vector<pair<int, int>> res;
 
    for (int i = 1; i < totalCarNum; i++) {
        int time = totalTime[i];
        if (time <= fees[0]) {
            res.push_back(make_pair(fees[1],carList[i]));
        } else {
            int overTime = time - fees[0];
            int overCost = overTime % fees[2] == 0 ? (overTime/fees[2]) * fees[3]  : ((overTime / fees[2])+ 1) * fees[3];
            int totalcost = overCost + fees[1];
            res.push_back(make_pair(totalcost, carList[i]));
        }
    }
    sort(res.begin(), res.end(), Cmp);
    vector<int> answer;
    for (auto data : res) {
        answer.push_back(data.first);
    }
    return answer;
}
 
vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    findEntranceTime(records);
    answer = findAnswer(fees);
    return answer;
}