Stack문제이다! 대표적인 Stack 유형 문제인 괄호 문제와 비슷하게 풀어주면 된다. 반복문을 활용해 문자열 s를 한 문자씩 char 변수로 떼어서 차례대로 검사한다. 해당 char 변수가 Stack에 들어있는 맨 위의 값과 동일하다면 stack.pop()을 하여 같은 알파벳이 2개 붙어 있는 짝을 제거하는 역할을 해주고, 그렇지 않다면 stack.push()를 한다. 만약 최종적으로 Stack이 비었다면 짝지어 제거하기를 성공적으로 수행한 것이므로 1을 리턴하고, 그렇지 않다면 0을 리턴해준다.
Key Point
🔑 Stack을 활용한다.
Java 코드
import java.util.*;
classSolution{
publicintsolution(String s){
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if(!stack.isEmpty() && stack.peek() == c) stack.pop();
else stack.push(c);
}
return stack.isEmpty() ? 1 : 0;
}
}
+
근데 이거 괄호가 왜 독특한지는 모르겠다 ,,?
뭔가 ,,, 괄호에게 한 칸 전부를 수여해주는 ,, 2017 팁스타운만의 차별화 방식인가 ,,,?
compareTo 메서드는 알고리즘을 풀면서 몇 번 사용한 적이 있지만 Comparable과 Comparator 인터페이스는 처음 접해보았다 ,, 아니면 까먹었거나 ,,^^ 인터페이스 사용법을 검색하다가 우연히 "문자열 내 마음대로 정렬하기" 문제를 만났다. 문제가 훨씬 직관적이어서 이 문제를 먼저 풀고 나니 Java에서의 객체 정렬을 이해하는데 도움이 되었다.
Java 코드
import java.util.*;
classSolution{
public String[] solution(String[] strings, int n) {
Arrays.sort(strings, new Comparator<String>() {
// 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 양수로 주면 값을 바꾼다. (오름차순)// 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 음수로 주면 값을 바꾸지 않는다. (내림차순) @Overridepublicintcompare(String o1, String o2){
if (o1.charAt(n) > o2.charAt(n)) {
return1;
}
elseif (o1.charAt(n) == o2.charAt(n)) {
// compareTo() 함수는 두 개의 값을 비교하여 int 값으로 반환해준다. return o1.compareTo(o2);
}
else {
return -1;
}
}
});
return strings;
}
}
import java.util.*;
classSolution{
public String solution(int n, int t, int m, int p){
String answer = "";
StringBuilder sb = new StringBuilder();
int num = 0;
// m명이 t번 말하는 경우를 StringBuilder로 저장한다.while(sb.length() < m*t) {
sb.append(Integer.toString(num++, n));
}
// 튜브가 말해야 하는 숫자 부분만 answer에 더해준다.for (int i=p-1; i<m*t; i+=m) {
answer += sb.charAt(i);
}
return answer.toUpperCase();
}
}
Kakao Tech 블로그에서 문제 해설을 보니 이 문제는 챔퍼나운 수라는 수학 상수를 이용한 문제라고 한다.
챔퍼나운 상수(Champernowne constant) 란 ?
초월수이자 실수인 수학 상수 중 하나로 소수점 이하 자릿수에 특이한 점이 있는 수이다.
십진법에서 챔퍼나운 수는 소수 전개가 1부터 시작하여 연속적인 정수를 쭉 이은 수열인 실수이다.
이 급수를 10과 9 대신에 b와 b-1로 각각 바꿔서 임의의 b진법으로 일반화할 수 있다고 한다.
따라서 재생 시간과 음악 길이를 구해 아래 두 가지 조건으로 나누어 실제 재생되는 악보를 만들면 된다.
1) 재생 시간 > 음악 길이
실제 재생되는 악보는 "재생 시간 / 음악 길이" 만큼 악보를 반복한 후, 나머지 "재생 시간 % 음악 길이 " 만큼 뒤에 덧붙여주면 된다.
2) 재생 시간 <= 음악 길이
실제 재생되는 악보는 재생 시간만큼만 악보를 잘라주면 된다.
여기까지 풀다가 #이 붙은 음을 어떻게 처리할지 고민하는 부분에서 막혔다.
C#은 두 글자이지만 사실 하나의 음이기 때문이다.
Kakao Tech 블로그 문제 해설에서는 문자열 비교에서 이런 문제를 처리할 때 두 가지 방법을 이용하라고 알려준다.
1) 토큰화(Tokenizing)를 통해 ["A", "B" "C#"] 식의 배열로 변환한 후 비교한다. 2) 두 글자로 된 "C#", "D#", "F#" 등을 악보에서 사용되지 않는 문자 "c", "d", "e" 등으로 치환(Substitution)한 후 문자열 비교 함수를 이용한다.
개인적으로는 치환하는 것이 더 편할 것 같아서 #이 붙은 음을 치환하는 함수를 만들었다.
그리고 마지막으로 실제 재생되는 악보 중 네오가 기억하는 멜로디인 문자열 m을 포함하는 악보의 음악 제목을 찾으면 된다.
여기서 놓치면 안되는 점이 있다. 만약 조건이 일치하는 음악이 여러 개인 경우는 제일 재생 시간이 긴 음악을 찾아야 하기 때문에 변수 maxPlayingTime을 하나 만들어서 조건이 일치하는 음악 중 제일 긴 재생 시간을 업데이트해주어야 한다.
이렇게 풀고 채점하니 테스트 케이스 몇 개가 실패라고 떠서 헤맸는데, 조건이 일치하는 음악이 없는 경우를 고려하지 못한 것이 원인이었다.
조건이 일치하는 음악이 없는 경우에는 "(None)"을 리턴한다는 점을 포함하면 테스트 케이스가 전부 통과된다.
Key Point
🔑재생 시간 > 음악 길이인 경우, 재생 시간 <= 음악 길이인 경우를 나누어 처리한다.
🔑#이 붙은 음을 치환하는 함수를 만든다.
🔑조건이 일치하는 음악이 여러 개인 경우와 없는 경우를 고려한다.
Java 코드
import java.util.*;
classSolution{
public String solution(String m, String[] musicinfos){
int maxPlayingTime = 0;
String answer = "";
// 네오가 기억한 멜로디를 치환한다.
m = changeCode(m);
for (String musicInfo : musicinfos) {
String[] info = musicInfo.split(",");
// 재생된 시간 구하기int playingTime = (Integer.parseInt(info[1].substring(0, 2))
- Integer.parseInt(info[0].substring(0, 2)))*60
+ Integer.parseInt(info[1].substring(3))
- Integer.parseInt(info[0].substring(3));
// 악보 정보(=info[3]) #이 붙은 음 치환하기
info[3] = changeCode(info[3]);
// 음악 길이 구하기int musicLength = info[3].length();
// 실제 재생된 음악 악보 구하기
String musicCode = "";
// 재생 시간 > 음악 길이 : 처음부터 음악 반복 재생if (playingTime > musicLength) {
for (int j=0; j<playingTime/musicLength; j++) {musicCode += info[3];}
musicCode += info[3].substring(0, playingTime%musicLength);
}
// 재생 시간 <= 음악 길이 : 처음부터 재생된 시간만큼 재생else {musicCode += info[3].substring(0, playingTime);}
// answer = 네오가 기억하는 멜로디를 포함하면서 // 제일 재생 시간이 긴 음악 제목(=info[2])if (musicCode.contains(m) && playingTime > maxPlayingTime) {
answer = info[2];
maxPlayingTime = playingTime;
}
}
// 조건이 일치하는 음악이 없는 경우 answer = (None)if (maxPlayingTime == 0) { answer = "(None)"; }
return answer;
}
// #이 붙은 음을 치환하는 함수publicstatic String changeCode(String code){
code = code.replaceAll("C#", "c");
code = code.replaceAll("D#", "d");
code = code.replaceAll("F#", "f");
code = code.replaceAll("G#", "g");
code = code.replaceAll("A#", "a");
return code;
}
}
