Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- dfs
- java
- 백트래킹
- CS
- 유니온 파인드
- 시뮬레이션
- 동적계획법
- 투 포인터
- 스택
- Effective Java
- 플로이드-와샬
- 이분탐색
- Kotlin
- 수학
- 후니의 쉽게 쓴 시스코 네트워킹
- 세그먼트 트리
- 알고리즘
- 백준
- 구현
- 에라토스테네스의 체
- Network
- 위상정렬
- JUnit 5
- 완전탐색
- swea
- 프로그래머스
- mst
- 그리디
- BFS
- 문자열
Archives
반갑습니다!
[프로그래머스] 방금그곡 본문
풀이
문자열 처리 문제이다. 알고리즘이 어렵다기보다는 구현할 것이 많아 까다로운 문제이다. 특히 C++의 경우 문자열 처리가 다른 언어에 비해서 약해 구현해야할 것이 많다. 우선 C, D, E, F, ... ,A, B 멜로디는 모두 1글자이지만 C#, D#, F#, G#, A# 은 2글자이므로 C#은 c로 D#은 d로 ... A#은 a로 변환해 멜로디를 찾기 쉽도록했다. 그리고 입력받은 노래 정보에서 재생 길이를 계산해 멜로디를 재생 되는 만큼 재구성했다. 이게 무슨 말이냐면 예를 들어 재생 길이가 5분인데 노래의 멜로디는 "ABCDEF"라면 노래의 멜로디를 "ABCDE"로 재구성한다. 다른 예시로 재생 길이가 13분인데 노래의 멜로디가 "ABC"라면 노래의 멜로디를 "ABCABCABCABCA"로 재구성한다. 그리고 재구성한 멜로디에서 사용자가 들은 멜로디를 찾아서 문제를 해결했다.
코드
##include <string>
#include <vector>
using namespace std;
string replace_all(string& str, const string& from, const string& to) {
int pos = 0;
while ((pos = str.find(from, pos)) != string::npos) {
str.replace(pos, from.length(), to);
pos += to.length();
}
return str;
}
void translate_sharp(string& melody) {
replace_all(melody, "C#", "c");
replace_all(melody, "D#", "d");
replace_all(melody, "F#", "f");
replace_all(melody, "G#", "g");
replace_all(melody, "A#", "a");
}
pair<string, string> parse_music_info(string info) {
// 음악 재생 시, 음악 끝 시
int h1 = stoi(info.substr(0, 2));
int h2 = stoi(info.substr(6, 2));
// 음악 재생 분, 음악 끝 분
int m1 = stoi(info.substr(3, 2));
int m2 = stoi(info.substr(9, 2));
info = info.substr(12);
int idx = info.find(',');
// 음악 제목
string name = info.substr(0, idx);
// 노래 멜로디
string melody = info.substr(idx + 1);
// #을 다른 문자로 처리
translate_sharp(melody);
// 재생 시간 분으로 계산
int time = m2 - m1 + 60 * (h2 - h1);
string s = melody;
while(s.size() < time) {
s += melody;
}
s = s.substr(0, time);
return { name, s };
}
string solution(string m, vector<string> musicinfos) {
// 사용자가 들은 멜로디에 있는 #을 다른 문자로 변환
translate_sharp(m);
int len = 0;
// 못찾은 경우를 위해 (None)으로 초기화
string answer = "(None)";
for (string s : musicinfos) {
pair<string, string> t = parse_music_info(s);
// 멜로디를 찾은 경우
if (t.second.find(m) != string::npos) {
// 가장 긴 길이의 멜로디가 정답
if (len < t.second.length()) {
len = t.second.length();
answer = t.first;
}
}
} return answer;
}
Java
class Solution {
public int getMinutes(String time) {
int h = Integer.parseInt(time.substring(0, 2));
int m = Integer.parseInt(time.substring(3, 5));
return h * 60 + m;
}
public String replaceAll(String str) {
str = str.replaceAll("C#", "c");
str = str.replaceAll("D#", "d");
str = str.replaceAll("F#", "f");
str = str.replaceAll("G#", "g");
str = str.replaceAll("A#", "a");
return str;
}
public String solution(String m, String[] musicinfos) {
String answer = "(None)";
m = replaceAll(m);
int length = 0;
for (String info : musicinfos) {
int t1 = getMinutes(info.substring(0, 5));
int t2 = getMinutes(info.substring(6, 11));
int time = t2 - t1;
info = info.substring(12);
String music = info.substring(0, info.indexOf(","));
String melody = info.substring(music.length() + 1);
melody = replaceAll(melody);
String s = melody;
while (s.length() < time) {
s += melody;
}
s = s.substring(0, time);
System.out.println(s);
if (s.contains(m) && length < time) {
length = time;
answer = music;
}
}
return answer;
}
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 14889 스타트와 링크 (0) | 2020.05.06 |
---|---|
[백준] 14888 연산자 끼워넣기 (0) | 2020.05.06 |
[백준] 2665 미로만들기 (0) | 2020.05.05 |
[프로그래머스] 파일명 정렬 (0) | 2020.05.04 |
[프로그래머스] 압축 (0) | 2020.05.04 |