[백준 2371] 파일 구별하기 - JAVA

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

 

조건이 애매해서 글 올림

https://www.acmicpc.net/board/view/159125

 

풀이

 

k = 1부터,

각 파일을 k길이로 자른 subString을 set에 넣는다.

set.size() != N이라면 k++하고 다시 진행한다.

 

set.size() == N이라는 것은, 순서까지 고려 했을 때 다른 파일이 N개인 경우를 의미한다.

즉, 모든 파일이 구분되는 경우인 정답에 해당한다.

 

 

오답 요인

1. 파일을 수열과 같이 다루라고 써있어서 순서가 상관 없는줄 착각

2. 파일 별 최대 길이를 안줌(..)

 

그래서 set.equals()로 비교했는데 시간초과가 발생했었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    int N = Integer.parseInt(br.readLine());
    int k = 0;

    List<Integer>[] l = new ArrayList[N];

    for (int i = 0; i < N; i++) {
      l[i] = new ArrayList<>();
      st = new StringTokenizer(br.readLine());
      List<Integer> at = l[i];

      while (st.hasMoreTokens()) {
        int e = Integer.parseInt(st.nextToken());
        if (e == -1) {
          break;
        }
        at.add(e);
      }
    }

    StringBuilder sb = new StringBuilder();

    while (true) {

      k++;

      Set<String> set = new HashSet<>();

      for (int i = 0; i < N; i++) {
        int L = l[i].size();

        for (int j = 0; j < k; j++) {
          if (j < L) {
            sb.append(l[i].get(j));
          } else {
            sb.append('0');
          }
        }
        set.add(sb.toString());
        sb.setLength(0);
      }

      if (set.size() == N) {
        break;
      }
    }

    System.out.println(k);
  }
}