Programmers 2개 이하로 다른 비트 Level 2

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/77885?language=java 

• 양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
  • x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
  예를 들어,
  • f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
  수비트다른 비트의 개수

  2	000...0010
  3	000...0011	1

  • f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
  수비트다른 비트의 개수

  7	000...0111
  8	000...1000	4
  9	000...1001	3
  10	000...1010	3
  11	000...1011	2

  정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

  ---

  제한사항
  • 1 ≤ numbers의 길이 ≤ 100,000
  • 0 ≤ numbers의 모든 수 ≤ 1015

---

문제 해석 및 풀이 방법

1. 비트로 변경한다.

2. 그리고 최하위비트부터 0인 값을 1로 변경한다. 

3. 만약 111이런 것이면 1001등의 방법으로 변경한다. (홀수인 경우)

 

내가 작성한 소스코드(Java)

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        int index = 0;
        
        for(int i=0;i<numbers.length;i++){
            StringBuilder binaryValue = new StringBuilder(); // 수정을 편하게 하려고 스트링빌더 선언
            binaryValue.append("0"+Long.toBinaryString(numbers[i])); // 앞에 0을 추가 해서 수정편하게함 
            
            int leastValueIndex = binaryValue.lastIndexOf("0"); // 최하위비트부터 해서 0을 검색
            binaryValue.setCharAt(leastValueIndex,'1'); // 그리고 그걸 1로 변경함 
            
            if(numbers[i] % 2 == 1) 
                binaryValue.setCharAt(binaryValue.indexOf("1",leastValueIndex +1),'0');
            //홀수면 다음 1을 0으로 변경
            answer[index++] = Long.parseLong(binaryValue.toString(),2);
            
        }
        return answer;
    }
}

먼저 answer의 크기를 numbers의 크기만큼 지정해 준다.

for문을 그 크기만큼 반복한다. 그리고 스트링빌더로 선언 후 그 numbers[i]값을 binaryValue에 넣어준다. 이때 앞에 0을 추가해준다 그 이유는 1111일때 10000으로 변경해야해서 그 것을 수월하게 하기 위함이다.

 

그리고 최하위비트 lastIndexOf(우->좌) 부터 0을 찾는다(설명에 조건에 맞기 위해서는 가장 작은 값순서로 증가해야함)

그리고 1로 변경해준다. 

 

만약 값이 홀수면 그 비트의 이전 비트를 0으로 변경한다. ( 11일때 100으로  바꾸기 위함)

 

위 과정을 반복 하며 answer에 값을 추가한 후 반환한다. 

 

결론 및 고찰

이 문제는 처음에 다른 방법으로 성공을 했었다. 하지만 효율성 문제(시간초과)가 떳었고 이것을 바꾸는데 고민을 했었다. 처음에 3중 for문을 사용해서 양심없게 풀긴 했지만. 다시 생각해보았고 그래서 생각한게 최하위비트부터 바꾸는 것을 고민했다. 솔직히 명령어를 몰라서 우측부터 인덱스를 찾는 lastIndexOf명령어를 찾아서 사용했고 성공적으로 풀 수 있었다. 

 

소요 시간 60분