Programmers [3차] 방금그곡[C++, Java]

junto·2024년 7월 2일

Algorithms Implementation programmers

programmers

목록 보기

40/66

문제

Programmers [3차] 방금그곡

핵심

입력의 크기가 작아 대략 $O(N^2)$ 이하 알고리즘을 사용한다.
방송된 곡의 정보와 네오가 기억하는 멜로디가 주어진다. 곡의 멜로디는 노래가 시작하는 동안 계속해서 반복된다. 네오가 기억하는 멜로디가 반복된 곡의 멜로디에 있는지 확인하고, 있다면 곡의 제목 없다면 "None"을 반환한다. 같은 멜로디가 여러 곡에 있다면 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 이를 위해 노래 제목, 멜로디, 재생 시간을 기록하는 tuple 자료구조를 이용하였다.

["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]

vector<tuple<string, string, int>> music; // title, melody, playingTime

음악 정보가 주어지면 몇 분 동안 노래가 반복되는지, 노래가 반복되면서 만드는 멜로디를 파싱해서 알아두어야 한다. 문자열 파싱이 익숙지 않아서 개인적으로 까다롭게 느껴졌었다.

istringstream iss(m);
vector<string> split;
string tmp;
while (getline(iss, tmp, ',')) {
	split.push_back(tmp);
}
int st = stoi(split[0]) * 60 + stoi(split[0].substr(3));
int end = stoi(split[1]) * 60 + stoi(split[1].substr(3));
int playing = end - st;

노래 플레이 시간을 위처럼 구현하였다. 멜로디를 구현할 때 실수 하기가 쉽다. 멜로디에는 #이 붙을 수 있는데, C#의 경우 문자가 2개여도 2개로 세면 안 된다. 따라서 문자가 '#'일 땐 시간을 줄이지 않았다. 하지만 C#이 마지막 멜로디라면 #을 붙이지 못하는 문제가 발생한다. 멜로디를 만들고, 마지막 커서가 '#'을 가리키고 있다면 추가로 #을 붙이는 처리를 해주었다.

int idx = 0;
string gasa = "";
int time = playing;
while (time) {
	char append = split[3][(idx % split[3].length())];
	gasa += append;
	++idx;
	if (append == '#') continue;
	--time;
}
if (split[3][(idx % split[3].length())] == '#') {
	gasa += '#';
}

네오가 기억하는 멜로디가 "ABC"이고, 방송에 나온 멜로디가 "ABC#"이라면 다른 멜로디로 봐야 한다. 하지만 단순히 find함수를 쓰게 되면 해당 문자열이 포함되어 있기에 같은 멜로디로 처리가 된다. 즉, 이 부분을 처리해야 한다. 크게 두 가지 방법이 있다.

1. 사용자 정의 비교 함수 작성

match()함수를 작성하여 찾는 문자열이 다 있더라도 뒤에 #이 붙었다면 다른 문자열로 보는 처리를 하는 것이다. 아래와 같이 작성할 수 있다.

bool is_match(string& a, string& b) {
    if (a.length() < b.length()) return false;

    for (int i = 0; i < a.length() - b.length() + 1; ++i) {
        int idx = i;
        bool is_matched = true;
        for (int j = 0; j < b.length(); ++j) {
            if (a[idx + j] != b[j]) {
                is_matched = false;
                break;
            }
            if (j == b.length() - 1 && idx + j + 1 < a.length()) {
                if (a[idx + j + 1] == '#') is_matched = false;
            }
        }

        if (is_matched) return true;
    }
    return false;
}

2. #이 붙은 멜로디를 미리 다른 문자로 치환

#include <unordered_map>

string convert_sharp(string& m) {
	map['C'] = 'c';
	map['D'] = 'd';
	map['F'] = 'f';
	map['G'] = 'g';
	map['A'] = 'a';

    string tmp = "";
    for (int i = 0; i < m.size(); ++i) {
        if (m[i] == '#') {
            continue;
        }
        if (map.find(m[i]) != map.end() && i != m.size() - 1 && m[i + 1] == '#') {
            tmp += map[m[i]];
            ++i;
            continue;
        }
        tmp += m[i];
    }
    return tmp;
}

개선

2번 방식으로 미리 치환하고, KMP 알고리즘을 이용하면 기존 $O(N^2)$ 알고리즘을 $O(N + M)$ 에 해결할 수 있다.

코드

C++

풀이 1

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

using namespace std;

vector<tuple<string, string, int>> music;

bool is_match(string& a, string& b) {
    if (a.length() < b.length()) return false;

    for (int i = 0; i < a.length() - b.length() + 1; ++i) {
        int idx = i;
        bool is_matched = true;
        for (int j = 0; j < b.length(); ++j) {
            if (a[idx + j] != b[j]) {
                is_matched = false;
                break;
            }
            if (j == b.length() - 1 && idx + j + 1 < a.length()) {
                if (a[idx + j + 1] == '#') is_matched = false;
            }
        }

        if (is_matched) return true;
    }
    return false;
}

void make_music(string& m) {
    
    istringstream iss(m);
    vector<string> split;
    string tmp;
    while (getline(iss, tmp, ',')) {
        split.push_back(tmp);
    }
    int st = stoi(split[0]) * 60 + stoi(split[0].substr(3));
    int end = stoi(split[1]) * 60 + stoi(split[1].substr(3));
    int playing = end - st;    

    int idx = 0;
    string gasa = "";
    int time = playing;
    while (time) {
        char append = split[3][(idx % split[3].length())];
        gasa += append;
        ++idx;
        if (append == '#') continue;
        --time;
    }
    if (split[3][(idx % split[3].length())] == '#') {
        gasa += '#';
    }
    music.push_back({split[2], gasa, playing});
}

string solution(string m, vector<string> musicinfos) {
    
    for (int i = 0; i < musicinfos.size(); ++i) {
        make_music(musicinfos[i]);
    }
    
    stable_sort(music.begin(), music.end(), [](auto& a, auto& b) {
        return get<2>(a) > get<2>(b);
    });

    for (auto e : music) {
        if (is_match(get<1>(e), m)) {
            return get<0>(e);
        }
    }
    return "(None)";
}

풀이 2

unordered_map<char, char> map;

string convert_sharp(string& m) {
    string tmp = "";
    for (int i = 0; i < m.size(); ++i) {
        if (m[i] == '#') {
            continue;
        }
        if (map.find(m[i]) != map.end() && i != m.size() - 1 && m[i + 1] == '#') {
            tmp += map[m[i]];
            ++i;
            continue;
        }
        tmp += m[i];
    }
    return tmp;
}

string solution(string m, vector<string> musicinfos) {
    
    map['C'] = 'c';
    map['D'] = 'd';
    map['F'] = 'f';
    map['G'] = 'g';
    map['A'] = 'a';
    
    m = convert_sharp(m);
    ...

    for (auto e : music) {
        if (get<1>(e).find(m) != string::npos) {
            return get<0>(e);
        }
    }
    return "(None)";
}

Java

풀이 1

import java.util.*;

class Solution {
    class Music {
        String name;
        String gasa;
        int playing;

        Music(String name, String gasa, int playing) {
            this.name = name;
            this.gasa = gasa;
            this.playing = playing;
        }
    }

    private boolean isMatch(String a, String b) {
        if (a.length() < b.length()) return false;

        for (int i = 0; i <= a.length() - b.length(); ++i) {
            int idx = i;
            boolean isMatched = true;
            for (int j = 0; j < b.length(); ++j) {
                if (a.charAt(idx + j) != b.charAt(j)) {
                    isMatched = false;
                    break;
                }
                if (j == b.length() - 1 && idx + j + 1 < a.length()) {
                    if (a.charAt(idx + j + 1) == '#') isMatched = false;
                }
            }
            if (isMatched) return true;
        }
        return false;
    }

    private void makeMusic(String m, List<Music> musicList) {
        String[] split = m.split(",");
        int st = Integer.parseInt(split[0].substring(0, 2)) * 60 + Integer.parseInt(split[0].substring(3));
        int end = Integer.parseInt(split[1].substring(0, 2)) * 60 + Integer.parseInt(split[1].substring(3));
        int playing = end - st;

        int idx = 0;
        StringBuilder gasa = new StringBuilder();
        int time = playing;
        while (time > 0) {
            char append = split[3].charAt(idx % split[3].length());
            gasa.append(append);
            ++idx;
            if (append == '#') continue;
            --time;
        }
        if ((idx % split[3].length()) < split[3].length() && split[3].charAt(idx % split[3].length()) == '#') {
            gasa.append('#');
        }
        musicList.add(new Music(split[2], gasa.toString(), playing));
    }

    public String solution(String m, String[] musicinfos) {
        List<Music> musicList = new ArrayList<>();

        for (var e : musicinfos) {
            makeMusic(e, musicList);
        }

        musicList.sort((a, b) -> b.playing - a.playing);

        for (var e : musicList) {
            if (isMatch(e.gasa, m)) {
                return e.name;
            }
        }
        return "(None)";
    }
}

풀이 2

import java.util.*;

class Solution {

    private Map<Character, Character> map = new HashMap<>();

    private String convertSharp(String m) {
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < m.length(); ++i) {
            if (m.charAt(i) == '#') {
                continue;
            }
            if (map.containsKey(m.charAt(i)) && i != m.length() - 1 && m.charAt(i + 1) == '#') {
                tmp.append(map.get(m.charAt(i)));
                ++i;
                continue;
            }
            tmp.append(m.charAt(i));
        }
        return tmp.toString();
    }
    ...

    public String solution(String m, String[] musicinfos) {
        map.put('C', 'c');
        map.put('D', 'd');
        map.put('F', 'f');
        map.put('G', 'g');
        map.put('A', 'a');

        m = convertSharp(m);
		...
        for (var e : musicList) {
            if (e.gasa.contains(m)) {
                return e.name;
            }
        }
        return "(None)";
    }
}