[프로그래머스] (Swift) 이진변환 반복하기 (LV.2) (feat. radix)

🫠 TIL - init(_: radix: )

swift에서 진수변환을 하는 메서드, radix에 대해서 배웠습니다. (알고가면 코테에서 유용하게 사용할듯!🤔)

let num = 7
print(String(num, radix: 2))
// "111"

• radix 뒤에 자유롭게 10진수를 어떤 진수로 변환할지 적으면 된다.
• String형태로 출력된다.

왜 이진수 인데, Int 형태가 되지 않는가? 당연하지!! Int는 10진수 아냐?? 

var num = 7
print(Int(num, radix: 2))

// error

일단, 내가 생각했던 이유중 하나는, Int는 10진수를 가진다. 그래서 int형 "111"과 이진수 "111" 은 다르기 때문에, Int로 바로 형변환이 불가능하다. 

그리고 위 이미지 처럼, radix는 string 프로토콜을 따른다고 나와있다. 진법 전환은 string으로 출력된다는 것을 기억하자!!

 

🟠 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/70129

프로그래머스

 

🟠 나의 첫번째 풀이 - 시간초과

테케 2, 5, 6, 8 시간초과

• while문이 너무 많아서 시간초과에 걸렸나?
  • while문을 true로 두지 않고 처리하는 방식을 고민해보자.
• while문에서 탈출하지 못해서 시간초과가 났던 것
  • result 가 10 일때에 대한 조건문을 추가해주면서 break 문을 걸어줌
• 그리고 로직을 어떻게 고쳐도 2, 5, 6, 8만 에러나던데, 숫자가 아주 커지면 감당이 안되나 ?
  • 이중 while문을 사용한다기보단, filter나 radix 문법을 사용해보는게 좋을듯
  • filter - O(N) / radix - O(1)
  • radix를 구하는 부분에서 while문을 사용하지 않게 고쳐야함.
• 둘째로, 아래 코드로 작성하면 시간초과
  • filter를 사용해서 “0”을 지워주면 더 좋을 것
• var deleteZeroCount = copyS.components(separatedBy: "0").joined().count

import Foundation

let s = "110010101001" // 결과 [3, 8]

func solution(_ s: String) -> [Int] {
    var zerocount = 0
    var rotation = 0
    var copyS = s
    var deletezero = 0
    var ans = [Int]()

    while true {
        rotation += 1
        print(rotation)
        // 0제거한 길이 구하고, count에 제거된 0개수 더해주기
        deletezero = deleteZeroCount(copyS)
        zerocount += copyS.count - deletezero

        // deletezero 이진법으로 바꾸기
        let result = makeBinaryScale(deletezero)
        print(result)

        if result != "10" {
            copyS = result
        } else {
            rotation += 1
            zerocount += 1
            break
        }
    }
    ans.append(rotation)
    ans.append(zerocount)
    return ans
}

func deleteZeroCount(_ s: String) -> Int {
    var result = s.components(separatedBy: "0").joined().count
    return result
}

func makeBinaryScale(_ num: Int) -> String {
    var binaryNum = num
    var result = ""
    while true {
        let quot = binaryNum / 2
        let remainder = binaryNum % 2

        if quot != 1 {
            result += String(remainder)
            binaryNum = quot
        } else if quot == 1 {
            result += String(remainder)
            result += "1"
            break
        }
    }

    return String(result.reversed())
}

print(solution(s))
//print(makeBinaryScale(111))

 

🟠 정답코드

https://github.com/deslog/Algorithm/tree/main/Algorithm/Programmers/%EC%9D%B4%EC%A7%84%EB%B3%80%ED%99%98%EB%B0%98%EB%B3%B5%ED%95%98%EA%B8%B0(lv.2) 

GitHub - deslog/Algorithm: ✨ 백준, 프로그래머스 Swift 문제풀이 ✨

import Foundation

let s = "110010101001" // 결과 [3, 8]

func solution(_ s: String) -> [Int] {
    var zerocount = 0
    var rotation = 0
    var copyS = s

    while copyS != "1" {
        let deleteZeroNum = copyS.filter { $0 == "1" }
        zerocount += copyS.count - deleteZeroNum.count
        copyS = String(deleteZeroNum.count, radix: 2)
        rotation += 1
    }
    return [rotation, zerocount]
}

print(solution(s))

 

 

아,, 생각없이 반복문 쓰다가 시간초과 걸렸다고 생각했는데, 생각보다 while문을 줄였다고 시간초과가 바로 해결되진 않았다. 메서드 하나하나 시간복잡도를 따져보면서 코드를 작성해야함을 깨달앗다 ㅠㅠㅠ 

우선 아래 참고글을 조금 차근차근 정독해보자.

https://demian-develop.tistory.com/30

iOS) Swift의 Time complexity에 관한 고찰