내일은 알고리즘

https://nodingco.tistory.com/135

Python 풀이를 Java로 옮기기만 했습니다. 문제링크와 아이디어, 구현 방법은 위 링크에 설명되어 있습니다.

import java.util.LinkedList;
import java.util.Queue;

public class q118667_Programmers_두큐합같게만들기 {
	public static void main(String[] args) {

		System.out.println(solution(new int[] { 3, 2, 7, 2 }, new int[] { 4, 6, 5, 1 }));

	}

	static int solution(int[] queue1, int[] queue2) {
		Queue<Long> leftqueue = new LinkedList<Long>();
		Queue<Long> rightqueue = new LinkedList<Long>();
		long leftsum = 0;
		long rightsum = 0;
		int count = 0;
		int limit = 2 * (queue1.length + queue2.length);

		for (int i = 0; i < queue1.length; i++) {
			leftsum += queue1[i];
			leftqueue.add((long) queue1[i]);
		}
		for (int i = 0; i < queue2.length; i++) {
			rightsum += queue2[i];
			rightqueue.add((long) queue2[i]);
		}

		if ((leftsum + rightsum) % 2 == 1) {
			return -1;
		}

		while (count < limit) {
			if (leftsum == rightsum) {
				return count;
			}

			if (leftsum < rightsum) {
				leftsum += rightqueue.peek();
				rightsum -= rightqueue.peek();
				leftqueue.add(rightqueue.poll());
			} else {
				rightsum += leftqueue.peek();
				leftsum -= leftqueue.peek();
				rightqueue.add(leftqueue.poll());
			}
			count += 1;
		}

		return -1;

	}
}

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

두 큐의 합을 같게 만드는 문제입니다.

그리디 하게 합이 더 큰 쪽의 큐에서 수를 빼서 작은 쪽으로 넣으면 되는데, 이유는 조금만 생각해봐도 떠올릴 수 있습니다.

(큐의 선입선출 구조를 생각하시면 왜 그리디하게 풀이해서 정답이 나오는지 알 수 있습니다.)

입력된 리스트를 두개의 큐에 (Python의 경우 deque) 담고 그리디 하게 값을 빼고 넣어주며 같은 값이 되게 해 주면 됩니다.

실행시간을 단축시키는 가지치기가 몇개 가능한데, 우선 두 큐의 합을 더한 값이 홀수면 어떤 방법을 써도 같게 만들 수가 없습니다. 3을 정수로 2등분 시키는 게 불가능하듯이요.

2로 나눈 나머지가 0이 아니면 -1을 리턴하시면 됩니다. 그리고 큐의 합을 매번 구하지 않도록 초기 상태에서 합을 미리 구해놓은 다음, 옮기는 수만 합에서 직접 빼고 더해주면 매번 큐의 합을 구하는 것보다 빠르게 동작할 수 있습니다.

from collections import deque


def solution(queue1, queue2):
    left = sum(queue1)
    lqueue = deque(queue1)
    right = sum(queue2)
    rqueue = deque(queue2)
    limit = 2 * (len(queue1) + len(queue2))
    count = 0

    if (left + right) % 2 == 1:
        return -1

    while count < limit:

        if left == right:
            return count

        if left < right:
            gap = rqueue.popleft()
            left += gap
            right -= gap
            lqueue.append(gap)
        else:
            gap = lqueue.popleft()
            right += gap
            left -= gap
            rqueue.append(gap)

        count += 1
    return -1


print(solution([3, 2, 7, 2], [4, 6, 5, 1]))

https://school.programmers.co.kr/learn/courses/30/lessons/42862

Greedy 유형의 연습문제입니다.

여분의 체육복을 누구에게 빌려줄지가 중요할것 같지만, 앞에서부터 가능한 경우를 채워가면 풀이가 가능합니다.

만약 뒤에서 체육복이 필요하게 되면 앞의 체육복을 빼앗아야 하는데 앞의 체육복을 뺏는 경우는 어차피 총합은 같은 제로섬 동작이고 뒤에서 빌리는게 가능하면 최대값이 바뀌므로 가능한한 앞쪽부터 채우는게 유리합니다.

주의할 점은 여분의 체육복이 있는 상태에서 체육복을 도둑맞는 경우 무조건 자신이 착용한다는 것을 구현해줘야 합니다.

이 경우는 체육복의 수가 줄어들 수 있습니다.

Ex) 3번과 4번이 여벌을 소유하고 2,3번이 체육복을 도둑맞는 경우 1번(자기것) 2번(3번의 것) 3번(4번의 것) 4, 5번으로 5명 모두 체육복을 입을 수 있지만 문제의 조건에서 3번은 자기가 우선적으로 자기것을 입습니다. 즉 2번은 3번의 여벌 체육복을 빌리지 못해 답은 4가 됩니다.

def solution(n, lost, reserve):
    answer = 0
    student = [True for i in range(n)]
    spair = [False for i in range(n)]
    
    for i in lost:
        student[i-1] = False
    
    for i in reserve:
        if student[i-1]:
            spair[i-1] = True
        else:
            student[i-1] = True
        
    
    for i in range(n):
        if student[i]:
            answer += 1
        
        else:
            for j in range(-1,2):
                if 0 <= i+j < n and spair[i+j]:
                    spair[i+j] = False
                    answer += 1
                    break
    
    return answer