백준[node.js] > 30804번 과일 탕후루

문제

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

 

풀이

처음 풀이는 시간초과가 나서 연산횟수를 줄이는 방법으로 접근하였다. 

 

내가 푼 방식은 이러하다

만약 과일이  1 2 2 3 3 4 5 6 7 8 9 이렇게 주어지면

 

[ 1 ] 을 담고 kind를 확인 한다.  ( kind:1, count: 1 )

[ 1, 2 ] 를 담고 kind, count를 확인한다.  (kind:2 count:2)

[ 1 , 2 , 2 ] 를 담고 kind와 count를 확인한다. (kind:2, count: 3 ) 

그다음  과일을 담으면

[ 1, 2 , 2, 3 ] 이 되고 kind는 3이 된다 이때 kind가 2가 될때까지 left를 올린다. 

여기서는 [ 2, 2, 3] 이 될 것이다. 이후에 kind와 count를 확인한다. ( kind:2, count:3 ) 

이런식으로 끝까지 진행하면 우리는 답을 구할 수 있다.

 

코드에서 실제로 과일을 담는 어레이는 존재하지 않는다.

대신 담긴 과일의 종류별 갯수를 나타내는 group이라는 어레이를 만들어 이를 참고하여 계산을 진행했다.

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let arr = input[1].split(" ").map((n) => Number(n));
let max = 0; // 최대 과일 갯수를 담을 변수
let group = Array(10).fill(0); // group [i] 는 현재 그룹에서 i번 과일이 몇개 있는지 나타냄
let left = 0; // 왼쪽 idx
let right = 0; // 오른쪽 idx
let count = 0; // 과일 갯수
let kind = 0; // 과일 종류
while (right < arr.length) {
    if (group[arr[right]] === 0) {
        kind += 1;
    }
    group[arr[right]] += 1;
    ++count;
    if (kind > 2) {
        // kind 2 될때까지 left를 올림

        while (kind > 2) {
            group[arr[left]] -= 1;
            if (group[arr[left]] === 0) {
                kind -= 1;
            }
            count -= 1;
            ++left;
        }
    }
    max = Math.max(max, count);
    ++right;
}

console.log(max);