[프로그래머스] 방금그곡 (2018 KAKAO BLIND RECRUITMENT)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/17683

 

 

이번 문제는 시간복잡도를 고려할 필요없는 파씽문제이다. 

그렇기에 연산적인 효율보다는 그냥 구현하기 편한대로 구현하였다.

 

<전체적인 알고리즘> 

1. 우선 파씽을 한다,  파씽을 하여 재생시간을 구해준 후 재생시간 동안만큼의 악보를 재작성한다.

2. 재작성한 악보에 주어진 음계m이 포함되어 있다면 조건과 일치하는 음악이다.

  2-1 조건과 일치한 음악 중에 재생 시간이 가장 긴 것을 고른다.

  2-2 재생 시간이 가장 긴 것 중에선 제일 앞쪽 제목을 선택

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

#include<iostream> #include<vector> #include<string>   using namespace std;   string m; vector<string> musicinfos;   string time_to_minute(string tmp)  //시간을 분으로 바꿔줌 {     string hour_str = tmp.substr(0, 2);     string minute_str = tmp.substr(3, 2);     int hour = stoi(hour_str);     int minute = stoi(minute_str);     int total= hour * 60 + minute;     return to_string(total); } string changing_sheet(string sheet)  //#음계를 소문자로 변경(분당 소문자 하나 맞추기 위해) {                                    // 물론 그냥 이 함수 안쓰고 #고려하며 바로 계산해줘도 됨     string tmp = "";     string score = "";     for (int i = 0; i < sheet.size(); i++)     {         if (sheet[i] == '#')         {             score += tolower(tmp[0]);             tmp = "";         }         else         {             score += tmp;             tmp = sheet[i];         }       }     if (tmp.size() > 0)score += tmp;     return score; }   vector<string> parsing(string str)   {     vector<string> v;     string tmp = str.substr(0, 5);     v.push_back(time_to_minute(tmp));  //시작 시간을 분으로 vector에 저장     tmp = str.substr(6, 5);     v.push_back(time_to_minute(tmp));   //끝나는 시간을 분으로 vector에 저장       tmp = "";     int i = 12;     for (;str[i]!=','; i++)     {         tmp += str[i];     }     i++;     v.push_back(tmp);  //음악 제목을 vector에 저장     tmp = "";     for (; i < str.size(); i++)     {         tmp += str[i];     }     tmp = changing_sheet(tmp);  //#음계는 소문자로     int playing_time = stoi(v[1]) - stoi(v[0]);  //재생 시간         string sheet = "";     int index = 0;     for (int i = 0; i < playing_time; i++)  //재생시간동안의 악보 작성     {         sheet += tmp[index];         index++;           if (index == tmp.size())index = 0;     }           v.push_back(sheet);  //재생된 만큼의 악보를 저장       return v; }   string solution(string m2, vector<string> musicinfos2) {           m=m2;     musicinfos=musicinfos2;           m = changing_sheet(m); //#붙은 건 소문자로 바꿔줌     int max_playing_time = 0;     string answer = "";     for (int i = 0; i < musicinfos.size(); i++)     {         vector<string> v = parsing(musicinfos[i]);           int index = v[3].find(m);         if (index >= 0)         {             if (stoi(v[1]) - stoi(v[0]) > max_playing_time)             {                 max_playing_time = stoi(v[1]) - stoi(v[0]);                 answer = v[2];             }         }     }           if (answer.empty())answer = "(None)";           return answer; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.