[Kotlin] 배준 3460 - 이진수

문제

양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10^6)

풀이

1. 2진수의 경우, 2로 나눈 나머지가 존재한다면(나머지는 1) 해당 위치 1의 값이 온다.

2. 테스트 케이스 당 n의 값을 2로 계속 나눈다면 최대 log(n)번 수행해야한다. O(TlogN)

3. T는 최대 10 n의 최댓값은 10^6으로 이므로 최대 log(10^7)의 시간복잡도를 가지므로 2로 계속 나누는 방법을 채택한다.

소스 코드

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    val T = nextInt()	// 테스트케이스 수
    
    // 반복
    for(i in 1..T){
        val N = nextInt()	// 테스트케이스
        module(N)	// 모듈 호출
    }
}

// 이진수를 계산하고 출력하는 모듈
fun module(N:Int) {
   val sb = StringBuilder()	// 출력용 StringBuilder
   var n = N	// 나눌값(몫)
   var c = 0	// 현재 자리 인덱스(1의 자리가 0)
   
   while(n > 0){
   	// 2의 나머지가 1이라면, 해당 자리를 1이 되므로 위치를 저장
	if(n % 2 == 1){
		sb.append(c)
		sb.append(" ")
	}
    
    // 다음조건 설정
	n /= 2	// 2로 나눈 몫
	c++		// 다음 자리(인덱스)증가
   }
   println(sb)
}