백준 30804번
https://www.acmicpc.net/problem/30804

문제

---

생각하기

---

• 투 포인터 문제이다.

  • 왼쪽과 오른쪽의 포인터를 움직이면서 조건에 맞는 가장 긴 연속된 배열을 찾는다.

• 탕후루 과일을 진짜 제거하는 개념으로 접근하는 것이 아니라, 투 포인터를 통해서 왼쪽과 오른쪽 포인터를 이동함으로써 더 이상 해당 과일을 고려하지 않는다는 개념으로 접근해야됨

동작

2개의 숫자로 이루어진 연속된 배열의 가장 긴 길이를 찾는다.

    private static int twoPointer(int left, int right, int cnt, int kind, int max) {
        if (right >= N) {
            // right 포인터가 배열의 끝에 도달했음을 의미함
            return max;
        }

        if (nums[arr[right]] == 0) {
            kind++;
        }

        cnt++;
        nums[arr[right]]++;

        // 만약 과일의 종류가 2개를 넘으면, 왼쪽의 포인터를 이동한다.
        if (kind > 2) {
            if (--nums[arr[left]] == 0) {
                kind--;
            }
            cnt--;
            left++;
        }

        max = Math.max(max, cnt);

        // left pointer는 그대로 두고, right 포인터만 배열의 끝으로 계속해서 이동
        return twoPointer(left, right + 1, cnt, kind, max);
    } // End of twoPointer()

결과

코드

---

import java.io.*;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;
    private static int[] nums = new int[10];

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(twoPointer(0, 0, 0, 0, 0));
        return sb.toString();
    } // End of solve()

    private static int twoPointer(int left, int right, int cnt, int kind, int max) {
        if (right >= N) {
            // right 포인터가 배열의 끝에 도달했음을 의미함
            return max;
        }

        if (nums[arr[right]] == 0) {
            kind++;
        }

        cnt++;
        nums[arr[right]]++;

        // 만약 과일의 종류가 2개를 넘으면, 왼쪽의 포인터를 이동한다.
        if (kind > 2) {
            if (--nums[arr[left]] == 0) {
                kind--;
            }
            cnt--;
            left++;
        }

        max = Math.max(max, cnt);

        // left pointer는 그대로 두고, right 포인터만 배열의 끝으로 계속해서 이동
        return twoPointer(left, right + 1, cnt, kind, max);
    } // End of twoPointer()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        String s = br.readLine();
        for (int i = 0; i < N; i++) {
            arr[i] = s.charAt(i << 1) - '0';
        }
    } // End of input()
} // End of Main class