Stack문제이다! 대표적인 Stack 유형 문제인 괄호 문제와 비슷하게 풀어주면 된다. 반복문을 활용해 문자열 s를 한 문자씩 char 변수로 떼어서 차례대로 검사한다. 해당 char 변수가 Stack에 들어있는 맨 위의 값과 동일하다면 stack.pop()을 하여 같은 알파벳이 2개 붙어 있는 짝을 제거하는 역할을 해주고, 그렇지 않다면 stack.push()를 한다. 만약 최종적으로 Stack이 비었다면 짝지어 제거하기를 성공적으로 수행한 것이므로 1을 리턴하고, 그렇지 않다면 0을 리턴해준다.
Key Point
🔑 Stack을 활용한다.
Java 코드
import java.util.*;
class Solution
{
public int solution(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.*;
class Solution {
public String[] solution(String[] strings, int n) {
Arrays.sort(strings, new Comparator<String>() {
// 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 양수로 주면 값을 바꾼다. (오름차순)
// 앞의 값(o1)과 뒤의 값(o2)을 비교해서 리턴값을 음수로 주면 값을 바꾸지 않는다. (내림차순)
@Override
public int compare(String o1, String o2) {
if (o1.charAt(n) > o2.charAt(n)) {
return 1;
}
else if (o1.charAt(n) == o2.charAt(n)) {
// compareTo() 함수는 두 개의 값을 비교하여 int 값으로 반환해준다.
return o1.compareTo(o2);
}
else {
return -1;
}
}
});
return strings;
}
}
import java.util.*;
class Solution {
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진법으로 일반화할 수 있다고 한다.
각 스테이지마다 실패율을 구하기 위해서 주어진 배열 stages를 참고하여 배열 두 개를 만들었다.
1) 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수를 담은 배열
2) 스테이지에 도달한 플레이어 수를 담은 배열
배열의 인덱스가 스테이지 번호라고 생각하고, 각 스테이지 번호와 일치하는 인덱스에 수를 저장한다.
두 배열의 같은 인덱스에 들어있는 원소 값을 나누어 실패율을 계산하고, HashMap에 저장하면 된다.
만약 스테이지에 도달한 유저가 없는 경우, 실패율을 0으로 정의하는 예외 처리도 해주어야 한다.
Key Point
🔑배열을 활용해 실패율을 구한다.
🔑 HashMap을 사용해 스테이지 번호(key)와 실패율(value)을 저장한다.
🔑 스테이지에 도달한 유저가 없는 경우(실패율 = 0)를 고려한다.
🔑 실패율(value)을 기준으로 내림차순으로 정렬한 후, 스테이지 번호(key)를 배열 answer에 넣어준다.
Java 코드
import java.util.*;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
// 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수 정보를 담은 배열
int[] stageCount = new int[N+2];
for (int stage : stages) {
stageCount[stage]++;
}
// 스테이지에 도달한 플레이어 수 정보를 담은 배열
int[] stagePassCount = new int[N+1];
stagePassCount[N] = stageCount[N] + stageCount[N+1];
for (int i=N-1; i>=1; i--) {
stagePassCount[i] = stageCount[i] + stagePassCount[i+1];
}
// HashMap을 사용해 실패율 저장 (Key: 스테이지 번호, value: 실패율)
HashMap<Integer,Double> map = new HashMap<>();
for (int i=1; i<=N; i++) {
if (stagePassCount[i] == 0) {
map.put(i, (double)0);
}
else {
map.put(i, (double)stageCount[i]/stagePassCount[i]);
}
}
// 각 스테이지 번호(key)를 실패율(value)의 내림차순으로 정렬
List<Integer> keySet = new ArrayList<>(map.keySet());
keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));
int idx = 0;
for (int stage : keySet) {
answer[idx++] = stage;
}
return answer;
}
}
따라서 재생 시간과 음악 길이를 구해 아래 두 가지 조건으로 나누어 실제 재생되는 악보를 만들면 된다.
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.*;
class Solution {
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;
}
// #이 붙은 음을 치환하는 함수
public static 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;
}
}
LRU (Least Recently Used)는 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.
LRU 캐시 교체 알고리즘 구현은 보통 Queue, ArrayList, LinkedList를 사용하는 것 같다.
Java에서는 LinkedList가 Queue의 구현체라고 한다.
그래서 LinkedList를 사용했다.
아래는 LinkedList 메소드이다.
add(Object object)는 LinkedList의 마지막에 데이터를 추가한다.
remove(int index)는 해당 인덱스 위치의 값이 지워지는 것이지만,
remove(Object object)는 해당 값이 없다면 false, 있다면 지우고 true를 반환한다고 한다.
이 문제는 세 가지 경우를 생각하면 된다.
1) cache size가 0인 경우
이 문제에서 중요한 포인트는cache size가 0인 경우를 잊지 말고 생각해야 한다는 점이다.
cache size가 0이면 모든 경우는 cachs miss이므로 그냥 cities의 길이에 5를 곱해주면 된다.
2) cache hit 인 경우
3) cache miss 인 경우
아래는 문제 풀이 코드이다.
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
// cache size가 0이면 모든 경우는 cache miss 이다.
if (cacheSize == 0) return cities.length*5;
int answer = 0;
LinkedList<String> cache = new LinkedList<>();
for (int i=0; i<cities.length; i++) {
// 대문자로 통일한다.
String s = cities[i].toUpperCase();
// cache hit 인 경우 실행시간은 1이다.
if (cache.remove(s)) {
answer += 1;
cache.add(s);
}
// cache miss 인 경우 실행시간은 5이다.
else {
answer += 5;
if (cache.size() >= cacheSize) {
cache.remove(0);
}
cache.add(s);
}
}
return answer;
}
}
