백준 30804번: 과일 탕후루

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

 

문제를 보고 맨 처음에는 단순히 과일 두 종류만을 남겼을 때, 가능한 최대 값을 구하는 건 줄 알았다.

틀리고 다시보니, 앞뒤에서부터 없애나가다가 남은 두 종류라는 것이 포인트라는 것을 깨달았다.

 

앞뒤에서 한 칸 씩 없애봐야 한다는 것, 그렇게 하여 최대값을 찾는 것을 브루트포스로 풀려고 했다.

일단, 재귀함수로 구현했고 그 매개변수로 현재의 꼬치에 남아있는 과일과 꼬치의 상태를 받아주었다.

재귀 함수 처음에는 꼬치에 있는 과일의 종류를 세고 2개 초과라면,

앞의 과일을 줄인 값과, 뒤에 과일을 줄인 값을 비교하여 더 큰 값을 리턴하는 하도록 했다.

만약 꼬치의 과일 종류가 2종류 이하라면 그냥 꼬치의 길이를 리턴하도록 했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] fruit = new int[10];
    int N = Integer.parseInt(br.readLine());
    int[] skewer = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      int token = Integer.parseInt(st.nextToken());
      fruit[ token ]++;
      skewer[i] = token;
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( del(fruit, skewer) + "");
    bw.flush();
    bw.close();
  }

  static int del(int[] fruit, int[] skewer) {
    int kind = 0;
    int res = 0;
    for (int i : fruit) if (i > 0) kind++;

    if (kind > 2) {
      fruit[ skewer[0] ]--;
      int case1 = del(fruit, Arrays.copyOfRange(skewer, 1, skewer.length));
      fruit[ skewer[0] ]++;

      fruit[ skewer[skewer.length - 1] ]--;
      int case2 = del(fruit, Arrays.copyOf(skewer, skewer.length - 1));
      fruit[ skewer[skewer.length - 1] ]++;
      res = (case1 > case2) ? case1 : case2;
      return res;
    }
    else return skewer.length;
  }
}

해당 코드는 재귀함수 내부에서 copyOfRange로 배열을 계속 생성하기 때문에

메모리 초과가 날 수도 있겠다고 생각했는데, 실제로도 그러했다.

 

그래서 다음으로는 앞뒤로 값을 넣고 빼기 쉬운  Deque를 사용해서 구현하기로 했다.

함수 내부에서 재귀함수로 배열을 주는 게 사실상 static을 쓰는 것과 큰 차이가 없다고 느껴서

함수 내부에서 필요한 배열과 Deque를 static으로 선언해주었고, 

꼬치의 상태를 배열로 만들고 새로운 배열을 만들어 다음 함수로 넘겼던 것과 달리

static으로 만들었기 때문에 Deque에서 뺀 값은 나중에 함수를 빠져나오면서 다시 추가하는 것으로 코드를 고쳤다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Arrays;

public class Main {
  static int[] fruit = new int[10];
  static Deque<Integer> skewer = new LinkedList<>();

  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());
    for (int i = 0; i < N; i++) {
      int token = Integer.parseInt(st.nextToken());
      fruit[ token ]++;
      skewer.addFirst(token);
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( del() + "" );
    bw.flush();
    bw.close();
  }

  static int del() {
    int kind = 0;
    int res = 0;
    for (int i : fruit) if (i > 0) kind++;

    if (kind > 2) {
      int temp = skewer.pollFirst();
      fruit[ temp ]--;
      int case1 = del();
      fruit[ temp ]++;
      skewer.addFirst(temp);

      temp = skewer.pollLast();
      fruit[ temp ]--;
      int case2 = del();
      fruit[ temp ]++;
      skewer.addLast(temp);

      res = (case1 > case2) ? case1 : case2;
      return res;
    }
    else return skewer.size();
  }
}

이로써 메모리 초과는 극복했지만, 이제 시간 초과에 당면했다.

