44일차)알고리즘 문제(소수 찾기, 쿼드 압축 후 개수 세기)

>알고리즘 문제

1. 소수 찾기

1)문제

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

2)솔루션

class Solution {
    fun solution(numbers: String): Int {
        var answer = 0
        
        //nums에 모든 경우의 수 저장(1운 소수, 0은 합성수)
        val q=ArrayDeque<Node>()
        val nums=HashMap<Int,Int>()
        val inits=Node()
        inits.setinit(numbers)
        q.addLast(inits)
        while(q.isNotEmpty()){
            val cur=q.removeFirst()
            
            if(cur.n>1) nums.put(cur.n,1)
            
            for(i in cur.bef){
                q.addLast(cur.choose(i))
            }
        }
        
        val max=nums.keys.maxOrNull() as Int
        
        for(i in 2..Math.sqrt(max.toDouble()).toInt()){
            for((k,v) in nums){
                if(k%i==0&&k!=i){
                    nums.put(k,0)
                }
            }
        }
        
        
        for((k,v) in nums){
            answer+=v
        }
        
        return answer
    }
}

class Node(){
    var n=0
    val bef=ArrayList<Int>()
    
    fun setinit(numbers:String){
        for(i in numbers){
            bef+=i.toString().toInt()
        }
    }
    fun choose(num:Int):Node{
        val node=Node()
        val idx=this.bef.indexOf(num)
        for((i,v) in this.bef.withIndex()){
            if(i==idx) continue
            node.bef+=v
        }
        node.n=this.n*10+num
        return node
    }
}

-BFS방식으로 모든 경우의 수를 찾음

-찾은 숫자들을 에라토스테네스의 체방식으로 한번에 소수판별

 

 

2. 쿼드 압축 후 개수 세기

 

1)문제

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예arrresult

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

2)솔루션

class Solution {
    fun solution(arr: Array<IntArray>): IntArray {
        var answer: IntArray = intArrayOf()
        val result=check(arr,0,0,arr.size)
        answer+=result.second
        answer+=result.first
        return answer
    }
    fun check(arr:Array<IntArray>,sx:Int,sy:Int,l:Int):Pair<Int,Int>{
        var zero=0
        var one=0
        var flag=true
        var check=arr[sx][sy]
        for(i in sx..sx+l-1){
            for(j in sy..sy+l-1){
                if(check!=arr[i][j]){
                    flag=false
                    break
                }
            }
        }
        if(flag){
            if(check==0) one++ else zero++
            return Pair(zero,one)
        }
        else{
            val (lu0,lu1)=check(arr,sx+l/2,sy+l/2,l/2)
            val (ru0,ru1)=check(arr,sx,sy+l/2,l/2)
            val (ld0,ld1)=check(arr,sx+l/2,sy,l/2)
            val (rd0,rd1)=check(arr,sx,sy,l/2)
            zero=lu0+ru0+ld0+rd0
            one=lu1+ru1+ld1+rd1
            return Pair(zero,one)
        }
    }
}

-체크후 압축가능하면 하고 아니면 4분할로 나눠서 반복이므로 재귀함수 이용