문제
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”을 만들 수 있습니다.
풀이
먼저 입력받은 문자열에서 “110”을 뽑을 수 있을 때 까지 계속 뽑아내야한다.
문자열에서
indexOf('110')을 통해 해당 index를 찾고substring를 통해 해당 문자열을 바꿔주었을 때 시간초과가 발생했다.프로그래머스 월간챌린지 2 5월호 3번문제의 풀이를 보니 스택을 사용하면 O(n)시간에 변경된 문자열을 찾을 수 있다고 힌트를 보았고 이를 아래와 같이 코드를 작성해서 “110”을 모두 제거한 문자열을 얻었다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
const strArr = []; // 문자열 스택 선언 for (let i = 0; i < str.length; i++) { const c = str.charAt(i); //해당 idx의 문자를 c에 저장 if (strArr.length >= 2) { //배열의 길이가 2이상이여서 3자리 문자열을 만들 수 있을 때 const b = strArr.pop(); const a = strArr.pop(); if (a === "1" && b === "1" && c === "0") { // 3자리 문자열이 "110"일때 insertStr에 110을 추가 문자열 스택에 넣지않기위해 continue insertStr += "110"; continue; } // 110이 아닐때 순서대로 다시 배열에 추가 strArr.push(a); strArr.push(b); } strArr.push(c); }
insertStr이 빈 문자열일 때, 즉, “110”이 입력 문자열에 존재하지 않을 때 입력 문자열을 정답 배열에push해준다.
1
if (insertStr === "") ans.push(str);
insertStr이 빈 문자열이 아닐 때, 즉, “110”이 입력 문자열에 존재할 때 위치를 찾아서 넣어줘야한다. 내가 생각한 방법은 뒤에서 “0”의 위치를 찾고 해당 인덱스 이후에insertStr을 넣어주는 방법을 생각했다. “110”이 모두 제거되었기 때문에 문자 “0” 앞에는 1이 연속적으로 2개 이상이 오지 못한다. 따라서 “0”뒤에insertStr을 넣었을 때 사전순으로 가장 앞에 오는 문자열을 만들 수 있다.
1
2
3
const tempStr = strArr.join("");
const idx = tempStr.lastIndexOf("0") + 1;
ans.push(tempStr.substring(0, idx) + insertStr + tempStr.substring(idx));
전체 코드
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
const solution = (s) => {
const ans = [];
s.forEach((str) => {
let insertStr = "";
let strArr = [];
for (let i = 0; i < str.length; i++) {
const c = str.charAt(i);
if (strArr.length >= 2) {
const b = strArr.pop();
const a = strArr.pop();
if (a === "1" && b === "1" && c === "0") {
insertStr += "110";
continue;
}
strArr.push(a);
strArr.push(b);
}
strArr.push(c);
}
if (insertStr === "") ans.push(str);
else {
const tempStr = strArr.join("");
const idx = tempStr.lastIndexOf("0") + 1;
ans.push(tempStr.substring(0, idx) + insertStr + tempStr.substring(idx));
}
});
return ans;
};
월간 코드챌린지 2 5월 문제를 풀때 “110”을 찾고 문자열을 변경하는 부분에서 시간초과가 발생했다는 것은 알고 있었지만, 어떻게 해결해야 할지 잘 몰라서 해결하지 못했다. 스택을 통해 선형시간에 해당 문자열을 검사할 수 있다는 것을 배웠다.