[프로그래머스] 2개 이하로 다른 비트

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

이 문제 계속 틀리고 있었는데..하나를 빠트렸던 ㅓ경ㅆ다.

문제 풀이

이 문제는 문자열로도 충분히 풀 수 있다.

1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 10^15

나는 Java 의 Long.toBinaryString() 을 사용하여, long -> Long -> String 으로 변환 할 것이다.
즉 매 번 String 이 생성된다.
numbers 의 길이가 10만이기에 10만개 정도의 문자열이 생성되었다가 참조를 잃게 될 것이다. 너무 많은 문자열을 생성하면 성능 저하로 시간초과가 일어날 것 같았는데. 여기서는 10만 x (2~3) 정도의 문자열만 생성되었다가 고아객체가 될 듯 하여 문자열로 풀이가 가능한 듯 하다.

그리고 나는 이 문제는 규칙 찾기 문제로 풀이했다.

• 먼저, toBinaryString() 결과는 0 이 아닌 한 항상 "1xxx" 의 문자열을 리턴한다

따라서

1xxx에서

• xxx 가 모두 1인 경우
  • 가장 왼쪽에 1을 추가하고 , 가장 크던 1은 0으로 만든다.
  • 즉, 11111 -> 101111
• xxx 에 1개 이상의 0이 있는 경우
  • 가장 우측의 0 을 1로 변경
  • 그 값이 가장 낮은 자리가 아닌 경우, 바로 우측의 값은 0 으로 변경 ( 이거를 빼먹었었다 ㅠ-ㅠ)
  • 즉, 11010 -> 11100

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = {};
        
        answer = solve(numbers);

        return answer;
    }

    private long[] solve(long[] numbers) {
        long[] ans = new long[numbers.length];
        int idx = 0;

        for(long numb : numbers) {
            if(numb == 0) {
                ans[idx++] = 1;
                continue;
            }
            String str = convertToBin(numb); // 10 만개의 문자열이 생성되겠다 x 2~3

            // 0 이 우측에 하나라도 존재 할 경우, 가장 우측의 0 을 1로 변경한다 
            if(hasRightZero(str)) {
                ans[idx++] = convertToLong(changeToOne(str));
            } else {
                ans[idx++] = convertToLong(addToRight(str));
            }
        }

        return ans;
    }

    // 문자열 형태로 반환 
    private String convertToBin(long numb) {
        return Long.toBinaryString(numb);
    }

    // 문자열을 Long 타입으로 변환
    private long convertToLong(String numb) {
        return Long.parseLong(numb, 2);
    }


    private boolean hasRightZero(String numb) {
        int len = numb.length();

        for(int idx = len - 1 ; idx > 0 ; idx--) {
            if ( numb.charAt(idx) == '0') return true;
        }

        return false;
    }
    
    // 현재 가장 왼쪽의 1을 0으로 변경하고 1을 추가한다
    private String addToRight(String number) {
        StringBuilder sb = new StringBuilder(number);
        sb.reverse();

        sb.setCharAt(sb.length()-1,'0');
        sb.append('1');

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

    // 가장 우측의 0 을 1로 변경한다
    private String changeToOne(String number) {
        StringBuilder sb = new StringBuilder(number);
        int idx = number.length() - 1;

        for(; idx > 0 ; idx--) {
            if(number.charAt(idx) == '0') {
                sb.setCharAt(idx, '1');
                sb = setAsZero(idx, number.length() - 1, sb);
                break;
            }
        }

        return sb.toString();
    }
    
    // 0 -> 1 로 변경한 위치가 가장 우측의 수가 아닌 경우, 바로 우측의 수를 0 으로 변경
    private StringBuilder setAsZero(int idx, int len, StringBuilder sb) {
        if(idx < len) {
            sb.setCharAt(idx+1,'0');
        }
        
        return sb;
    }
    

}