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
- java
- BFS
- JUnit 5
- 알고리즘
- 구현
- swea
- 세그먼트 트리
- 완전탐색
- 동적계획법
- 백준
- 수학
- 그리디
- 에라토스테네스의 체
- CS
- mst
- 플로이드-와샬
- 위상정렬
- 프로그래머스
- Network
- 백트래킹
- Effective Java
- 스택
- 투 포인터
- 후니의 쉽게 쓴 시스코 네트워킹
- dfs
- 유니온 파인드
- 문자열
- 이분탐색
- Kotlin
- 시뮬레이션
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 |