[알고리즘 PS] 백준 11656번 접미사 배열 자바 문제풀이

문제

해당 포스팅은 백준의 11656번 접미사 배열 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

문제 분석을 해보자.

 

우선 문자열 길이가 n인 문자가 들어온다.

 

그리고 우리는 그 문자열의 길이가 n-1, n-2 ... 1이 될 때 까지 반복해서 문자열을 나누고 해당 문자 배열을 정렬하면 된다.

시간 복잡도

혹시 모르니 시간 복잡도를 계산 해보자.

 

일단 문자열의 길이가 이번 반복의 주체인 n이 될 것이므로 n은 최대 1,000이다.

 

또한 우리는 java에 포함된 정렬 알고리즘을 사용할 것인데, java 정렬 알고리즘은 Object인 경우 TimSort를 수행한다.

TimSort의 시간복잡도는 평균 O(n log n)이고 최악의 경우 O(n^2) 이므로 최악의 경우 우리의 입력에는 1,000,000 번 이하의 반복을 수행할 수 있다.

 

시간 제한이 1초이므로 충분히 해결 가능한 수준이니 우리의 풀이에서 시간 복잡도는 문제가 되지 않을 것으로 보인다.

정답 코드

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] s = br.readLine().split("");
    String[] answer = new String[s.length];

    for(int i = 0; i < s.length; i++) {
      StringBuilder sb = new StringBuilder();
      for(int j = i; j < s.length; j++) {
        sb.append(s[j]);
      }
      answer[i] = sb.toString();
    }

    Arrays.sort(answer);

    for(String str : answer) {
      bw.write(str + "\n");
    }
    bw.flush();
    bw.close();
  }
}

그리고 연습삼아 Comparator을 이용해 정렬 기준 재정의로 정렬을 해볼 수 있다.

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] s = br.readLine().split("");
    String[] answer = new String[s.length];

    for(int i = 0; i < s.length; i++) {
      StringBuilder sb = new StringBuilder();
      for(int j = i; j < s.length; j++) {
          sb.append(s[j]);
      }
      answer[i] = sb.toString();
    }

    Comparator<String> myComparator = new Comparator<String>() {
      @Override
      public int compare(String s1, String s2) {
          return s1.compareTo(s2);
      }
    };

    Arrays.sort(answer, myComparator);

    for(String str : answer) {
      bw.write(str + "\n");
    }
    bw.flush();
    bw.close();
  }
}

 

두 방법 모두 잘 통과한다.

---

문제 회고

회고

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.