[백준 - 31411번] 대회 개최 - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: 그리디, 정렬, 두 포인터

입력

첫 번째 줄에 알고리즘의 개수
$N$과 알고리즘마다 만든 문제 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le N,K \le 1\,000)$ 

이후
$N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 알고리즘의 $j$번째 문제의 난이도를 의미하는 정수 $d_{i1},\cdots,d_{iK}$가 공백으로 구분되어 주어진다. $(1 \le d_{ij} \le 100\,000)$ 

출력

$N$개의 문제들의 순서를 적절히 배치할 때 난이도 커브의 최솟값을 출력한다.

풀이

순서를 적절히 배치할 때 난이도 커브의 최솟값을 출력해야 한다.

만약 문제가 1 6 3 4 2 4 7 8과 같이 배치되었다고 했을 때 오름차순으로 정렬해서 배치하는 방식이 난이도 커브의 최솟값을 출력한다.

직접 N이 1일 때부터 하나씩 추가해서 어떻게 하면 작아질 수 있는지 증명해 보자, 그러면 결국 양쪽 끝을 작게 만들어 나가는 것이 난이도 커브의 값을 작게 만드는 방법이며, 그 전체 모습은 오름차순으로 정렬되어 있음을 알 수 있다.

그리고 난이도 커브의 값은 첫 번째와 마지막 문제 난이도 차의 절댓값이 된다.

그러면 결국 양쪽 끝의 차를 작게 만드는 것이 목표인데, N개의 문제를 전부 포함해야 되기 때문에 그러한 부분에서 값을 구해 비교하면 된다.

이는 두 포인터를 활용해 구할 수 있다.

먼저, 모든 문제를 list에 담고, 정렬한다. 이때 문제의 난이도만이 아닌 어떤 알고리즘인지도 포함해야 한다.

그리고 leftCursor는 0, rightCursor는 list.size() - 1부터 시작해서 leftCursor를 가장 오른쪽으로, rightCursor을 가장 왼쪽으로 땡겨준다.

여기서 가장이라는 것은 가능한 최대로라는 의미이고, 최대는 결국 모든 문제가 포함될 수 있는 마지막 index를 의미한다.

문제가 포함되는지는 간단하게 visited로 구할 수 있다. 만약 left를 기준으로 오른쪽으로 이동했을 때 그 왼쪽은 제외되기 때문에 제외되는 부분을 카운트해서 left ~ right사이에 모든 문제가 포함되고 있는지 알 수 있게 된다.

여기서 끝나는 것이 아닌 이번엔 leftCursor를 왼쪽으로 이동시키면서, rightCursor도 가능한 최대로 왼쪽으로 이동시키며 답을 가능한 경우 답을 구해 비교해 준다.

leftCursor가 왼쪽으로 이동한다면, 제외된 문제를 하나 포함하기 때문에 rightCursor가 더 움직일 수 있는 가능성이 생긴다.

그런데 생각해 보면, 이 구현 방식은 불필요한 부분이 포함되어 있다. 그냥 왼쪽 커서 0부터 시작해서 오른쪽 커서를 움직이고, 모든 문제가 포함된 경우 값을 비교하는 방식이 더 효율적이고, 구현도 간단해 진다. 그래서 후자의 방식으로 구현하길 바란다.

이 풀이의 시간 복잡도는 O(NK)다.

소스 코드

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

class Problem implements Comparable<Problem> {
    int algo, d;
    Problem(int algo, int d) {
        this.algo = algo;
        this.d = d;
    }
    
    @Override
    public int compareTo(Problem o) {
        if(this.d < o.d) {
            return -1;
        } else if(this.d > o.d) {
            return 1;
        }
        return 0;
    }
}

public class Main {
    static int N, K;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      
      if(N == 1) {
          System.out.println(0);
          return;
      }
      
      ArrayList<Problem> list = new ArrayList<>();
      for(int i=1; i<=N; i++) {
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          for(int j=0; j<K; j++) {
              int d = Integer.parseInt(st2.nextToken());
              list.add(new Problem(i, d));
          }
      }
      Collections.sort(list);
      int[] visited = new int[N + 1];
      int left = 0;
      
      for(int i=0; i<list.size(); i++) {
          if(visited[list.get(i).algo] + 1 == K) {
              left = i;
              break;
          }
          visited[list.get(i).algo] += 1;
      }
      
      int right = moveRightCursor(list.size() - 1, visited, list); //초기에는 left와 right는 절대 같을 수 없음.
      int answer = list.get(right).d - list.get(left).d;
      for(int i=left - 1; i>=0; i--) {
          //left를 왼쪽으로 한 칸씩 움직여준다.
          //그로인해 right가 왼쪽으로 움직이는 경우를 체크
          visited[list.get(i).algo] -= 1;
          for(int j=right; j>=1; j--) {
              //right가 왼쪽으로 움직였을 때
              if(visited[list.get(j).algo] + 1 == K) {
                  //불가능한 경우는 움직일 수 없음
                  right = j;
                  break;
              }
              //가능하다면
              visited[list.get(j).algo] += 1;
              if(list.get(i).algo != list.get(j - 1).algo) {
                answer = Math.min(answer, list.get(j - 1).d - list.get(i).d);
              }
          }
      }
      System.out.println(answer);
  }
  
  static int moveRightCursor(int cur, int[] visited, ArrayList<Problem> list) {
      int result = cur;
      for(int i=cur; i>=0; i--) {
          if(visited[list.get(i).algo] + 1 == K) {
              return i;
          }
          visited[list.get(i).algo] += 1;
      }
      return result;
  }
}