휴가를 다녀와서 오랜만에 풀어보는 코딩 문제들.. 그래도 푹 쉬고 와서인지 나름 수월하게 풀린 것 같다. 해쉬 맵, 스택, 큐 사이좋게 한 문제씩 풀어봤다.
1657. Determine if Two Strings Are Close
주어진 두 문자열은 다음 두 명령으로 하나에서 다른 하나를 얻을 수 있다면 '가깝다'고 할 수 있다.
명령 1: 존재하는 두 문자열을 서로 바꿔치기한다.
명령 2: 단어에 출현한 하나의 문자 모두를 다른 하나의 문자 모두로 바꾼다. 예를 들어 a 모두를 b로 바꾸고, b를 모두 a로 바꾼다.
위 두 명령을 필요한 만큼 수행할 수 있다고 할 때, word1과 word2과 '가깝다'면 true, 그렇지 않으면 false를 리턴하라.
Two strings are considered close if you can attain one from the other using the following operations:
Operation 1: Swap any two existing characters.
For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)
You can use the operations on either string as many times as necessary.
Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.
문제를 처음 읽었을 때 word1에서 word2로 바꾸는 과정을 과연 어떻게 찾아야할지 고민을 많이 했다. 그런데 곰곰이 읽어보니 word1에서 word2로 변형이 가능한지를 리턴하면 되고 과정은 필요하지 않았다. 그래서 예시를 몇 가지 두고, 어떤 경우에 두 문자열이 변경이 가능할지 생각해 봤다.
가장 분명한 조건은 두 문자열의 길이가 같아야 한다. 그렇지 않으면 아무리 바꿔도 같아질 수 없다. 그 다음은 word1, word2가 동일한 문자 set을 가지고 있는지 여부다. 명령 1, 명령 2 모두 출현한(existing) 문자들 내에서 바꿀 수 있기 때문에 두 문자열이 같은 출현 문자를 가지고 있어야 한다. 다음은 문자열의 출현 횟수를 생각해봐야 한다(명령 2). 두 문자열의 문자 set이 같고, 출현 횟수가 같다면 명령 1, 명령 2로 충분히 변경이 가능하다.
그래서 아래와 같이 코드를 짤 수 있었고, 제출했을 때 런타임 55%로 통과했다.
class Solution {
public boolean closeStrings(String word1, String word2) {
if (word1.length() != word2.length()) {
return false;
}
Map<Character, Integer> word1Map = getCharFreq(word1);
Map<Character, Integer> word2Map = getCharFreq(word2);
List<Integer> word1FreqList = new ArrayList(word1Map.values());
List<Integer> word2FreqList = new ArrayList(word2Map.values());
Collections.sort(word1FreqList);
Collections.sort(word2FreqList);
return word1Map.keySet().equals(word2Map.keySet()) && word1FreqList.equals(word2FreqList);
}
private Map<Character, Integer> getCharFreq(String word) {
Map<Character, Integer> ret = new HashMap<>();
for(char c : word.toCharArray()) {
int freq = ret.getOrDefault(c, 0);
ret.put(c, freq+1);
}
return ret;
}
}word1의 길이를 n, word2의 길이를 m이라고 했을 때, 문자-빈도 맵을 만들 때 각각 O(n), O(m)이 걸린다. 그리고 빈도 수의 리스트를 정렬한 뒤 비교하고 있는데 최악의 경우 리스트의 길이는 각각 m, n이 될 것이고, 이들을 정렬하려면 O(nlogn), O(mlogm)이 걸린다. 따라서 시간 복잡도는 O(nlogn + mlogm)이 될 것 같다. 공간 복잡도는 O(m+n)이 된다.
394. Decode String
주어진 부호화된 문자열을 복호화하여 리턴하라.
인코딩 규칙은 k[인코딩 문자열] 이고 k는 인코딩 문자열의 반복 횟수를 나타낸다. 입력 문자열은 항상 유효하다고 가정할 수 있다.
그리고 원본 데이터는 숫자를 포함하지 않고 숫자는 반복 횟수만 의미한다. 그래서 3a 또는 2[4] 같은 입력 문자열은 없다.
생성되는 테스트 케이스의 길이는 10^5을 초과하지 않는다.
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 10^5.
인코딩 문자열 안에 또 인코딩 규칙이 들어있을 수 있다. 그래서 이것을 재귀적으로 처리하거나 혹은 스택을 이용해서 반복적으로 처리해야 한다. 아무래도 반복문을 사용하는 것보다는 재귀함수로 처리하는 게 더 쉽다. 입력 문자열이 항상 유효한 문자열임을 보장하기 때문에 leftBracket의 개수와 rightBracket의 개수가 같을 때 하나의 인코딩 룰이 완성된다. 그래서 leftBracket과 rightBracket 개수가 같을 때 내부를 substring으로 만들고, 그 substring을 인자로 다시 decodeString을 호출하여 재귀적으로 처리하였다.
제출했을 때 런타임 100%로 통과했다.
class Solution {
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
int i=0;
while (i < s.length()) {
char c = s.charAt(i);
if (!Character.isDigit(c)) {
sb.append(c);
i++;
} else {
StringBuilder kBuilder = new StringBuilder();
while(s.charAt(i) != '[') {
kBuilder.append(s.charAt(i));
i++;
}
int leftBracket = 1, rightBracket = 0, j=i+1;
while(true) {
char cc = s.charAt(j);
if (cc == '[') {
leftBracket++;
} else if (cc == ']') {
rightBracket++;
}
if (leftBracket == rightBracket) {
break;
}
j++;
}
int k = Integer.parseInt(kBuilder.toString());
String decoded = decodeString(s.substring(i+1, j));
for(int cnt=0; cnt<k; cnt++) {
sb.append(decoded);
}
i = j+1;
}
}
return sb.toString();
}
}시간복잡도.. 😅
649. Dota2 Senate
문제를 읽는데 참 오랜 시간이 걸렸던... 간단히 요약하면 'R 또는 D로 이뤄진 문자열이 있을 때, 각 문자열은 서로 다른 문자열을 지울 수 있다. 이것을 반복할 때 마지막에 남은 문자를 구하라.'라고 요약할 수 있을 것 같다.
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:
- Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
- Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "Radiant" or "Dire".
내가 풀었던 솔루션은 R의 출현 횟수, D의 출현 횟수를 각각 기록하고, boolean 배열을 활용해서 ban 됐는지 체크를 하고, 마지막에 어떤 문자의 출현 횟수가 0인지 확인해서 Dire 또는 Radiant를 리턴하는 방법이었다. 그런데 이 문제의 주제가 Queue였듯이 두 개의 Queue를 사용해서 푸는 아주 좋은 방법이 있었다. 시각적 설명까지 덧붙인 설명이라서 보고 바로 이해가 돼서 그대로 구현을 했다. 그래서 런타임은 고작 61%...😂 더 나은 솔루션이 있다는 얘긴데... 다시 찾아봐야겠다.
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> rad = new LinkedList<>();
Queue<Integer> dir = new LinkedList<>();
for(int i=0; i<n; i++) {
if (senate.charAt(i) == 'R') {
rad.offer(i);
} else {
dir.offer(i);
}
}
while(!rad.isEmpty() && !dir.isEmpty()) {
if (rad.peek() < dir.peek()) { // radiant win
rad.offer(n++);
} else {
dir.offer(n++);
}
rad.poll();
dir.poll();
}
return rad.isEmpty() ? "Dire" : "Radiant";
}
}주어진 문자열의 길이를 n이라고 했을 때, 시간 복잡도는 각 문자열을 큐에 넣는 데에 O(n)이다. 그리고 둘 중 하나의 큐가 빌 때까지 반복문을 도는데, 둘 중 이기는 쪽만 큐에 다시 값을 넣기 때문에, 많아야 O(n/2) 안에 끝나게 된다. 따라서 시간 복잡도는 O(n)이 된다. 그리고 공간 복잡도 역시 O(n)이다.
