내일은 알고리즘

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

슬라이딩 윈도우(혹은 투포인터), 맵 자료구조의 개념을 알면 쉽게 풀 수 있는 문제입니다.

가입한 날로부터 10일간 할인을 받을 수 있는 것을 이용해 1~10일동안 살 수 있는 품목을 카운팅합니다.

만약 2~11일 동안 살 수 있는 품목이 궁금하다면, 10일간을 전부 찾을게 아니라 카운팅한 값에서 1일의 할인상품을 빼주고,  11일의 할인상품을 더해주면 됩니다.

우리가 원하는 상품목록이 있기 때문에 그 상품들만 찾아주면 되고 카운팅과 범위 처리는 예외가 나지 않도록 적당히 잘 해주면 됩니다. (설명이 좀 그런데 정말 적당히 잘 하면 됩니다. ㅋㅋ;;)

def solution(want, number, discount) -> int:
    answer = 0
    product = {}
    idx = 0

    for w in want:
        product[w] = idx
        idx += 1

    for i in range(10):
        if discount[i] in product:
            number[product[discount[i]]] -= 1

    for i in range(len(discount)):
        if checklist(number):
            answer += 1

        if discount[i] in product:
            number[product[discount[i]]] += 1
        
        if i + 10 < len(discount) and discount[i + 10] in product:
            number[product[discount[i + 10]]] -= 1

    return answer


def checklist(number) -> bool:
    for n in number:
        if n > 0:
            return False
    return True

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

또 다른 투 포인터 문제입니다. 

정확히는 슬라이딩 윈도라고 할 수 있겠네요. 

기본적인 투 포인터가 데이터의 양 쪽 끝에서 좁혀 들어오면서 탐색한다면, 슬라이딩 윈도는 한쪽 끝에서 시작해서 연속된 특정 범위를 찾습니다.

조금 더 상세히 설명해 볼까요?

N길이의 수열에서 연속된 부분을 구한다는 것은, 연속된 부분합의 시작점과 끝점을 정한다는 뜻입니다.

즉 N*N개의 경우가 존재한다는 뜻입니다.

슬라이딩 윈도우는 이 시작점과 끝점을 모든 경우에 대해 계산해보지 않고, 현재 부분에서 조건보다 작으면 연속된 부분을 늘리고 크면 연속된 부분을 줄이면서 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] num = new int[N];

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

		int left = 0;
		int right = 1;
		int sum = num[0];
		int answer = 100_001;

		while (left < N) {
			if (sum >= S) {
				answer = Math.min(answer, right - left);
				sum -= num[left];
				left++;
			} else {
				if (right == N) {
					break;
				} else {
					sum += num[right];
					right++;
				}
			}
		}
		if(answer == 100_001) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}

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

정석적인 투포인터 문제입니다.

투포인터 알고리즘에 대해선 나중에 포스팅을 작성해 보도록 하겠습니다.

투포인터 알고리즘을 통해 절댓값이 0에 가장 가까운 두개의 특성값을 기록하고 출력하면 간단히 풀립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));

		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int value = Integer.MAX_VALUE;
		int[] answer = new int[2];

		st = new StringTokenizer(br.readLine());

		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = N - 1;

		while (left < right) {
			int sum = num[left] + num[right];
			int abs = Math.abs(sum);

			if (abs < value) {
				value = abs;
				answer[0] = num[left];
				answer[1] = num[right];
			}

			if (sum <= 0) {
				left++;
			} else {
				right--;
			}

		}
		System.out.println(answer[0] + " " + answer[1]);
	}
}