과일 탕후루

과일 탕후루

 

백준 30804번 문제

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

 

 

 

1. 문제

 

 

 

2. 문제 풀이

2.1 조합

어떤 과일을 남겨야 가장 긴 탕후루를 만들 수 있을까?

아쉽게도 이에 대한 답을 한 번에 내기는 어렵다.

다행히 과일의 종류는 총 9개밖에 안되기 때문에 조합을 사용해 모든 경우의 수를 체크하는 방식으로 문제를 풀 수 있다.

주어진 과일에서 두개의 과일을 중복 없이 선택하고, 선택된 과일을 남겼을 때 가장 긴 탕후루를 구하면 된다.

 

조합은 다음과 같이 반복문을 통해 쉽게 구현할 수 있다.

 

[반복문을 통한 조합 구현]

for (int i = 0; i < fruitList.size() - 1; i++) {
    for (int j = i + 1; j < fruitList.size(); j++) {
        //탕후루에서 남길 과일
        int reservedFruit1 = fruitList.get(i);
        int reservedFruit2 = fruitList.get(j);

        int extractedTanghulu = extractFruit(reservedFruit1, reservedFruit2, tanghulu);

        if (extractedTanghulu > maxSize) {
            maxSize = extractedTanghulu;
        }
    }
}

 

fruitList는 과일들의 종류가 담겨있는 ArrayList이다. 

이중 반복문을 사용해서 주어진 과일들 중 남길 과일을 중복 없이 두 개 선택한다(reservedFruit1, 2)

extractFruit()는 남길 과일들을 인자로 받아서, 남길 과일 이외의 과일들을 제거했을 때 가장 길어지는 탕후루의 길이를 구하는 메서드이다.

 

 

2.2 슬라이딩 윈도우

이제, 남길 과일을 정했을 때 나머지 과일들을 제거해서 가장 긴 탕후루를 만들어야 한다.

그러나 여기서는 과일을 제거해서 가장 긴 탕후루를 만든다기보다는 남길 과일들이 연속적으로 이어졌을 때 가장 길어지는 구간의 길이를 구한다고 생각하는 게 좋다.

 

[탕후루 예시 그_1]

 

예를 들어 위 그림과 같은 탕후루가 있고 1과 2를 남기기로 했다고 하자.

이 경우 3과 4, 5를 제거하면서 1과 2로 이루어진 가장 긴 탕후루를 찾는 것보다 그냥 1과 2로 이루어진 가장 긴 탕후루를 찾는 것이 쉽고 빠르다.

 

슬라이딩 윈도우는 어떤 배열에서 연속된 구간을 탐색하는 알고리즘 기법이다.

슬라이딩 윈도우를 사용해서 가장 긴 탕후루를 구하는 방법은 다음과 같다.

 

1. 길이가 0인 구간을 만든다.

2. 배열의 앞부터 탐색하며 탐색한 원소가 남길 과일이면 구간을 늘린다.

3. 탐색한 원소가 남길 과일이 아니면 구간의 길이를 체크하고 다시 구간의 길이를 0으로 초기화한다.

 

위 방식으로 다음과 같이 문제를 풀어나갈 수 있다.

 

[윈도우 슬라이딩 그_1]

 

위와 같이 탕후루가 주어지고 남길 과일이 1과 2라고 하자.

우선 두 개의 포인터를 이용해 길이가 0인 구간을 만들어주고 배열의 맨 앞에 위치시킨다.

 

[윈도우 슬라이딩 그_2]

 

[윈도우 슬라이딩 그_3]

 

포인터(오른쪽)가 가리키는 값이 남길 과일(1)이기 때문에 포인터(오른쪽)를 오른쪽으로 이동시키며 구간을 늘린다.

 

[윈도우 슬라이딩 그_4]

 

[윈도우 슬라이딩 그_5]

 

같은 방식으로 오른쪽 포인터를 계속 이동시켜 주며 구간을 늘리다, 포인터가 가리키는 곳이 남길 과일이 아닌 경우(3) 탐색한 구간의 길이(=2)를 체크해 준 뒤 구간의 길이를 0으로 만들어 준다.

 

[윈도우 슬라이딩 그_6]

 

위와 같은 방식을 반복하며 가장 긴 탕후루의 길이를 구한다.

 

위의 과정은 다음과 같이 코드로 구현할 수 있다.

 

[extractFruit]

