이번에는 백준 2852번 NBA 농구 문제를 풀어보았습니다.
이 문제는 농구 경기에서 각 팀이 몇 분 몇 초 동안 이기고 있었는지를 구하는 문제입니다.
처음에는 현재 이기고 있는 팀과 이기기 시작한 시간을 직접 관리하는 방식으로 풀었고,
이후에는 시간을 전부 초 단위로 변환해서 조금 더 간단하게 개선해보았습니다.
문제 설명
동혁이는 NBA 농구 경기를 즐겨 봅니다.
농구 경기는 정확히 48분 동안 진행되고,
골이 들어갈 때마다 득점한 팀과 득점 시간이 주어집니다.
이때 1번 팀과 2번 팀이 각각 몇 분 동안 이기고 있었는지를 출력하면 됩니다.
시간은 MM:SS 형식으로 주어지고,
출력도 같은 형식으로 해야 합니다.
예를 들어 어떤 팀이 01:00부터 03:00까지 이기고 있었다면,
그 팀의 승리 시간에는 02:00이 더해집니다.
풀이 아이디어
이 문제에서 중요한 것은 단순히 점수를 세는 것이 아니라,
어느 팀이 언제부터 언제까지 이기고 있었는지를 구하는 것입니다.
점수가 바뀌는 순간마다 경기 상태는 크게 세 가지입니다.
- 1번 팀이 이기고 있음
- 2번 팀이 이기고 있음
- 동점
리드 시간이 시작되는 순간은
동점 상태에서 한 팀이 앞서가기 시작하는 순간입니다.
반대로 리드 시간이 끝나는 순간은
이기고 있던 팀이 있다가 다시 동점이 되는 순간입니다.
따라서 현재 점수뿐만 아니라,
현재 이기고 있는 팀과 그 팀이 이기기 시작한 시간도 관리해야 합니다.
V1 코드
처음에는 시간을 문자열 형태로 관리했습니다.
시간이 MM:SS 형식으로 주어지기 때문에,
substr을 이용해서 분과 초를 따로 추출한 뒤 직접 계산하는 방식입니다.
#include <bits/stdc++.h>
using namespace std;
int N;
int score[2];
string getWinningTime(string st_time, string ed_time){
int st_time_minutes = atoi(st_time.substr(0,2).c_str());
int ed_time_minutes = atoi(ed_time.substr(0,2).c_str());
int st_time_seconds = atoi(st_time.substr(3,2).c_str());
int ed_time_seconds = atoi(ed_time.substr(3,2).c_str());
int ret_minutes = ed_time_minutes - st_time_minutes;
int ret_seconds;
if (st_time_seconds > ed_time_seconds) {
ret_minutes -= 1;
ret_seconds = ed_time_seconds + 60 - st_time_seconds;
} else {
ret_seconds = ed_time_seconds - st_time_seconds;
}
string ret_minutes_str = to_string(ret_minutes);
string ret_seconds_str = to_string(ret_seconds);
if (ret_minutes >= 0 && ret_minutes <= 9)
ret_minutes_str = "0" + to_string(ret_minutes);
if (ret_seconds >= 0 && ret_seconds <= 9)
ret_seconds_str = "0" + to_string(ret_seconds);
return ret_minutes_str + ":" + ret_seconds_str;
}
void addWinningTime(string &target_winning_time, string time){
int target_time_minutes = atoi(target_winning_time.substr(0,2).c_str());
int plus_time_minutes = atoi(time.substr(0,2).c_str());
int target_time_seconds = atoi(target_winning_time.substr(3,2).c_str());
int plus_time_seconds = atoi(time.substr(3,2).c_str());
int ret_minutes = target_time_minutes + plus_time_minutes;
int ret_seconds = target_time_seconds + plus_time_seconds;
if (ret_seconds > 60) {
ret_minutes += 1;
ret_seconds -= 60;
}
string ret_minutes_str = to_string(ret_minutes);
string ret_seconds_str = to_string(ret_seconds);
if (ret_minutes >= 0 && ret_minutes <= 9)
ret_minutes_str = "0" + to_string(ret_minutes);
if (ret_seconds >= 0 && ret_seconds <= 9)
ret_seconds_str = "0" + to_string(ret_seconds);
target_winning_time = ret_minutes_str + ":" + ret_seconds_str;
}
string team1_winning_time = "00:00";
string team2_winning_time = "00:00";
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
int before_winning_team = -1;
string before_winning_start_time;
string current_time;
string current_winning_time;
for (int i = 0; i < N; i++) {
int team;
cin >> team >> current_time;
score[team - 1]++;
if (score[0] == score[1]) {
if (before_winning_team == 1) {
current_winning_time = getWinningTime(before_winning_start_time, current_time);
addWinningTime(team1_winning_time, current_winning_time);
before_winning_team = -1;
} else if (before_winning_team == 2) {
current_winning_time = getWinningTime(before_winning_start_time, current_time);
addWinningTime(team2_winning_time, current_winning_time);
before_winning_team = -1;
}
} else {
if (score[0] > score[1] && before_winning_team != 1) {
before_winning_team = 1;
before_winning_start_time = current_time;
} else if (score[0] < score[1] && before_winning_team != 2) {
before_winning_team = 2;
before_winning_start_time = current_time;
}
}
}
if (before_winning_team == 1) {
current_winning_time = getWinningTime(before_winning_start_time, "48:00");
addWinningTime(team1_winning_time, current_winning_time);
} else if (before_winning_team == 2) {
current_winning_time = getWinningTime(before_winning_start_time, "48:00");
addWinningTime(team2_winning_time, current_winning_time);
}
cout << team1_winning_time << "\n" << team2_winning_time;
return 0;
}V1 풀이 흐름
V1에서는 현재 이기고 있는 팀을 before_winning_team으로 관리했습니다.
int before_winning_team = -1;값의 의미는 다음과 같습니다.
-1 : 현재 동점
1 : 1번 팀이 이기는 중
2 : 2번 팀이 이기는 중처음에는 어느 팀도 이기고 있지 않으므로 -1로 초기화했습니다.
득점 정보가 들어오면 먼저 해당 팀의 점수를 증가시킵니다.
score[team - 1]++;그 후 점수 상태를 확인합니다.
만약 before_winning_team이 -1이고,
현재 두 팀의 점수가 같지 않다면 한 팀이 새롭게 이기기 시작한 것입니다.
이때는 현재 이기고 있는 팀과 시간을 저장합니다.
before_winning_team = 1;
before_winning_start_time = current_time;반대로 현재 점수가 같아졌고,
before_winning_team이 -1이 아니라면 이전까지 이기고 있던 팀의 승리 시간이 끝난 것입니다.
if (score[0] == score[1])이 경우에는 before_winning_start_time부터 current_time까지의 시간을 계산한 뒤,
해당 팀의 누적 승리 시간에 더해줍니다.
current_winning_time = getWinningTime(before_winning_start_time, current_time);
addWinningTime(team1_winning_time, current_winning_time);그리고 다시 동점 상태가 되었으므로
before_winning_team을 -1로 초기화합니다.
before_winning_team = -1;V1에서 시간 계산 방식
V1에서는 시간이 문자열로 주어지기 때문에,
substr을 사용해서 분과 초를 따로 추출했습니다.
st_time.substr(0,2);
st_time.substr(3,2);그리고 atoi를 이용해서 문자열을 숫자로 바꿔 계산했습니다.
int st_time_minutes = atoi(st_time.substr(0,2).c_str());
int st_time_seconds = atoi(st_time.substr(3,2).c_str());시간 차이를 계산할 때 초끼리 바로 뺄 수 없는 경우가 있습니다.
예를 들어 01:50부터 02:10까지의 차이를 구하면
초는 10 - 50이 되기 때문에 바로 계산할 수 없습니다.
그래서 분에서 1을 빌려온 뒤 계산했습니다.
if (st_time_seconds > ed_time_seconds) {
ret_minutes -= 1;
ret_seconds = ed_time_seconds + 60 - st_time_seconds;
}또한 출력 형식을 유지하기 위해
분이나 초가 한 자리 수라면 앞에 0을 붙여주었습니다.
if (ret_seconds >= 0 && ret_seconds <= 9)
ret_seconds_str = "0" + to_string(ret_seconds);V2 코드
V2에서는 시간을 문자열로 계속 다루지 않고,
분을 초로 바꿔서 계산한 뒤 마지막에 다시 MM:SS 형식으로 바꾸었습니다.
#include <bits/stdc++.h>
using namespace std;
int N;
int team_1_winning_time;
int team_2_winning_time;
void calculate_winning_time(string st, string ed, int &winning_team) {
int st_time_minutes = atoi(st.substr(0,2).c_str());
int ed_time_minutes = atoi(ed.substr(0,2).c_str());
int st_time_seconds = atoi(st.substr(3,2).c_str());
int ed_time_seconds = atoi(ed.substr(3,2).c_str());
st_time_seconds += 60 * st_time_minutes;
ed_time_seconds += 60 * ed_time_minutes;
winning_team += (ed_time_seconds - st_time_seconds);
}
string make_time(int seconds){
int minutes = seconds / 60;
seconds = seconds % 60;
string minutes_str = "";
string seconds_str = "";
minutes_str = to_string(minutes);
seconds_str = to_string(seconds);
if (minutes >= 0 && minutes <= 9) {
minutes_str = "0" + to_string(minutes);
}
if (seconds >= 0 && seconds <= 9) {
seconds_str = "0" + to_string(seconds);
}
return minutes_str + ":" + seconds_str;
}
int main() {
cin >> N;
int score[2] = {0, 0};
string prev_time;
for (int i = 0; i < N; i++) {
int team;
string time;
cin >> team >> time;
if (score[1] > score[0]) {
calculate_winning_time(prev_time,time, team_2_winning_time);
}
if (score[0] > score[1]) {
calculate_winning_time(prev_time,time, team_1_winning_time);
}
score[team-1]++;
prev_time = time;
}
if (score[1] > score[0]) {
calculate_winning_time(prev_time,"48:00", team_2_winning_time);
}
if (score[0] > score[1]) {
calculate_winning_time(prev_time,"48:00", team_1_winning_time);
}
cout << make_time(team_1_winning_time) << "\n" << make_time(team_2_winning_time);
return 0;
}V2 풀이 흐름
V2에서는 V1처럼 “언제부터 이기기 시작했는지”를 직접 저장하지 않았습니다.
대신 경기 시간을 구간 단위로 나눠서 생각했습니다.
득점이 들어오는 순간에만 점수가 바뀌기 때문에,
이전 득점 시간부터 현재 득점 시간까지는 경기 상태가 변하지 않습니다.
예를 들어 이전 시간이 10:00이고 현재 득점 시간이 13:00이라면,10:00 ~ 13:00 구간 동안 이기고 있던 팀에게 3분을 더해주면 됩니다.
그래서 V2에서는 점수를 갱신하기 전에
현재 점수 기준으로 어느 팀이 이기고 있었는지를 먼저 확인합니다.
if (score[1] > score[0]) {
calculate_winning_time(prev_time,time, team_2_winning_time);
}
if (score[0] > score[1]) {
calculate_winning_time(prev_time,time, team_1_winning_time);
}그 다음 이번 득점을 반영합니다.
score[team-1]++;그리고 현재 시간을 다음 구간의 시작 시간으로 저장합니다.
prev_time = time;이렇게 하면 매 득점 시점마다
prev_time부터 time까지의 구간을 처리할 수 있습니다.
V2에서 시간 계산 방식
V2에서는 시간 계산을 할 때 분과 초를 따로 계산하지 않습니다.
먼저 시간을 초 단위로 바꿉니다.
st_time_seconds += 60 * st_time_minutes;
ed_time_seconds += 60 * ed_time_minutes;이렇게 바꾸면 시간 차이는 단순히 뺄셈으로 구할 수 있습니다.
winning_team += (ed_time_seconds - st_time_seconds);이 방식은 V1보다 훨씬 간단합니다.
V1에서는 분과 초를 따로 계산해야 했고,
초가 부족하면 분에서 1을 빌려오는 처리도 필요했습니다.
하지만 V2에서는 모든 시간을 초로 바꾸기 때문에
그런 예외 처리가 필요 없어졌습니다.
마지막 출력 직전에만 다시 MM:SS 형식으로 바꿔주면 됩니다.
cout << make_time(team_1_winning_time) << "\n" << make_time(team_2_winning_time);마지막 48:00 처리
모든 득점 정보를 처리한 뒤에도 한 팀이 계속 이기고 있을 수 있습니다.
농구 경기는 정확히 48:00까지 진행되므로,
마지막 득점 시간부터 48:00까지의 시간도 따로 더해줘야 합니다.
if (score[1] > score[0]) {
calculate_winning_time(prev_time,"48:00", team_2_winning_time);
}
if (score[0] > score[1]) {
calculate_winning_time(prev_time,"48:00", team_1_winning_time);
}이 부분을 빼먹으면 마지막 리드 구간이 누락됩니다.
V1에서 V2로 개선한 점
V1과 V2의 가장 큰 차이는 시간을 다루는 방식입니다.
V1에서는 시간을 MM:SS 문자열 형태로 계속 다뤘습니다.
그래서 시간 차이를 구하거나 시간을 더할 때마다
분과 초를 따로 추출하고, 다시 문자열로 바꾸는 과정이 필요했습니다.
반면 V2에서는 시간을 초 단위 정수로 바꿔서 처리했습니다.
이렇게 하니 다음과 같은 장점이 있었습니다.
- 시간 차이를 단순 뺄셈으로 구할 수 있음
- 승리 시간을 정수 덧셈으로 누적할 수 있음
- 분에서 1을 빌려오는 예외 처리가 필요 없어짐
- 출력 형식 변환은 마지막에만 하면 됨
- 코드 흐름이 더 짧고 단순해짐
또한 V1에서는 before_winning_team, before_winning_start_time을 이용해서
리드 시작 시점과 종료 시점을 직접 관리했습니다.
반면 V2에서는 prev_time을 기준으로
이전 득점 시간부터 현재 득점 시간까지의 구간을 처리했습니다.
즉, V1은 상태 변화 중심의 풀이이고,
V2는 시간 구간 중심의 풀이라고 볼 수 있습니다.
개인적으로는 V2 방식이 더 깔끔하다고 느꼈습니다.
득점 사이에는 점수 상태가 바뀌지 않는다는 점을 이용하면,
매 구간마다 현재 이기고 있는 팀에게 시간을 더해주면 되기 때문입니다.