이를 극복하기 위해 꼬치의 존재하는 과일의 종류를 확인하는 용도로 쓰던 배열을 지우고

해당 역할을 Deque에 .contatins()함수를 사용하는 것으로 바꾼다던가,

기존 코드가 앞을 지울 때랑 뒤를 지울 때랑 같이 있어서 그런가 싶어 둘을 나눠보는 등의 시도를 했지만

전부 실패했다.

 

문제에서 앞에서 a개, 뒤에서 b개를 빼서 N - (a + b)가 된다는 부분에 영감을 받아서

꼬치를 String으로 받고, 과일의 종류를 미리 센 다음

함수에서 꼬치의 상태를 변화시키는 것이 아니라

현재 꼬치의 시작과 끝을 나타내는 값으로 사용한 a, b와

indexOf, lastIndexOf 함수로 해당 범위 내에 없애려는 과일과 같은 종류가 있는지 여부에 따라

과일 종류의 값을 변화시켰다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
  static String skewer;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    
    int N = Integer.parseInt(br.readLine());
    skewer = new String(br.readLine());
    skewer.replaceAll(" ", "");

    int kind = 0;
    for (int i = 1; i < 10; i++) 
      if ( skewer.contains(String.valueOf(i)) ) kind++;
 
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( del(0, N, kind) + " ");
    bw.flush();
    bw.close();
  }

  static int del(int a, int b, int kind) {
    if (kind > 2 && a + 2 < b) {
      int case1 = 0;
      if ( skewer.indexOf( String.valueOf( skewer.charAt(a) ), a + 1 ) == -1 )
        case1 = del(a + 1, b, kind - 1);
      else case1 = del(a + 1, b, kind);

      int case2 = 0;
      if ( skewer.lastIndexOf( String.valueOf( skewer.charAt(b - 1) ), b - 2 ) == -1 )
        case2 = del(a, b - 1, kind - 1);
      else case2 = del(a, b - 1, kind);

      return (case1 > case2) ? case1 : case2;
    }
    else return b - a;
  }
}

이 코드까지 실패하고 퍼뜩 아이디어가 떠올랐다.

결국, 이어져 있는 두 종류의 과일의 길이를 구하면 되니까 입력받으면서

과일의 종류가 세 종류가 넘어가면 맨 앞의 과일은 없애고, 뒤의 두 종류만 남기도록 했다.

그렇게 해서 기존의 두 종류의 과일과 다른 종류의 과일이 들어오면 그 길이를 새로 구하기 시작하고,

기존의 두 종류의 과일과 같은 종류의 과일이 들어오면 그저 길이를 늘려서 기록해서

순간순간의 길이와 기존 최대값을 비교하도록 했다.

 

이렇게 한다면 입력을 받으면서 코드가 돌아가니 시간도 아낄 수 있고,

또다른 재귀함수나 전역변수, 다른 자료구조를 사용할 필요가 없으니 메모리에도 문제가 없을 거라고 생각했다.

실제로 그러했고, 덕분에 문제를 풀 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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 front = Integer.parseInt(st.nextToken());
    int rear = 0;
    int rrPt = 0;
    int res = 1;
    int length = 1;
    for (int i = 1; i < N; i++) {
      int token = Integer.parseInt(st.nextToken());
      if (rear == 0) {
        if (token != front) {
          rear = token;
          rrPt = i;
        }
        length++;
      }

      else if (token != rear) {
         if (token != front) { //new value
          front = rear;
          rear = token;

          length = i - rrPt + 1;
          rrPt = i;
        }
        else { //front == token, 앞뒤 바꾸기
          front = rear;
          rear = token;

          rrPt = i;
          length++;
        }
      }

      else { //token == rear
        length++;
      }

      res = (length > res) ? length : res;
    }
      
 
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write( res + " ");
    bw.flush();
    bw.close();
  }
}