[백준, 자바, 30804번] 과일 탕후루

풀이

• 해당 문제는 뭔가 어려웠다.
• 우선 처음에는 어떻게 해결할 수 있을지 고민하다가
• 누적합으로 해결 할 수 있지 않을까 했는데
• 생각하다보니 20만 배열의 경우엔 너무 반복이 심할 것 같아서
• 고민을 했지만 우선 진행
• 하지만 역시나 시간초과...
• 그래서 아래에 태그를 확인해보니 투 포인터
• 물론 두 개의 인덱스로 어찌어찌 한다는 정도는 알지만
• 어떤 경우에 사용하면 좋은지 이해하고자, 
• 우선 개념을 이해하기로 함.

주요 개념
	포인터: 배열이나 리스트에서 특정 위치를 가리키는 인덱스입니다.
	두 포인터:
		왼쪽 포인터와 오른쪽 포인터를 초기화하고, 조건에 따라 이동시키면서 필요한 값을 찾습니다.
	시간 복잡도: 보통 **O(N)**으로 동작하며, 완전 탐색(O(N²))에 비해 효율적입니다.

투 포인터의 활용
	구간 합 문제:
		연속된 부분 구간(subarray)의 합을 빠르게 찾기.
	두 배열의 교집합:
		두 정렬된 배열에서 공통 요소 찾기.
	특정 조건 만족 구간:
		최소 길이의 구간 찾기, 예를 들어 슬라이딩 윈도우와 결합.


장점
	효율적: 시간 복잡도를 줄임.
	메모리 절약: 추가적인 자료 구조 없이 인덱스만으로 해결 가능.

 

• 이에 대한 개념과 추가 자료를 참고하여 아래와 같이 해결
• 우선 입력 값을 배열에 추가한 뒤
• 배열을 순차적으로 돌면서 Map에 해당 인덱스의 값을 key로 두고 카운팅
• 다만 put을 하며 해당 key의 기존 value를 가져오려고 하다보니
• 그냥 get 만 하게 되면 key가 없을 경우 null이기에
• 연산을 진행하면 에러처리가 발생
• 그래서 getOrDefault 메서드를 활용하여 없을 경우 0으로 초기화하는 작업을 진행
• 이후 탐색 구간에 주어진 과일 종류가 3개 이상의 경우엔
• 시작 포인트 부터 하나씩 차감 후 종류가 2개가 되도록 만들고
• 이후 시작 포인트를 1씩 증가
• 마지막으로 while 문 탈출 후
• 현재 거리를 계산한 값 중 가장 큰 값을 리턴하여 해결.

 

 

// 성공 코드(투 포인터)

import java.io.*;
import java.util.*;

public class _30804 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] li;
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        addFruits(N);
        System.out.println(findManyFruits(N));
    }


    private static void addFruits(int N) throws IOException {
        li = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) li[i]=Integer.parseInt(st.nextToken());
    }

    private static int findManyFruits(int N) {
        Map<Integer, Integer> fruits = new HashMap<>();
        int result = 0;
        int s = 0;
        for (int e=0; e<N; e++) {
            fruits.put(li[e],fruits.getOrDefault(li[e],0)+1);
            while (fruits.size()>2) {
                fruits.put(li[s],fruits.get(li[s])-1);
                if (fruits.get(li[s])==0) fruits.remove(li[s]);
                s++;
            }
            if (e-s+1>result) result = e-s+1;
        }
        return result;
    }
}

 

// 실패 코드(누적합)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] li;
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        addFruits(N);
        System.out.println(findManyFruits(N));
    }

    private static void addFruits(int N) throws IOException {
        li = new int[N+1][10];
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            li[i]= Arrays.stream(li[i-1]).toArray();
            li[i][Integer.parseInt(st.nextToken())]++;
        }
    }

    private static int findManyFruits(int N) {
        int result = 0;
        for (int i=1; i<N; i++) { // 기준
            for (int j=i+1; j<=N; j++) { // 이동
                int[] f_cnt = {0,0}; // 과일 종류, 총 개수
                for (int k=0; k<9; k++) {
                    if (li[j][k]-li[i-1][k]!=0) {
                        f_cnt[0]++; // 과일 카운팅
                        f_cnt[1]+=li[j][k]-li[i-1][k]; // 총 개수 카운팅
                        if (f_cnt[0]>2) break;
                    }
                }
                if (!(f_cnt[0]>2)&&f_cnt[1]>result) result=f_cnt[1];
            }
        }
        return result;
    }
}