[Programmers] 2개 이하로 다른 비트 (Java, Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

문제

x에 대한 함수 f(x)를 x보다 크고 x와의 비트가 1, 2개 다른 수들 중에서 가장 작은수를 찾는 문제입니다. 해당 문제의 예시는 위의 사이트에서 확인 가능합니다.

 

접근 아이디어

1. x를 기준으로 오른쪽부터 0이 있는지를 먼저 판별한다. (x보다 큰 수들 모두 비트로 바꾸어 비교하면 효율성에서 통과하지 못한다)

2. 0이 있다면 그 자리가 마지막 인덱스인지 아닌지에 따라 분기처리한다.

3. 0이 없다면 모든 자리의 비트가 1인상태기 때문에 1을 더해준다.

4. 위의 아이디어는 코드에 주석처리 하여 확인 가능합니다.

 

조심해야할 점

1. x보다 큰 수들을 모두 찾으려고 하면 효율성에서 문제가 있을 수 있다. (numbers는 최대 10만이고 비트로 바꾸면 자리수가 상당히 크다)

2. 분기처리 할 때 기준을 명확히 나누고 인덱스의 위치를 잘 파악하여 런타임 에러를 조심하도록 해야한다.

 

- Java

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            String binary = getNumToBinary(numbers[i]);
            StringBuilder sb = new StringBuilder();

            if (binary.contains("0")) {
                /*
                오른쪽부터 '0' 찾기
                110110111 -> 110111110 오른쪽기준 제일 오른쪽 0 찾고 0보다 오른쪽 의 마지막 1과 맞바꿈
                10111111 -> 11111110
                111100011 -> 111100110
                */
                int zeroIndex = getLastZeroIndex(binary);
                if (zeroIndex == binary.length() - 1) {
                    //111110 -> 111111
                    for (int index = 0; index < binary.length() - 1; index++) sb.append(binary.charAt(index));
                    sb.append(1);
                } else {
                    //1111 -> 10111
                    int oneIndex = getLastOneIndex(binary);
                    for (int index = 0; index < zeroIndex; index++) sb.append(binary.charAt(index));
                    sb.append(10);
                    for (int index = zeroIndex + 1; index < oneIndex; index++) sb.append(1);
                }
            } else {
                //1111 -> 10111
                sb.append(1);
                if (!binary.isEmpty()) sb.append(0);
                for (int index = 1; index < binary.length(); index++) sb.append(1);
            }

            answer[i] = getBinaryToNum(sb.toString());
        }

        return answer;
    }

    private static String getNumToBinary(long num) {
        StringBuilder result = new StringBuilder();
        long temp = num;
        while (temp > 0L) {
            result.append(temp % 2);
            temp /= 2;
        }

        return result.reverse().toString();
    }

    private static long getBinaryToNum(String binary) {
        long result = 0L;
        long mul = 0L;
        for (int i = binary.length() - 1; i >= 0; i--) {
            result += (binary.charAt(i) - 48) * Math.pow(2.0, mul) * 1L;
            mul++;
        }

        return result;
    }

    private static int getLastOneIndex(String binary) {
        int index = 0;
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '1') {
                index = i;
            }
        }

        return index;
    }

    private static int getLastZeroIndex(String binary) {
        int index = 0;
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '0') {
                index = i;
            }
        }

        return index;
    }
}

 

 

- Kotlin

class Solution {
    
    fun solution(numbers: LongArray): LongArray {
        val answer = LongArray(numbers.size)
        for (i in numbers.indices) {
            val binary = getNumToBinary(numbers[i])
            val sb = StringBuilder()

            if (binary.contains('0')) {
               /*
               오른쪽부터 '0' 찾기
               110110111 -> 110111110 오른쪽기준 제일 오른쪽 0 찾고 0보다 오른쪽 의 마지막 1과 맞바꿈
               10111111 -> 11111110
               111100011 -> 111100110
               */
                val zeroIndex = getLastZeroIndex(binary)
                if (zeroIndex == binary.length - 1) {
                //111110 -> 111111
                for (index in 0 until binary.length - 1) sb.append(binary[index])
                    sb.append(1)
                } else {
                    //1011 -> 1110
                    val oneIndex = getLastOneIndex(binary)
                    for (index in 0 until zeroIndex) sb.append(binary[index])
                    sb.append(10)
                    for (index in zeroIndex + 1 until oneIndex) sb.append(1)
                }
            } else {
                //1111 -> 10111
                sb.append(1)
                if (binary.isNotEmpty()) sb.append(0)
                for (index in 1 until binary.length) sb.append(1)
            }

            answer[i] = getBinaryToNum(sb.toString())
        }

        return answer
    }

    fun getNumToBinary(num: Long): String {
        val result = StringBuilder()
        var temp: Long = num
        while (temp > 0L) {
           result.append(temp % 2)
           temp /= 2
        }
        return result.reverse().toString()
    }   

    fun getBinaryToNum(binary: String): Long {
        var mul = 0
        var result: Long = 0
        for (num in binary.reversed()) {
            result += (num.toInt() - 48) * 2.0.pow(mul.toDouble()).toLong()
            mul++
        }
        return result
    }

    fun getLastOneIndex(binary: String): Int {
        var index = 0
        for (i in binary.indices) {
            if (binary[i] == '1') {
                   index = i
            }
        }
        return index
    }

    fun getLastZeroIndex(strNum: String): Int {
        var index = 0
        for (i in strNum.indices) {
            if (strNum[i] == '0') {
                index = i
            }
        }
        return index
    }
}

 

 

좌(Java 채점 결과), 우(Kotlin 채점 결과)