[Swift] 백준 10829 이진수 변환 / 재귀 /recursion

 

10829번: 이진수 변환

GitHub - dbguswls030/Argorithm

 

GitHub - dbguswls030/Argorithm

 

 

 

 

 

10829번 - 이진수 변환 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	3636	1899	1648	55.544%

문제

자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000)

출력

N을 이진수로 바꿔서 출력한다. 이진수는 0으로 시작하면 안 된다.

제한

 

예제 입력 1

53

예제 출력 1

110101

힌트

 

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 구현
• 재귀

 

---

해결 방안_1

일반적으로 이진수 변환을 암산으로 하였을 때를 생각하면서 구현해보았다.

 

1. 입력 값 N보다 작은 2의 거듭제곱 중 가장 큰 값의 지수 i를 구한다. ex) N = 53일 때 36(2^5)의 i는 5이다.

2. N(53)에서 2의 거듭제곱 중 i 지수를 가지는 수를 뺀다. ex) 53 - 36 =17

3. 1,2번 과정이 가능하다면 문자열 변수 s에 "1"을 추가하고 아니면 "0"을 추가한다.

4. 1~3번 과정을 지수 i 값이 0일 때까지 실행하고 문자열 s를 출력한다.

 

import Foundation
func binary(_ n : Int, _ i : Int){
    if i < 0{
        return
    }
    var n = n
    let pow = Int(pow(2.0, Double(i)))

    if n >= pow{
        n -= pow
        s+="1"
    }else{
        s+="0"
    }
    binary(n, i-1)
}

var N = Int(readLine()!)!
var s : String = ""
var i = 0

while true{
    let pow = Int(pow(2.0,Double(i)))

    if pow>N{
        i -= 1
        break
    }

    i+=1
}


binary(N, i)

print(s)

 

---

해결방안_2

1번 방법은 코드도 지저분해지고 비효율적인 것 같다고 느끼는데 효율적인 코드가 분명 있을 것 같아서 구글링하여 다시 구현해보았다.

 

1. N을 입력 받고 nn이라는 변수에 N%2 값을 저장한다. ex) N = 53 , nn = 53%2 = 1

2. nn 값이 1이면 s에 "1"을 추가, 0이면 "0"을 추가한다.

3. 1, 2 과정을 수행하는 함수에 N/2를 매개변수로 하여 재귀호출을 한다.

4. 1~3 과정을 n이 0이 되면 종료하고 s를 거꾸로 출력한다.

 

 

func binary(_ n : Int){
    let nn = n % 2
    if(n == 0){
        return
    }
    if nn == 1{
        s+="1"
        
    }
    if nn == 0{
        s+="0"
    }
    
    binary(n/2)
}

var N = Int(readLine()!)!
var s : String = ""


binary(N)
print(String(s.reversed()))