public static int extractFruit(int reservedFruit1, int reservedFruit2, int[] tanghulu) {

    int maxLength = 0;
    int right = 0;
    int left = 0;

    //탕후루 배열의 맨 앞 부터 시작해서 과일 두 종류로 이루어진 가장 긴 경우를 찾는다.
    //포인터가 가리키는 곳이 남겨야할 과일이라면 오른쪽 포인터만 오른쪽으로 이동시켜 연속되는 과일의 길이를 구한다.
    //오른쪽 포인터가 가리키는 곳이 남겨야할 과일이 아니라면 왼쪽 포인터를 오른쪽 포인터 다음으로 위치 시켜 구간을 초기화한다.
    while (right <= tanghulu.length) {

        //오른쪽 포인터가 가리키는 곳이 남겨야할 과일이 아닌경우 or 오른쪽 포인터가 배열의 길이를 넘어갔을 경우
        if (right == tanghulu.length || (tanghulu[right] != reservedFruit1 && tanghulu[right] != reservedFruit2)) {
            int length = right - left;
            if (length > maxLength) {
                maxLength = length;
            }

            left = right + 1;
            right++;
            continue;
        }

        //오른쪽 포인터가 가리키는 곳이 남겨야 할 과일인 경우
        if (tanghulu[right] == reservedFruit1 || tanghulu[right] == reservedFruit2) {
            right++;
        }
    }

    return maxLength;
}

 

 

 

3. 전체 코드

[전체 코드]

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

public class 과일_탕후루_30804 {

    public static int extractFruit(int reservedFruit1, int reservedFruit2, int[] tanghulu) {

        int maxLength = 0;
        int right = 0;
        int left = 0;

        //탕후루 배열의 맨 앞 부터 시작해서 과일 두 종류로 이루어진 가장 긴 경우를 찾는다.
        //포인터가 가리키는 곳이 남겨야할 과일이라면 오른쪽 포인터만 오른쪽으로 이동시켜 연속되는 과일의 길이를 구한다.
        //오른쪽 포인터가 가리키는 곳이 남겨야할 과일이 아니라면 왼쪽 포인터를 오른쪽 포인터 다음으로 위치 시켜 구간을 초기화한다.
        while (right <= tanghulu.length) {

            //오른쪽 포인터가 가리키는 곳이 남겨야할 과일이 아닌경우 or 오른쪽 포인터가 배열의 길이를 넘어갔을 경우
            if (right == tanghulu.length || (tanghulu[right] != reservedFruit1 && tanghulu[right] != reservedFruit2)) {
                int length = right - left;
                if (length > maxLength) {
                    maxLength = length;
                }

                left = right + 1;
                right++;
                continue;
            }

            //오른쪽 포인터가 가리키는 곳이 남겨야 할 과일인 경우
            if (tanghulu[right] == reservedFruit1 || tanghulu[right] == reservedFruit2) {
                right++;
            }
        }

        return maxLength;
    }

    public static void main(String[] args) throws IOException {
        //*초기화 시작*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        //과일을 원소로 갖는 배열
        int[] tanghulu = new int[size];
        //과일을 중복 없이 저장하기 위한 Set
        Set<Integer> fruitSet = new HashSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < size; i++) {
            int fruit = Integer.parseInt(st.nextToken());
            tanghulu[i] = fruit;
            fruitSet.add(fruit);
        }
        //*초기화 끝*

        List<Integer> fruitList = new ArrayList<>(fruitSet);
        //남길 수 있는 과일의 최대 갯수를 담는 변수
        int maxSize = 0;

        //과일 종류가 2개 이하이면 탕후루의 길이를 바로 반환
        if (fruitList.size() <= 2) {
            System.out.println(tanghulu.length);
            return;
        }

        //반복문으로 탕후루에서 남길 과일 2개를 조합을 이용해서 고르고, 탕후루의 최대 길이를 구한다.
        for (int i = 0; i < fruitList.size() - 1; i++) {
            for (int j = i + 1; j < fruitList.size(); j++) {
                //탕후루에서 남길 과일
                int reservedFruit1 = fruitList.get(i);
                int reservedFruit2 = fruitList.get(j);

                int extractedTanghulu = extractFruit(reservedFruit1, reservedFruit2, tanghulu);

                if (extractedTanghulu > maxSize) {
                    maxSize = extractedTanghulu;
                }
            }
        }

        System.out.println(maxSize);
    }
}