[54] 코딩테스트: 쿼드압축 후 카드 세기, 두 큐 합 같게 만들기(long type) 자바

코딩테스트 준비 54일차

 

오늘 풀 문제는 쿼드압축 후 카드 세기, 두 큐 합 같게 만들기이다.

 

저번주에 풀었던 문제인데,

그때 올리지 않아서 뒤늦게 업로드한다.

 

아래 자세히 작성해두었다.

long type 사용 이유도!

 

쿼드압축 후 카드 세기

• 부터~ N/2만큼 돌면서 숫자가 같은지 확인해줄 boolean 함수
• 끝까지 확인하기 위한 is 함수

출처: 프로그래머스 쿼드압축 후 카드 세기 자바

 

프로그래머스

 

최종 코드

import java.util.*;

class Solution {
    int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        int N = arr.length;
        dfs(N, arr, 0, 0);
        return answer;
    }
    
    private void dfs(int N, int[][] arr, int a, int b){

        if(is(N, arr, a, b)){
            answer[arr[a][b]]++;
            return;
        }
        
        dfs(N/2, arr, a, b);
        dfs(N/2, arr, a+N/2, b);
        dfs(N/2, arr, a, b+N/2);
        dfs(N/2, arr, a+N/2, b+N/2);
    }

    private static boolean is(int N, int[][] arr, int a, int b){
        for(int i=a; i<a+N; i++){
            for(int j=b; j<b+N; j++){
                if(arr[i][j] != arr[a][b]){
                    return false;
                }
            }
        }
        return true;
    }
}

 

---

▼ 아래 쿼터트리 위키백과 내용도 참고해보긔 ▼

 

https://en.wikipedia.org/wiki/Quadtree

Quadtree - Wikipedia

 

두 큐 합 같게 만들기

• ArrayDeque 생성 후 queue.poll()
• while조건
  • count <= max && !q1.isEmpty() && !q2.isEmpty()

출처: 프로그래머스 두 큐 합 같게 만들기 자바

 

프로그래머스

 

최종 코드

import java.util.*;

class Solution {
    int count;
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        //long 왜?
        long sum1 = 0;
        long sum2 = 0;
        for(int i : queue1){
            q1.add(i);
            sum1 += i;
        }
        for(int i : queue2){
            q2.add(i);
            sum2 += i;
        }
        //이것의 중간값을 찾아라
        long t = sum1+sum2;
        long t1 = t/2;
        
        while(count <= max && !q1.isEmpty() && !q2.isEmpty()){
            if(sum1 == sum2){
                break;
            }else if(sum1 < t1){
                int cur = q2.poll();
                sum1 += cur;
                sum2 -= cur;
                q1.add(cur);
            }else{
                int cur = q1.poll();
                sum1 -= cur;
                sum2 += cur;
                q2.add(cur);
            }
            count++;
        }
        if(sum1 != sum2){
            return -1;
        }else{
            return count;
        }
    }
}

 

 

---

언제 long type을 고려해야할까?

현재 원소는 1~10의 9승이다.

그래서 더해서 값을 비교하기 때문에 int의 값을 넘어설 수 있다.

 

int는 20억(10의 9승까지?)

그래서 sum(s1, s2)만 long으로 선언해주면 오류 해결!

 

 

그리고 q.poll()하면 가장 먼저 들어간 값이 나온다!