내일은 알고리즘

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

간단한 그리디 유형의 문제입니다. 사과를 m개씩 묶어서 팔아야 하는데 m개 중 `가장 낮은 점수 x m`의 가격을 받을 수 있습니다. 간단하게 사과를 내림차순으로 정렬하고 앞에서 부터(점수가 높은 사과부터) m 개씩 끊어가며 판매하면 됩니다. 

예시를 통해 검증을 해보겠습니다. 예시 1번에서 사과의 점수가 [1, 2, 3, 1, 2, 3]이고 4개씩 묶어 팔아야 한다고 합니다. 이를 내림차순으로 정렬하면 [3, 3, 2, 2, 1, 1]이 되고 얻는 가격은 앞에서부터 4개를 선택해 얻은 [3, 3, 2, 2]에서 가장 낮은 점수인 2 x 4 = 8입니다. 

사과 n개가 존재하고 이를 내림차순으로 정렬한 값이 [A1, A2, A3, ...Am, ... An]이라고 해 봅시다. 내림차순으로 정렬했기 때문에 각 사과들의 가격은 A1 >= A2 >= A3 ...>= Am... >= An의 대소를 가집니다. 앞에서부터 m개의 사과를 선택했을 때 얻는 금액은 `Am x m` 입니다. Am보다 가격이 작거나 같은 어떤 사과 Ax (m < x <= n)를 선택하면 얻는 금액은 `Ax x m`이 됩니다. Am >= Ax이므로 m을 곱해봐야 대소관계가 변하지 않음을 알 수 있습니다. 따라서 매 순간마다 가능한 사과들 중에 가격이 큰 m개를 순서대로 고르는것이 가격합을 가장 크게 만드는 방법입니다.

def solution(k, m, score):
    score.sort(key = lambda x : -x)
    
    answer, i = 0, m - 1
    
    while i < len(score):
        answer += score[i] * m
        i += m
    
    return answer

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

문제 밑부분에 레벨이 2에서 1로 조정되었다고 적혀있네요. 아마 그리디 문제로 올라왔다가 너무 쉬워서 레벨이 조정된 것 같습니다. 

실제로 풀이도 간단합니다. 벽을 칠해야 하는 부분을 만나면 그 부분을 왼쪽 끝으로 놓고 최대한 칠해줍니다. 이 값을 기억해 뒀다가 다음에 칠해야 하는 부분이 칠한 부분 밖이라면 칠한 횟수를 늘려주고 같은 행동을 반복합니다.

코드도 간단하네요.

def solution(n, m, section):
    answer = 0
    e = 0
    for s in section:
        if s > e:
            answer += 1
            e = s + m - 1
    
    return answer

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

기본적인 탐욕법(Greedy) 문제입니다.

그리디란 매 상황에서 최선의 선택을 하는 풀이를 말합니다. 이 문제에서 한 보트에는 최대 2명이 탈 수 있으며 2명의 무게합 제한도 있습니다.

이때 가장 적은 보트로 모든 사람을 태우는 방법은 무엇일까요?

우선 보트에 최대한 2명을 많이 태워야 한다는 아이디어는 바로 떠올릴 수 있습니다. 1명씩 태우는 것보다 2명을 태울때 마다 사용하는 보트의 수가 1씩 줄어들죠.

그럼 최대한 2명을 많이 태우려면 어떻게 해야 할까요?

정답은 짝지을 수 있는 무거운 사람을 가장 가벼운 사람과 짝짓는다 입니다. 예를 들어볼까요?

무게 제한이 10이고 4명의 무게가 [1, 2, 5, 6, 8] 이라고 해봅시다. 가장 무거운 무게가 8인 사람을 무게가 1인 사람과 짝지으면 한 보트에 태울 수 있습니다. 이 사실은 당연하지만 이때 이런 생각을 하시는 분도 있을겁니다. 무게가 8, 2인 둘을 태우면 더 가벼운 무게가 1인 사람을 남길 수 있는데 이 방법을 고려하지 않아도 될까요? 

반례를 찾아봅시다. 작은 무게가 먼저 나오게 정렬된 a, b, c, d 가 있습니다. (a <= b <= c <= d) 우리는 a + d 대신 b + d를 태워서 이득을 보는 경우를 찾으려고 합니다. 즉 a + c는 보트에 탈 수 있지만 b + c는 보트에 탈 수 없는 경우를 찾는겁니다.

그럼 우리는 제한 무게 limit가 존재할 때, a + c <= limit < b + c 가 되게 하는 값들을 찾는겁니다.

a, b, c, d의 무게 순서를 알기 때문에 c와 d의 정확한 차이는 몰라도 d보다 작거나 같은 c는 d - x (x >= 0)로 다시 쓸 수 있습니다. 위 식에 대입을 해보면 limit < b + d - x가 되어야합니다. 그런데 우리는 a + d 대신 b + d를 태우려고 하기 때문에 b + d <= limit 성립해야합니다. 즉 b + d <= limit이고 여기서 x를 뺀 b + d - x는 당연히 limit보다 작거나 같다는 사실을 알 수 있습니다.

따라서, b + d를 보트에 태울 수 있다면 b + c를 보트에 태울 수 있는것도 당연한 사실이 되고 두 조합을 모두 보트에 태울 수 있으므로 고려하지 않아도 됩니다. 주어진 무게들을 정렬 한 뒤 현재 가장 무거운 사람과 가벼운 사람을 묶어 태울 수 있다면 태우고, 불가능하다면 무거운 사람을 혼자 보트에 태우며 필요한 보트의 수를 카운팅하면 됩니다.

