40일차)알고리즘 문제(2개 이하로 다른 비트), 팀 프로젝트

>알고리즘 문제

1. 문제

문제 설명

양의 정수 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

2. 솔루션

class Solution {
    fun solution(numbers: LongArray): LongArray {
        var answer: LongArray = LongArray(numbers.size)
        
        for((i,v) in numbers.withIndex()){
            answer[i]=Find(v)
        }  
        return answer
    }
    //2진수로 변환. 큐에 넣음(현재값, 바꾼개수, 바꾼위치)
    //하나만 바꾸고 넣음-처음인덱스부터 원본수 최대위치보다 한자리큰 위치까지
    //체크-원본수보다 큰지: 큰데 min보다 크면 스킵,큰데 min보다 작거나 같을시 min갱신 후 두번째 비트 바꿔 큐에 넣기
    //체크-원본수보다 작은지: 두번째 비트 바꿔 큐에 넣음
    //체크-원본수보다 큰지:min갱신 그리고 크든 작든 continue
    fun Find(n:Long):Long{
        var max=0
        var tmp=n
        while(tmp!=0L){
            tmp/=2L
            max++
        }
        
        val nstr=n.toString(2).reversed()+"0"
        
        val q=ArrayDeque<Triple<Long,Int,Int>>()
        q.addLast(Triple(n,0,-1))
        
        var min=Long.MAX_VALUE
        while(q.isNotEmpty()){
            val (cur,num,idx)=q.removeFirst()
            if(num==1){
                if(cur>n){
                    if(cur>min) continue
                    else min=cur
                }
            }
            if(num==2){
                if(cur>n) min=minOf(cur,min)
                continue
            }
            
            if(num<2){
                var pow=1L
                for(i in 0..max){
                    if(i==idx){
                        pow*=2L
                        continue
                    } 
                    if(nstr[i]=='1'){
                        q.addLast(Triple(cur-pow,num+1,i))
                    }else{
                        q.addLast(Triple(cur+pow,num+1,i))
                    }
                    pow*=2L
                    
                }
            }
        }
        return min
   
    }
}

 

 

2. 팀 프로젝트

https://appdevelopjava.tistory.com/53