해당 게시물은 longroadhome님의 게시물을 참고하여 풀이를 진행하였음을 미리 밝힙니다.
🧡문제 설명
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을 모두 추출하되,110이 추출되며 잔존하는 문자열의110또한 탐색해야한다.
하지만, 반복하여 탐색할 경우 시간이 초과되므로, 선형 탐색을 진행해야한다. -
110이 존재하지 않는 경우 현재의 문자열이 사전순으로 가장 빠른 경우이다. -
0이1보다 사전순으로 빠르기 때문에,0은 최대한 앞에 있어야하며,101은111...과 같은 문자 앞에 위치해야한다.
function solution(s) {
const result = []
// ["첫 문자열", "두번째 문자열", ...]
for(const s_el of s) {
// 110 이 나온 횟수
let count = 0
const cur = s_el.split("")
const stack = []
for(let i = 0 ; i < cur.length ; i ++) {
const third = cur[i]
// 110을 갖추기 위한 최소 두 개 이상의 요소가 있음
if(stack.length > 1) {
const second = stack.pop()
const first = stack.pop()
// first+second+third = "110" 인 경우
if(first+second+third === "110") {
count++
continue
} else {
// 아닌 경우 비교를 위해 재입력
stack.push(first, second, third)
}
} else {
// 요소가 없다면 push
stack.push(third)
}
}
// 110이 없다면 지금이 사전순으로 가장 빠름
if(!count) {
result.push(s_el)
} else {
// 거꾸로 뒤집힌 배열이 저장될 공간
const list = []
const reverse110 = "011"
// 110이 들어갈 위치 정하기
while(stack.length) {
const curElement = stack.pop()
// 0은 사전순으로 빠르기 때문에 즉시 종료
if(curElement === '0') {
stack.push("0")
break
}
list.push("1")
}
// 110을 "1"만 거른 배열에 입력한다.
while(count) {
list.push(...[...reverse110])
count--
}
// list 요소에 stack 요소(0으로 차있음)를 더해준다.
while(stack.length) {
list.push(stack.pop())
}
result.push(list.reverse().join(""))
}
}
return result
}