def solution(people, limit):
    answer, left, right = 0, 0, len(people) - 1
    people.sort()
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        answer += 1
    
    return answer

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

https://www.acmicpc.net/problem/23559

정렬이 곁들여진 시뮬레이션 문제입니다.

핵심아이디어는 돈이 허락하는 범위 안에서 5000원짜리 메뉴를 먹었을때 얻는 상대적 만족도가 가장 큰 경우를 선택해야 한다는 것입니다.

예를 들어서, 극단적으로 5000원짜리 메뉴의 만족도가 1만이라고 해도 1000원짜리 메뉴의 만족도가 9999라면 상대적 만족도는 1에 불과합니다. 또 역으로 1000원짜리 메뉴가 더 만족스러운 경우도 가능할 수 있습니다.

가장 만족스러운 식사를 하려면 날짜와 만족도에 상관없이 상대적 만족도가 큰 5000원짜리 메뉴부터 골라서 가능한만큼 선택하는것이 해결방법입니다.

따라서 A메뉴와 B메뉴의 만족도의 차이를 기준으로 입력된 데이터를 정렬해주고, 돈이 허락하는 한에서 A메뉴를 선택했습니다. 돈이 가능한지 여부는 (골라야하는 남은 메뉴의 갯수 * 1000) + 4000 보다 현재 자금이 크거나 같으면 가능하다고 조건문을 잡아두었고 메뉴를 하나 고를때 마다 자금에서 5000원씩을 빼 주었습니다.

또, 정렬을 통해서 B메뉴의 만족도가 더 큰 시점이 오면 이후로는 전부 B메뉴를 선택했습니다. B메뉴를 선택하기 시작한 경우는 두가지입니다.

1. 돈이 부족해서 남은 모든 식사는 B메뉴로 골라야 한다. (조건문을 통해 보장됨)

2. 남은 모든 식사들은 B메뉴가 A메뉴보다 맛있다. (정렬을 통해 보장됨)

따라서 이후로는 돈 계산을 하지 않고 B메뉴의 만족도를 계속 더해주었습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long answer = 0;

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int money = Integer.parseInt(st.nextToken());
		int[][] menu = new int[N][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			menu[n][0] = Integer.parseInt(st.nextToken());
			menu[n][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(menu, (e1, e2) -> {
			return (e2[0] - e2[1]) - (e1[0] - e1[1]);
		});

		int n = 0;

		while (money - ((N - n) * 1000) >= 4000) {
			if(menu[n][1] > menu[n][0]) {
				break;
			}
			answer += menu[n][0];
			money -= 5000;
			n++;
		}
		while (n < N) {
			answer += menu[n][1];
			n++;
		}
		
		System.out.println(answer);
	}
}

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/12904

1. 이해 (5분) - 2분

원리를 깨달으면 간단한 시뮬레이션 문제입니다.

다만, 문자열 관련해서 코드를 작성할 이해도가 필요할 것 같습니다.

문제는 간단명료합니다. 앞의 문자열에 두 가지 연산을 적용해서 뒤 문자열을 만들 수 있는지를 찾습니다.

간단히 생각하면 앞의 문자에 두가지 연산을 계속 적용해서 가능한 모든 경우의 수를 볼 수도 있겠지만... 

S의 길이가 1이고, T의 길이가 1000이라면? 2^1000가지 경우를 탐색해야 하니 어마어마한 일이겠죠. 

대신 연산의 조건을 파악하고 완성된 문자열에서 거꾸로 짚어가는 식으로 가부를 판단하려고 합니다.

2. 계획 (5분) - 4분

문자열에 적용한 연산 두가지는 모두 뒤쪽에 알파벳을 하나 더 붙입니다.

즉 최종결과에서 가장 뒤에 있는 알파벳은 이전에 적용된 연산이 무엇이었는지를 알려줍니다.

두 번째 문자열이 앞의 문자열보다 더 긴 길이만큼 연산을 거꾸로 적용하면 앞의 문자열과 같은 길이의 가능한 문자열이 나오게 되고 이 문자열을 앞의 문자열과 비교해서 가부를 판단할 수 있습니다.

문자열을 실제로 뒤집어서 풀이해도 되지만 저는 dir라는 boolean타입 변수를 하나 선언해서 투포인터 식으로 앞과 뒤에서 문자열을 줄여가는 방식으로 코드를 작성했습니다.

3. 검증 (5분) - 1분

시간복잡도나 메모리에서 문제가 생길 부분은 없을 것 같고, 구상한 대로 잘 풀이된다면 코드도 문제없이 작동할 겁니다.

4. 풀이 (30분) - 25분

문제의 이해와 계획은 금방 끝났지만 코드 작성에선 시간을 꽤 사용했습니다. 

반복문을 복잡하게 사용하다 보니 디버깅을 사용해서 제대로 동작하는지 검증을 철저히 했습니다.

5. 채점, 디버깅

다행히 제출은 한 번에 통과했습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();

		int N = s2.length - s1.length;

		int front = 0, back = s2.length - 1;
		boolean dir = true;

		for (int n = 0; n < N; n++) {
			if (dir) {
				if (s2[back] == 'A') {
					back--;
				} else {
					back--;
					dir = false;
				}
			} else {
				if (s2[front] == 'A') {
					front++;
				} else {
					front++;
					dir = true;
				}
			}
		}

		boolean answer = true;

		if (dir) {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[front + n]) {
					answer = false;
					break;
				}
			}
		} else {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[back - n]) {
					answer = false;
					break;
				}
			}
		}

		if (answer) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}