[프로그래머스 Lv.2] (C++) 방금그곡

winluck·2024년 5월 15일
0

Algorithm

목록 보기
5/8

https://school.programmers.co.kr/learn/courses/30/lessons/17683#

카카오는 시간계산을 참 좋아한다.

문제 설명

문제에서 추출할 수 있는 정보는 다음과 같다.

  • <시작시각,종료시각,음악제목,악보>의 문자열이 차례대로 주어진다.
  • 음악은 재생시각이 악보의 길이를 넘어서면 처음부터 다시 반복된다.
  • 특정 멜로디 m을 포함하고 있는 음악을 찾아야 하며, 여러 개 존재하면 재생시간이 가장 길고, 재생시간이 같다면 음악 입력 순서가 가장 빠른 음악의 제목을 반환해야 한다.
  • C와 C#은 다른 음이다.

해결 과정

먼저 시작시각과 종료시각을 통해 총 재생시간을 계산한다.

int getTime(string s1, string s2){ // 시간 계산
    int hour1 = stoi(s1.substr(0, 2));
    int minute1 = stoi(s1.substr(3, 2));
    int hour2 = stoi(s2.substr(0, 2));
    int minute2 = stoi(s2.substr(3, 2));
    
    int gap = minute2 - minute1;
    if(gap < 0){
        hour2--;
        gap += 60;
    }
    gap += (hour2-hour1) * 60;
    return gap;
}

다음으로, 계산한 재생시간에 따른 음악 문자열을 산출한다.
이때 음악 문자열의 알파벳이 #이 붙어있다면 이를 반영해주어야 한다. (A != A#)

string getMusic(int time, string s){ // 재생 시간에 따른 음악 산출
    string str = "";
    vector<string> v; // #으로 끝나는 경우 #도 포함해야 함
    for(int i=0; i<s.size(); i++){
        if(i < s.size()-1 && s[i+1] == '#'){
            v.push_back(s.substr(i, 2));
            i++;
        } else {
            string a = "";
            a += s[i];
            v.push_back(a);
        }
    }
    
    int len = v.size();
    for(int i=0; i<time; i++){
        str += v[i % len];
    }
    return str;
}

음악 문자열 산출이 끝났다면, 찾으려는 문자열 m이 존재하는지 판정한다.
이때 m을 찾았을 때 마지막 알파벳 끝에 #가 붙는지 추가로 확인해야 한다.
(ABC != ABC#)

int nowtime = getTime(started, finished); 
string now = getMusic(nowtime, origin);

if(now.size() < m.size()) continue;
for(int j=0; j<=now.size()-m.size(); j++){
	if(now.substr(j, m.size()) == m){
		if(now[j+m.size()] != '#'){
			candi.push_back(music(i, nowtime, name));
		}
	}
}

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
struct music { // 정렬 및 정답 반환을 위한 음악 구조체
    int idx, time;
    string name;
    
    music(int a, int b, string c){
        idx = a;
        time = b;
        name = c;
    }
};

bool cmp(music m1, music m2){ // 총 시간 내림차순 + 등장 오름차순
    if(m1.time == m2.time){
        return m1.idx < m2.idx;
    }
    return m1.time > m2.time;
}

int getTime(string s1, string s2){ // 시간 계산
    int hour1 = stoi(s1.substr(0, 2));
    int minute1 = stoi(s1.substr(3, 2));
    int hour2 = stoi(s2.substr(0, 2));
    int minute2 = stoi(s2.substr(3, 2));
    
    int gap = minute2 - minute1;
    if(gap < 0){
        hour2--;
        gap += 60;
    }
    gap += (hour2-hour1) * 60;
    return gap;
}

string getMusic(int time, string s){ // 재생 시간에 따른 음악 산출
    string str = "";
    vector<string> v; // #으로 끝나는 경우 #도 포함해야 함
    for(int i=0; i<s.size(); i++){
        if(i < s.size()-1 && s[i+1] == '#'){
            v.push_back(s.substr(i, 2));
            i++;
        } else {
            string a = "";
            a += s[i];
            v.push_back(a);
        }
    }
    
    int len = v.size();
    for(int i=0; i<time; i++){
        str += v[i % len];
    }
    return str;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "";
    vector<music> candi;
    
    for(int i=0; i<musicinfos.size(); i++){
        string started = musicinfos[i].substr(0, 5); // 시작시각
        string finished = musicinfos[i].substr(6, 5); // 종료시각
        string other = musicinfos[i].substr(12);
        string name = ""; // 음악 이름
        string origin = ""; // 음악 문자열
        for(int j=0; j<other.size(); j++){
            if(other[j] == ','){
                name = other.substr(0, j);
                origin = other.substr(j+1);
                break;
            }
        }
        int nowtime = getTime(started, finished); 
        string now = getMusic(nowtime, origin);

        if(now.size() < m.size()) continue;
        for(int j=0; j<=now.size()-m.size(); j++){
            if(now.substr(j, m.size()) == m){
                if(now[j+m.size()] != '#'){
                    candi.push_back(music(i, nowtime, name));
                }
            }
        }
    }
    
    if(candi.empty()) return "(None)"; // 없는 경우 None
    sort(candi.begin(), candi.end(), cmp); // 조건에 따라 정렬
    return candi[0].name;
}
profile
Discover Tomorrow

0개의 댓글