Baekjoon 30804. 과일 탕후루 / Java, Python

알고리즘 설명

문제 설명

과일 길이의 최댓값을 구한다. 단, 과일 종류는 두 종류 이하여야 한다.
과일은 앞, 뒤에서만 뺄 수 있다.

코드 설명

left, right를 증가시키며 최대 길이를 찾는 투포인터 알고리즘 방식을 적용했다.
과일의 종류가 9개밖에 안되므로 kind 배열을 사용해서 과일마다 몇개가 들어있는지를 계산했다.
최대 길이를 찾은 경우 -> 포인터 사이의 길이를 줄이면서 탐색하지 않는다, 즉 왼쪽을 한칸 당길 때, 오른쪽도 같이 당긴다.

import java.io.*;

public class Main {
    public static BufferedReader br;

    public static int n;	// 과일의 수
    public static int[] arr;	// 과일의 배열상태 저장
    public static int[] cntFruit;	// 과일종류별로 몇 개 골랐는지 저장

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        cntFruit = new int[10];

        String tmp = br.readLine();
        for (int i = 0; i < n ; i++) {
            arr[i] = tmp.charAt(i << 1) - '0';
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(sol(0, 0, 0, 0, 0)));
        bw.close();
    }

    private static int sol(int left, int right, int cnt, int kind, int max) {
        // 우측 포인터가 배열의 마지막에 도달하면 return
        if (right == n) {
            return max;
        }
        // 우측 포인터가 새로 도달한 과일이 새로운 과일이면 종류 수 증가
        if (cntFruit[arr[right]] == 0) {
            kind++;
        }
        // 도달한 과일 수 및 배열 길이 증가
        cntFruit[arr[right]]++;
        cnt++;
        // 과일 종류가 3개 이상이면 왼쪽 포인터를 이동
        if (kind > 2) {
            cntFruit[arr[left]]--;	// 왼쪽 포인터가 가리켰던 과일 수 -1
            cnt--;	// 배열 길이 감소
            if (cntFruit[arr[left]] == 0) {
                kind--;		// 왼쪽 포인터가 가리켰던 과일이 하나 남았었다면 종류 -1
            }
            left++;		// 왼쪽 포인터 이동
        }
        // 최댓값 갱신
        max = Math.max(cnt, max);
        // 재귀
        return sol(left, right + 1, cnt, kind, max);
    }
}

음.. 자바로 슬슬 알고리즘을 풀어보는데 쉽지 않다. 아래는 파이썬 코드

import sys; input = sys.stdin.readline

def sol():
	n = int(input())
    arr = list(map(int, input().split()))
    fruit_count = [0] * 10
    kind = 0
    s, e = 0, 0
    while True:
    	if e == n:
        	print(e - s + 1)
        	return
        e += 1
        if fruit_count[e] == 0:
        	fruit_count[e] += 1
            kind += 1
        if kind > 2:
        	fruit_count[s] -= 1
            if fruit_count[s] == 0:
            	kind -= 1
            s += 1
        
sol()