[백준][C++] 21942 부품 대여장

21942. 부품 대여장

21942번: 부품 대여장

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

흘러가는 로직은 나쁘지 않았지만, 안에서 예상치 못한 실수가 자꾸자꾸 있었던 문제. 문자열과 해시를 다루어서 재미있는 문제였다.

 

알고리즘 설계

1. 대출이라면 이름과 현재 시간을 분으로 바꾼 값을 저장한다.
이때 같은 사람이 똑같은 부품을 빌렸는지 확인.

 

2. 반납이라면 대출 목록에서 같은 이름을 꺼낸다.
이때 대여 기간이 입력된 대여 기간보다 크다면 벌금!

 

3. 벌금은 (현재 대여 기간 - 지켜야할 대여 기간) x 벌금이다.

그리고 내가 한 다채로운 실수들을 소개하자면...

 

1. 오버플로우

(벌금 * 초과 대여 기간(분))은 벌금의 최댓값이 4000이고, 기간의 단위가 분이기 때문에 int로 담을 수 없었다. 그래서 오버플로우가 발생했다...

    // int를...
    map<string, int> fineReports;

    // long long으로! =>
    map<string, long long> fineReports;

2. +1월

처음엔 아무 생각 없이 구글에 month to minute을 검색해서 43800을 복사해서 붙여놨지만... 저 미심쩍은 근삿값이라는 달마다 일이 다를 수도 있다는 당연한 사실을 깨달은 뒤에...

int monthDays[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int MonthToDay(int month)
{
    int days = 0;

    for (int i = 0; i < month; i++)
        days += monthDays[i];

    return days;
}    

달을 입력하면 일수를 주는 간단한 함수를 만들었는데... 여기서 또 오류가 있었다.

예를 들어 1월 23일을 입력하면 31 + 23 = 52일이 되는 것. 2월 23일이 되버린 것이다. 그리고 이걸 눈치채지 못해서 삼십 여분을 날린...

int monthDays[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int MonthToDay(int month)
{
    if (month == 1)return 0;

    int days = 0;

    for (int i = 0; i < month - 1; i++)
        days += monthDays[i];

    return days;
}    

월별로 고쳐주었다.

 

3. 한 부품만 빌릴 수 있다!

처음엔 대여할 수 있는 부품이 하나인 줄 알고 부품의 이름을 Key 값으로 map을 만들어서 썼지만...

struct user
{
    string name;
    int rentalTime;
};

// key => 부품의 이름
// value => 사용자 정보
map<string, map<string, user>> rentals;

분명 위 실수를 다 고치고 반례 출력값까지 맞았는데... 생각하고 있다가 그 어디에도 부품이 하나다!라는 말이 없다는 것을 깨달았다.

// key => 부품의 이름
// value => key => 사용자 이름
// value => value => 사용자 정보
map<string, map<string, user>> rentals;    

그래서 map을 이중으로 써주었다. 부품을 여러 개 빌려갈 수는 있지만, 한 부품을 한 사람이 반납하지 않고 여러번 빌려가는 것은 안되기 때문에 부품마다 유저를 키값으로 한 맵을 만들었다.

시각적으로 표현하자면...

여기서...

이렇게 된 것!

 

 

코드

#include<iostream>
#include<string>
#include<map>
using namespace std;

// 각 달의 일 수
int monthDays[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
struct user
{
	string name;
	int rentalTime;
};

// 달 => 일 변환
int MonthToDay(int month)
{
	if (month == 1)return 0;

	int days = 0;

	for (int i = 0; i < month - 1; i++)
		days += monthDays[i];

	return days;
}

int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	int len;
	int fine;
	string sDuration;
	int duration = 0;
	map<string, map<string, user>> rentals;
	map<string, long long> fineReports;

	cin >> len >> sDuration >> fine;

	duration += stoi(sDuration.substr(0, 3)) * 1440;		// Day
	duration += stoi(sDuration.substr(4, 2)) * 60;			// Hour	
	duration += stoi(sDuration.substr(7, 2));				// Minute

	for (int i = 0; i < len; i++)
	{
		string ymd, time, part, name;
		int curTime = 0;
		cin >> ymd >> time >> part >> name;

		curTime += MonthToDay(stoi(ymd.substr(5, 2))) * 1440;	// Month
		curTime += stoi(ymd.substr(8, 2)) * 1440;				// Day
		curTime += stoi(time.substr(0, 2)) * 60;				// Hour
		curTime += stoi(time.substr(3, 2));						// Minute

		// 대여 목록에서 찾는다면
		if (rentals.find(part) != rentals.end() && rentals[part].find(name) != rentals[part].end())
		{
			int rentalDuration = curTime - rentals[part][name].rentalTime;

			if (rentalDuration > duration)
			{
            	// 대여 기간을 넘었다면 벌금 부과
				fineReports[name] += (long long)((rentalDuration - duration) * fine);
			}
		
        	// 리셋
			rentals[part].erase(name);

			if (rentals[part].empty())
				rentals.erase(part);
		}
		else
			rentals[part][name] = { name, curTime };
	}


	// 벌금을 낼 사람이 없다면 -1 출력
	if (fineReports.empty()) cout << -1;
	else
	{
		for (auto user : fineReports)
			cout << user.first << " " << user.second << '\n';
	}
}

 

문자열이랑 해시를 같이 다룰 수 있어서 재미있었던 문제였다.