🖥️ CS/SW Expert 외의 Algorithms

프로그래머스 방금 그곡 (C++)

한국의 메타몽 2021. 4. 25. 19:41

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

 

코딩테스트 연습 - [3차] 방금그곡

방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV,

programmers.co.kr

2018년 카카오 블라인드 공채 3차 코딩테스트 - 난이도 LV2

 

이 문제가 LV2라는점이 신선했다.

막상 풀고나면 로직이 간단하지만, 큰 그림을 그리지 못하고 작은 부분들만 가지고 문제를 풀다가는 틀릴 수 밖에 없는 문제였다.

 

문제에서 유의해야할 점은 다음과 같다. 

1. C#과 같이 반올림 된 음계는 문자열의 길이는 2이지만 음계가 차지하는 시간은 결국 1이라는 점

2. 다음과 같은 케이스를 주의하자

-> m : CDCDE / 주어진 곡 : CDCDCDE

-> 만약 테스트 케이스 12번을 반복해서 틀린다면, 위의 케이스에서 실패한 것이다.

 

문제 풀이는 다음과 같다. 

1. 먼저 네오가 들은곡 m에서 반올림된 음계는 다른 문자로 치환한다.

나의 경우엔 D# -> d, C# - > c처럼 소문자로 치환했다.

치환할때 STL함수인 replace가 아닌, 직접 replaceAll라는 함수를 만들어 치환했다.

replace는 1개씩밖에 치환이 불가능한걸로 알고 있어서 고민끝에 직접 만들었다.

    replaceAll(m, "A#","a");
    replaceAll(m, "B#","b");
    replaceAll(m, "C#","c");
    replaceAll(m, "D#","d");
    replaceAll(m, "E#","e");
    replaceAll(m, "F#","f");
    replaceAll(m, "G#","g");
string replaceAll(string &m, string from, string to){
    int pos = 0;
    while((pos=m.find(from))!=-1){
        m.replace(pos,from.length(), to);
    }
    return m;
}

2. 시작시간과 종료시간을 모두 저장하여 플레이 시간을 분 단위로 치환한다.

이때 다음과 같이 시작 시간의 분이 종료 시간의 분보다 큰 경우를 고려해준다.

        h1 = musicinfos[i].substr(0,2);
        m1 = musicinfos[i].substr(3,2);
        h2 = musicinfos[i].substr(6,2);
        m2 = musicinfos[i].substr(9,2);
        t = abs(stoi(h2)-stoi(h1))*60;
        if(m1>m2){
            t-=60;
            t+=(stoi(m2)-stoi(m1))+60;
        }
        else t+=stoi(m2)-stoi(m1);

3. 타이틀을 추출해내서 저장해준다.

나는 바로 다음에 오는 음계를 편하게 저장해주기 위해, 종료 지점+1을 idx 변수에 저장해주었다.

        for(int j=12; j<musicinfos[i].size(); j++){
            if(musicinfos[i][j]==','){
                idx = j+1;
                break;
            }
            title += musicinfos[i][j];
        }

4. 음계를 모두 저장해주고 반올림된 음계를 치환해준다.

        for(int j=idx; j<musicinfos[i].size(); j++) scale+=musicinfos[i][j];
        replaceAll(scale, "A#","a");
        replaceAll(scale, "B#","b");
        replaceAll(scale, "C#","c");
        replaceAll(scale, "D#","d");
        replaceAll(scale, "E#","e");
        replaceAll(scale, "F#","f");
        replaceAll(scale, "G#","g");

5. 만약 플레이 타임이 곡의 길이보다 클 경우, 플레이 타임이 큰 만큼 곡의 길이를 늘려준다.

반대로 플레이 타임이 곡의 길이보다 작을 경우, 플레이 타임만큼 곡의 길이를 저장해준다.

        if(t/scale.size()>=1){
            int a = (t/scale.size())-1;
            string temp = scale;
            for(int j=0; j<a; j++) scale+=temp;
            for(int j=0; j<t%temp.size(); j++) scale+=temp[j];
        }
        else{
            string temp = "";
            for(int j=0; j<t; j++) temp+=scale[j];
            scale = temp;
        }

6. 곡에서 네오가 들은 곡 m을 찾을 수 있을 경우, 기존에 저장된 정답 음악의 플레이 타임보다 큰 경우에 한해서 값을 저장해준다.

        idx = scale.find(m);
        if(idx!=-1&&ans.first<t){
            ans.first = t;
            ans.second = title;
        }

7. for문을 종료하고 만약 답을 찾지 못할 경우, "(None)"을 출력해준다.

    answer = ans.second;
    if(answer=="") answer = "(None)";

 

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

using namespace std;

string replaceAll(string &m, string from, string to){
    int pos = 0;
    while((pos=m.find(from))!=-1){
        m.replace(pos,from.length(), to);
    }
    return m;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "";
    pair<int,string> ans = {0,""};
    replaceAll(m, "A#","a"); // 1. m에서 반올림된 음계를 모두 치환
    replaceAll(m, "B#","b");
    replaceAll(m, "C#","c");
    replaceAll(m, "D#","d");
    replaceAll(m, "E#","e");
    replaceAll(m, "F#","f");
    replaceAll(m, "G#","g");
    for(int i=0; i<musicinfos.size(); i++){
        int t = 0, idx = 0, pos = 0;
        string h1,h2,m1,m2, title = "", scale = "";
        h1 = musicinfos[i].substr(0,2); // 2. 시간을 분단위로 바꿔 계산
        m1 = musicinfos[i].substr(3,2);
        h2 = musicinfos[i].substr(6,2);
        m2 = musicinfos[i].substr(9,2);
        t = abs(stoi(h2)-stoi(h1))*60;
        if(m1>m2){
            t-=60;
            t+=(stoi(m2)-stoi(m1))+60;
        }
        else t+=stoi(m2)-stoi(m1);
        for(int j=12; j<musicinfos[i].size(); j++){ // 3. 타이틀을 저장
            if(musicinfos[i][j]==','){
                idx = j+1;
                break;
            }
            title += musicinfos[i][j];
        }
        for(int j=idx; j<musicinfos[i].size(); j++) scale+=musicinfos[i][j]; // 4. 악보 저장
        replaceAll(scale, "A#","a"); // 동시에 악보에서 반올림된 음계들을 모두 치환
        replaceAll(scale, "B#","b");
        replaceAll(scale, "C#","c");
        replaceAll(scale, "D#","d");
        replaceAll(scale, "E#","e");
        replaceAll(scale, "F#","f");
        replaceAll(scale, "G#","g");
        if(t/scale.size()>=1){ // 5. 플레임타임과 곡의 길이를 비교하여 곡을 저장
            int a = (t/scale.size())-1;
            string temp = scale;
            for(int j=0; j<a; j++) scale+=temp;
            for(int j=0; j<t%temp.size(); j++) scale+=temp[j];
        }
        else{
            string temp = "";
            for(int j=0; j<t; j++) temp+=scale[j];
            scale = temp;
        }
        idx = scale.find(m); // 6. 네오가 들은 곡이 있는지 찾아보기
        if(idx!=-1&&ans.first<t){
            ans.first = t;
            ans.second = title;
        }
    }
    answer = ans.second;
    if(answer=="") answer = "(None)";
    return answer;
}

 

문자열 라이브러리를 잘 활용못해서 공부가 필요하던 참이었는데, 이 문제 덕분에 문자열 라이브러리에 좀 더 친숙해질 수 있었다.