오늘의 문제는 지난 포스트에 이어서 “5635번 생일”.
이 문제를 풀 당시에는 사람이 한 명인 테스트 케이스가 문제인 줄 알았다. (사실 풀었으니까 됐다면서 그냥 넘어갔다) 그런데 다시 시험해보니 사람이 한 명인 테스트케이스도 문제가 없었다. 한참을 생각하다가 사람이 10명 이상만 되면 인덱스 값이 두 자리가 넘어가면서 생일의 날짜(day) 값이 변경되는, 일종의 오버플로우가 발생한다는 것을 발견했다. 따라서 사람이 가장 많은 테스트 케이스인 100명을 커버하기 위해 1000을 곱해야한다.
기존의 틀린 코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
int n, d, m, y, x;
string tmp;
vector <int> birth;
vector <string> name;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp >> d >> m >> y;
//x : 년+월+일+이름벡터 인덱스
x = y;
x *= 100;
x += m;
x *= 100;
x += d;
x *= 10;
x += i;
name.push_back(tmp);
birth.push_back(x);
}
sort(birth.begin(), birth.end()); //생년월일로 정렬
x = birth[n - 1]; //맨 뒷자리의 인덱스 추출
x %= 10;
cout << name[x] << endl; //인덱스를 활용하여 이름 출력
x = birth[0];
x %= 10;
cout << name[x] << endl;
return 0;
}
1000을 곱하면 100억자리가 돼서 int형을 넘는다. 이를 위해 각 변수들을 double형으로 바꾸고, double형은 %연산이 안 되기 때문에 비슷한 연산을 위해 좀 더 긴 작업이 필요했다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
double n, d, m, y, x;
int integer;
string tmp;
vector <double> birth;
vector <string> name;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> tmp >> d >> m >> y;
x = y;
x *= 100;
x += m;
x *= 100;
x += d;
x *= 1000;
x += i;
name.push_back(tmp);
birth.push_back(x);
}
sort(birth.begin(), birth.end());
x = birth[n - 1];
y = x / 1000;
integer = (int)y;
y = integer;
y *= 1000;
x -= y;
cout << name[x] << endl;
x = birth[0];
y = x / 1000;
integer = (int)y;
y = integer;
y *= 1000;
x -= y;
cout << name[x] << endl;
return 0;
}