[Baekjoon] 과일 탕후루 - Java

문제

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

 

풀이

탕후루에 꽂는 과일이 있는데 탕후루에 과일이 2개가 되는 종류 중에 가장 긴 길이를 구하는 문제이다.

 

N이 20만이다. 즉 이중 for문을 돌면 시간초과가 난다.

 

투포인터로 순회하면 O(N)연산으로 수행할 수 있다.

 

1. 투포인터에서는 left, right 두가지 포인터가 존재하는데, right를 한개씩 이동하면서 종류의 개수를 센다.

 

2. right로 이동해서 종류가 3개가 넘어버리면 left로 종류가 2개 이하가 될때까지 left를 이동한다.

 

3. 최대 길이를 갱신한다.

 

소스코드

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

import java.util.StringTokenizer;

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

        int n = Integer.parseInt(br.readLine());

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

        int[] arr = new int[n];
        int[] cntArr = new int[10];

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

        int left = 0;
        int right = 0;

        int answer = Integer.MIN_VALUE;

        while (right < n) {
            cntArr[arr[right]] += 1;

            while (getCnt(cntArr) > 2) {
                cntArr[arr[left]] -= 1;

                if (cntArr[arr[left]] < 0) cntArr[arr[left]] = 0;

                left += 1;
            }

            answer = Math.max(answer, right - left + 1);

            right += 1;
        }

        System.out.print(answer);

        br.close();
    }

    private static int getCnt(int[] cntArr) {
        int cnt = 0;

        for (int c : cntArr) {
            if (c > 0) cnt++;
        }

        return cnt;
    }
}

 

실행결과