백준 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()

Kotlin으로는 숫자배열이 아닌 HashMap을 사용해서 풀었다

결과

코드

---

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

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var ans = 0
private lateinit var arr: IntArray
private lateinit var map: HashMap<Int, Int>
private lateinit var nums: IntArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

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

private fun solve(): String {
    val sb = StringBuilder()


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

private fun twoPointer(low: Int, high: Int, count: Int, kind: Int, max: Int): Int {
    if (high >= N) {
        return max
    }

    var newCount = count
    var newKind = kind
    var newLow = low
    var newMax = max

    if (nums[arr[high]] == 0) {
        newKind++
    }

    newCount++
    nums[arr[high]]++

    if (newKind > 2) {
        if (--nums[arr[low]] == 0) {
            newKind--
        }
        newCount--
        newLow++
    }

    newMax = max.coerceAtLeast(newCount)
    return twoPointer(newLow, high + 1, newCount, newKind, newMax)
} // End of twoPointer()

private fun input() {
    N = br.readLine().toInt()
    ans = -1
    map = HashMap()
    nums = IntArray(10)

    val st = StringTokenizer(br.readLine())
    arr = IntArray(N) {
        st.nextToken().toInt()
    }
} // End of input()