[C++로 풀이] 방금그곡 ⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 방금그곡
난이도 ⭐⭐
🚀 문제
🚀 내 풀이 ⭕
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<string, int> a, pair<string, int> b) {
return a.second > b.second;
}
string solution(string m, vector<string> musicinfos) {
string answer = "";
vector<vector<string>> info(musicinfos.size());
vector<pair<string, int>> included;
// tokenizing with ','
for (int i = 0; i < musicinfos.size(); i++) {
string temp = "";
for (int j = 0; j < musicinfos[i].length(); j++) {
if (musicinfos[i][j] == ',') {
info[i].push_back(temp);
temp = "";
}
else
temp += musicinfos[i][j];
}
info[i].push_back(temp);
}
/* A# C# D# F# G# 는 각각 a,c,d,f,g 로 변경 */
// m 의 변경
for (int i = 0; i < m.length(); ) {
if (m[i] == '#') {
m[i - 1] = tolower(m[i - 1]);
m.erase(m.begin() + i);
}
else
i++;
}
// info 의 변경
for (int i = 0; i < info.size(); i++) {
for (int j = 0; j < info[i][3].length(); ) {
if (info[i][3][j] == '#') {
info[i][3][j - 1] = tolower(info[i][3][j - 1]);
info[i][3].erase(info[i][3].begin() + j);
}
else
j++;
}
}
for (int i = 0; i < info.size(); i++) {
// 시간(분) 구하기
int hours = stoi(info[i][1].substr(0, 2)) - stoi(info[i][0].substr(0, 2));
int minutes = stoi(info[i][1].substr(3, 2)) - stoi(info[i][0].substr(3, 2));
int time = 60 * hours + minutes;
// 원곡의 음 중 라디오에서 실제 재생된 음
int n = info[i][3].length();
if (time > n) {
string temp = "";
for (int count = 0; count < time; count++)
temp += info[i][3][count % n];
info[i][3] = temp;
}
else if (time < n)
info[i][3] = info[i][3].substr(0, time);
// 기억하는 음을 포함하는지 여부
n = info[i][3].length();
if (m.length() > n)
continue;
if (info[i][3].find(m) != string::npos)
included.push_back(make_pair(info[i][2], time));
}
if (included.empty())
return "(None)";
sort(included.begin(), included.end(), cmp);
answer = included[0].first;
return answer;
}
1️⃣ 콤마로 tokenizing
vector<vector<string>> info(musicinfos.size());
//...
for (int i = 0; i < musicinfos.size(); i++) {
string temp = "";
for (int j = 0; j < musicinfos[i].length(); j++) {
if (musicinfos[i][j] == ',') {
info[i].push_back(temp);
temp = "";
}
else
temp += musicinfos[i][j];
}
info[i].push_back(temp);
}
문자열은 쉼표를 기준으로 4 개 영역으로 이루어져있다. 시작시간 + 종료시간 + 곡제목 + 원곡음
각각의 musicinfos[i] 문자열 하나를 , 기준으로 4 개의 문자열로 쪼개 info[i] string vector에 추가한다. info는 musicinfos.size() 행과 4 열을 가진 이중 벡터가 될 것이다.
- info[i][0] 👉 시작 시간
- info[i][1] 👉 종료 시간
- info[i][2] 👉 곡 제목
- info[i][3] 👉 원곡 음
2️⃣ A# C# D# F# G# 는 각각 a,c,d,f,g 로 변경
// m 의 변경
for (int i = 0; i < m.length(); ) {
if (m[i] == '#') {
m[i - 1] = tolower(m[i - 1]);
m.erase(m.begin() + i);
}
else
i++;
}
// info 의 변경
for (int i = 0; i < info.size(); i++) {
for (int j = 0; j < info[i][3].length(); ) {
if (info[i][3][j] == '#') {
info[i][3][j - 1] = tolower(info[i][3][j - 1]);
info[i][3].erase(info[i][3].begin() + j);
}
else
j++;
}
}
"A#" 이건 쪼개서 볼 수 없는 하나의 음이기 때문에 하나의 문자로 봐야한다. 이 "A#"가 문자열 길이 2라고 판단되선 안되고 1로 판단되야 한다. 그래야 나중에 음의 개수를 문자열 길이로 비교하는데 있어 애로사항이 생기지 않는다. (음 1개당 재생이 1분걸리니까 나중에 원곡악보 문자열 길이와 재생된 시간을 비교할 것이다.) 따라서 그냥 A# C# D# F# G# 는 각각 a,c,d,f,g 로 바꿔주기로 했다. 하나의 문자로 변경.
#이라면- 앞 글자는 소문자로 변경
#는 삭제- 삭제되었으니
i++하지 않고 그 자리 그대로에서 다음 반복 진행
- 삭제되었으니
#이 아니라면 그냥i++다음 자리 반복 진행
3️⃣ 곡 정보들 순회 : 라디오에서 총 재생된 시간을 분(minutes)으로 구하기
for (int i = 0; i < info.size(); i++) {
// 시간(분) 구하기
int hours = stoi(info[i][1].substr(0, 2)) - stoi(info[i][0].substr(0, 2)); // = 종료 hours - 시작 hours
int minutes = stoi(info[i][1].substr(3, 2)) - stoi(info[i][0].substr(3, 2)); // = 종료 minutes - 시작 minutes
int time = 60 * hours + minutes;
음 하나 당 1분이기 때문에 분 단위로 총 재생된 시간을 구한다. 시간 형태는 "HH:MM"이다.
4️⃣ 곡 정보들 순회 : 원곡이 라디오에서 어떻게 재생이 되었는지
for (int i = 0; i < info.size(); i++) {
//...
int n = info[i][3].length(); // 원곡의 시간 (음 하나당 1분이므로 원곡악보 길이는 곧 분 단위의 원곡 시간이 됨)
if (time > n) {
string temp = "";
for (int count = 0; count < time; count++)
temp += info[i][3][count % n];
info[i][3] = temp;
}
else if (time < n)
info[i][3] = info[i][3].substr(0, time);
- 라디오에서 재생된 시간이 원곡 길이보다 크다면 👉 원곡이 반복되어 재생된 것
- 예를 들어 원곡은 ABCD 인데 라디오에서 재생된 시간은 10분이였다면 원곡이 라디오에서 재생된 형태는 “ABCDABCDAB” 가 됨.
- 라디오에서 재생된 시간이 원곡 길이보다 작다면 👉 원곡이 끝까지 재생되지 못하고 중간에 잘린 것
- 예를 들어 원곡은 ABCD 인데 라디오에서 재생된 시간은 2분이였다면 원곡이 라디오에서 재생된 형태는 “AB” 가 됨.
이렇게 진짜로 라디오에서 원곡이 어떻게 재생 되었는지의 형태를 info[i][3]에 다시 덮어 씌웠다.
5️⃣ 라디오에서 재생된 형태가 기억하는 음을 포함하는지 여부
vector<pair<string, int>> included;
//...
for (int i = 0; i < info.size(); i++) {
//...
n = info[i][3].length();
if (m.length() > n)
continue;
if (info[i][3].find(m) != string::npos)
included.push_back(make_pair(info[i][2], time));
- 라디오에서 재생된 형태의 음악이 기억하는 음보다 짧으면
- 기억하는 음을 포함하지 못하므로 답 후보가 될 수 없음
- 라디오에서 재생된 형태의 음악이 기억하는 음보다 길고 + 그 기억하는 음을 포함하고 있다면
includedvector 에 (곡제목 + 라디오에서재생된길이) 형태로 추가한다.included에는 기억하는 음을 포함하는 라디오 재생 곡만 모이게 된다.
6️⃣ 기억하는 음을 포함하는 라디오 재생 곡에서 재생길이 최대인 곡 찾기
if (included.empty())
return "(None)";
sort(included.begin(), included.end(), cmp); // 재생된 시간을 기준으로 내림차순 정렬
answer = included[0].first;
- 📢
included가 비어있다면, 즉 포함하는 라디오가 아무것도 없었다면 위 처리를 해주지 않으면 sort 에서 런타임 에러가 발생함 주의. - 기억하는 음을 포함하는 라디오 재생 형태가 여러개일 수 있으므로 라디오에서 재생된 길이가 최대인 것을 찾을 수 있게
included를 재생된 시간을 기준으로 내림차순 정렬하여 최대값을 가진 곡 제목을 찾는다. (정렬로 맨 앞에 위치하게 될 것)
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기