[프로그래머스/Kotlin]Level3 - 110 옮기기

프로그래머스

문제

문제 설명

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"을 만들 수 있습니다.

 

나의 최종 풀이

class Solution {
    fun solution(s: Array<String>): Array<String> {
        val answer: ArrayList<String> = arrayListOf()

        val new = StringBuilder()
        val str = StringBuilder()

        s.forEach {
            new.setLength(0)
            str.setLength(0)
            
            var zeroIdx = -1

            it.forEach { c -> 
                new.append(c)
                val index = new.lastIndex
                if (c == '0') {
                    if (index >= 2 && new[index-2] == '1' && new[index-1] == '1') {
                        new.setLength(index - 2)
                        str.append("110")
                    } else {
                        zeroIdx = index
                    }
                }
            }

            if (zeroIdx == -1) {
                answer.add(str.toString() + new.toString())
            } else {
                new.insert(zeroIdx+1, str)
                answer.add(new.toString())
            }
        }
        return answer.toTypedArray()
    }
}

string에서 "110"을 뽑고(new), str에 뽑아낸 "110"을 쭉 나열합니다.

그리고 글자(new)에서 제일 마지막 0 뒤에 str를 연결해 붙였습니다.

제일 마지막 0 뒤에 붙인 이유는 이 문제가 "110" 을 옮기는 데 있습니다.

이 문제는 "사전순으로 가장 앞"에 오는 위치에 110을 옮기고 싶어합니다.

"110" 보다 사전순으로 큰 숫자는 "111"밖에 없습니다.

따라서 0이 포함되면 "110"보다 사전순으로 같거나 작기 때문입니다.

만약 1 뒤에 110이 들어가면 "111"이 만들어지므로 이는 0 뒤에 붙을 때보다 사전순으로 뒤로 가게 됩니다.

 

그래서 "110"도 뽑아내서 쭉 나열한 것입니다.

결국 뽑아낸 "110"끼리는 어디에 배치를 하든 "110" 뒤에 붙을 수 밖에 없습니다.

1 뒤에 들어가지 못하니까요~

이 풀이의 시간복잡도

• s.forEach 루프 내에서 문자열 배열 s의 각 요소를 순회하므로 O(n) 시간이 소요됩니다.
  (여기서 n은 s 배열의 길이입니다.)
• 내부 루프 it.forEach는 각 문자열 it의 길이에 비례하므로 최악의 경우 O(m) 시간이 소요됩니다.
  (여기서 m은 문자열 it의 길이입니다.)
• 따라서, 전체 함수의 시간 복잡도는 O(n * m)입니다.

이 풀이의 공간복잡도

• answer 변수는 변환된 문자열을 저장하기 위한 ArrayList로 O(n) 공간을 사용합니다.
  (여기서 n은 s 배열의 길이입니다.)
• new와 str 변수는 StringBuilder 객체로 문자열을 임시로 저장하기 위해 사용되며, O(1) 공간을 사용합니다.
• 따라서, 전체 함수의 공간 복잡도는 O(n)입니다.

---

Comment

문제를 해결하는 데에 몇달이 걸린 문제입니다.

답은 거의 도달을 했는데 일부 테스트케이스에서 시간 초과가 났었습니다.
힌트를 봐도 모르겠고, 질문하기에 글을 올려도 답변이 달리지 않아 혼자 끙끙댔습니다.

 

결국 StringBuilder의 문제였습니다.

이 문제는 StringBuilder를 사용하지 않으면 시간초과가 나는 문제였으며, 저 역시는 StringBuilder를 통해 풀었었습니다.

그런데 가장 핵심이 되는 변수를 StringBuilder를 사용하지 않았고, 그걸 계속 발견하지 못해서 시간초과가 났었던 것입니다...

 

해결하고 나니 허무하고도 속이 시원하네용... ㅎㅎ