[Algorithms] 이진 문자열 처리

문제 설명

이진수로 이루어진 문자열 S가 주어집니다. 이 문자열을 0으로 만들기 위한 최소한의 연산 횟수를 구하는 문제입니다.

연산 규칙:

• 이진 문자열을 10진수로 변환했을 때 짝수면, 이진수에서 2로 나누는 연산을 수행할 수 있습니다.
• 이진 문자열을 10진수로 변환했을 때 홀수면, 이진수에서 1을 빼는 연산을 수행해야 합니다. 

입력

• 이진 문자열 S가 주어집니다. (1 ≤ S의 길이 ≤ 1000)
• S는 '1'로 시작하며, '0' 또는 '1'로만 구성됩니다.

출력

• 이진 문자열을 0으로 만들기 위한 최소한의 연산 횟수를 출력합니다.

---

 

나는 처음에 이렇게 풀었었다.

func solution(_ S: inout String) -> Int {
    var count: Int = 0
    var num = Int(S, radix: 2)!
    
    while num != 0 {
        if num % 2 == 0 {
            num /= 2
        } else {
            num -= 1
        }
        count += 1
    }
    
    return count
}

 

너무 쉬운데?라고 생각한 나는 너무 쉬운 사람이다.

 

잘 생각해 보자.

만약 S의 값이 엄청 길다면 어떨까?

예를 들어 "111111111111111111111111111111111111111111111111111111111111111111111111111111..." 같은 값이라면 어떻게 될까?

 

var num = Int(S, radix: 2)!

 

이 부분에서 문제가 발생한다. 너무 긴 문자열을 정수로 변환하려고 하면 Int의 범위를 초과하게 되어 nil을 반환하게 된다. 이건 의도치 않은 오류로, 우리가 해결하고자 하는 문제와는 다른 차원의 이슈가 되는 거지.

 

내가 코테를 풀며 가장 크게 느낀 점이 있다면! 출제된 문제는 반. 드. 시 어떠한 규칙이 있다는 것이다.

그래서 나는 뭘 어떻게 했냐? 우선 그 규칙을 찾기 위해 콘솔에 2진 문자열을 다 변환해 봄

Int("0", radix: 2)!
Int("1", radix: 2)!
Int("01", radix: 2)!
Int("10", radix: 2)!
...
Int("11111111", radix: 2)!

 

이러니까 내가 찾은 규칙은 무엇이냐?

• 끝자리가 0이면 짝수고, 끝자리가 1이면 홀수

아주 좋은 소득이다.

그럼 이제 어떻게 빼고 어떻게 나누지?를 고민했다.

제가 어떻게 했을 거 같음?

 

차이가 1인 수가 나오면서, 차이가 2배인 수가 나올 때까지 콘솔에 찍어봄.ㅎ

Int("111100", radix: 2)! // 60
Int("111101", radix: 2)! // 61
Int("1111000", radix: 2)! // 120

 

뇌피셜을 돌려봤음...

무슨 규칙이 있나...

• 2로 나누려면 문자열의 끝에 있는 0을 제거하면 됨
• 1을 빼려면 끝에 있는 1을 0으로 바꿔야 함

이 경우에만 그런 게 아닌가? 하는 마음에 몇 번 테스트해 보니까 저게 맞더라.

그럼, 이제 굳이 10진수로 변환하지 않더라도 홀짝을 구분하면서, 2로 나눌 수 있고 1을 뺄 수도 있음.

이걸 알아내는데 약 40분 걸렸던 것 같다.

 

func solution2(_ S: inout String) -> Int {
    var count:Int = 0
    
    while Int(S) != 0  {
        if S.last! == "0" {
            S.removeLast()
        } else {
            S = String(S.dropLast()) + "0"
        }
        count += 1
    }
    return count
}

좋아. 그럼 이제 문제없겠지?

굳.

한 가지 마음에 걸리는 게 있었다.

그것은 뭐냐? while Int(S)!= 0 이 부분임.

S를 Int형으로 바꾸는데, 만약 S가 저따위 라면...? "11111111......."

첫 번째 문제와 다를 게 없는 거 아닌가.

 

이때 어떻게든 두뇌 오버 클럭 돌렸어야 했다.

조건을 S.contains("1")로 바꾸면 된다.

그치... 저러면 변환할 필요가 없으니까.... 왜 저 간단한 게 생각이 안 났을까.... 개탄스럽다...

 

func solution2(_ S: inout String) -> Int {
    var count:Int = 0
    
    while S.contains("1") {
        if S.last! == "0" {
            S.removeLast()
        } else {
            S = String(S.dropLast()) + "0"
        }
        count += 1
    }
    return count
}