99클럽 코테 스터디 8일차 TIL [Queue]

 

- 오늘의 학습 키워드 : Queue

[문제 이름 : 과제 진행하기]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/118667

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        long totalSum = 0;
        long q1Sum = 0;
        
        for(int i=0; i<queue1.length; i++) {
            totalSum += queue1[i] + queue2[i];
            q1Sum += queue1[i];
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }
        
        // 두 배열의 합이 홀수라면, 각 배열의 합이 같아질 수 없으므로 -1 리턴
        if (totalSum % 2 != 0) return -1;
        
        while(true) {
            // int num;
            // queue1, queue2 비교 이후에도 변경될 여지가 있음.
            // 따라서 길이를 queue1.length * 2로 선언하면 안됨.
            // 반례 : [1,1,1,1], [1,1,7,1] 또는 [1,1,1,8,10,9], [1,1,1,1,1,1,1]
            if (answer > 3 * queue1.length) return -1;
            
            // 결과값 리턴
            if (q1Sum == totalSum / 2) break;
            
            // queue1의 합이 더 큰 경우
            else if (q1Sum > (totalSum / 2)) {
                int num = q1.poll();
                q1Sum -= num;
                q2.add(num);
            } else {
                int num = q2.poll();
                q1Sum += num;
                q1.add(num);
            }
            answer++;
        }
        return answer;
    }
}

 

queue1 배열의 합, queue2 배열의 합에 따라 조건을 나눠줘야 하는 문제였다.

처음 풀이했을 때, 반례를 생각하지 못하고 단순히 queue1 배열과 queue2의 배열의 길이만큼만 비교를 해주면 될 거라고 생각했다.

그런데 테스트 과정에서 몇 개가 통과하지 못했고, 이에 로직은 올바르지만 특정 분기문에 문제가 있다고 생각하게 되었다.

고심 끝에 반례를 찾아보니, 2개의 길이보다 더욱 긴 과정에서 답을 도출하는 경우가 있었다. 이에 따라 아래와 같이 코드를 작성해주었다.

if (answer > 3 * queue1.length) return -1;

 

항상 여러 예시를 생각해보고 정확한 풀이를 생각해내야 함에 중요성을 느꼈다. 

풀이 시간 : 40분

 

내일은 Deque에 대한 개념을 복습하고, 이에 대한 실습을 해보며 실전에서 적용할 수 있도록 연습해보려 한다.