[level 3] 110 옮기기 - 77886
성능 요약
메모리: 134 MB, 시간: 116.33 ms
구분
코딩테스트 연습 > 월간 코드 챌린지 시즌2
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2024년 10월 22일 22:48:21
문제 설명
0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.
- x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.
변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
s의 길이 ≤ 1,000,000 - 1 ≤
s의 각 원소 길이 ≤ 1,000,000 - 1 ≤
s의 모든 원소의 길이의 합 ≤ 1,000,000
입출력 예
| s | result |
|---|---|
["1110","100111100","0111111010"] |
["1101","100110110","0110110111"] |
입출력 예 설명
입출력 예 #1
- 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.
"1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.
- "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.
- "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
- 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
풀이
-
스트레스트레스트레스...받는 문제였다...(자바라 그런가?)
-
처음에 String으로 접근(String에서 제공하는 replaceFirst() 사용)했으나 일부 문제는 맞고 일부 문제는 시간 초과...
-> StringBuilder 사용으로 문자열 처리 속도를 높여서 몇 케이스는 추가로 통과됐으나 맨 뒤에 몇몇 케이스는 여전히 시간 초과
-> replaceFirst()를 호출할 때마다 문자열 처음부터 탐색을 해서 시간초과가 난다고 추론됨.
-> 사실 이미 탐색한 부분은 탐색하지 않아도 된다. 대신 110을 찾은 곳에서 2칸 전부터는 다시 탐색해야 함.(110을 뽑아내면서 뒤에랑 합쳐지기 때문에)
-> 그래서 char[]에 String의 문자를 하나씩 다 담아서 index를 가지고 문자열을 처리했다.
=> 성공... -
풀이 방법은 문자열에서 110이 형성되면 전부 빼버린 후 뺀 개수를 카운트한다.
-
110이 다 빠진 문자열은 ~11..1 혹은 ~0 으로 끝나게 된다. 따라서 110은 111보다 앞서므로 ~011..1 중 0 뒤에 1 앞에 110을 개수만큼 집어 넣으면 된다.
~0 으로 끝나면 0 뒤에 집어 넣으면 된다.
코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public String[] solution(String[] s) {
List<String> movedList = new ArrayList<>();
for (String x : s) {
char[] charStack = new char[x.length()];
int cnt = 0; // 110의 개수
int idx = 0; // 문자열의 인덱스
int size = 0; // stack의 크기
while (true) {
// 110인지 확인하기 위해 스택 크기가 2개 이하면 추가하고 스킵
if (size < 3) {
// 더 이상 넣을 수 있는 문자가 없을 때 break
if (idx >= x.length())
break;
charStack[size++] = x.charAt(idx++);
continue;
}
// 110이면
if (charStack[size - 3] == '1' && charStack[size - 2] == '1' && charStack[size - 1] == '0') {
size -= 3; // 110 스택에서 빼기
cnt++;
}
// 더 이상 넣을 수 있는 문자가 없을 때 break
if (idx >= x.length())
break;
charStack[size++] = x.charAt(idx++);
}
String tmp = new String(Arrays.copyOf(charStack, size));
idx = tmp.lastIndexOf("0"); // x에서 가장 뒤에 있는 0의 인덱스
StringBuilder left = new StringBuilder();
StringBuilder right = new StringBuilder();
if (idx == -1) { // 0이 없는 경우
right.append(tmp);
} else if (idx == tmp.length() - 1) { // 0이 맨 끝에 있는 경우
left.append(tmp);
} else { // 0이 중간에 있는 경우
left.append(tmp.substring(0, idx + 1));
right.append(tmp.substring(idx + 1));
}
for (int i = 0; i < cnt; i++) {
left.append("110"); // left와 right 사이에 끼워 넣기
}
movedList.add(left.toString() + right.toString());
}
return movedList.toArray(new String[] {});
}
}