[Algo] 백준 11656 접미사 배열 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/11656

메모리 : 19480KB

시간 : 208ms

언어 : Java 11

---

풀이

str을 뒤에서부터 탐색하며 접미사를 만들어 저장한 후 사전순으로 정렬해 출력한다.
여러가지 풀이를 시도해 보았다!

Array를 이용한 풀이

19172KB 208ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String str = br.readLine();
        String[] arr = new String[str.length()];
        String tmp = "";
        for (int i = str.length() - 1; i >= 0; i--) {
            tmp = str.charAt(i) + tmp;
            arr[i] = tmp;
        }
        Arrays.sort(arr);
        for (int i = 0; i < str.length(); i++) {
            sb.append(arr[i]).append('\n');
        }
        System.out.print(sb);
    }
}

List를 이용한 풀이

19480KB 208ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        List<String> list = new ArrayList<>();
        String str = br.readLine();
        String tmp = "";
        for (int i = str.length() - 1; i >= 0; i--) {
            tmp = str.charAt(i) + tmp;
            list.add(tmp);
        }
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)).append('\n');
        }
        System.out.print(sb);
    }
}

TreeSet을 이용한 풀이

19356KB 212ms

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        TreeSet<String> set = new TreeSet<>();
        String str = br.readLine();
        String tmp = "";
        for (int i = str.length() - 1; i >= 0; i--) {
            tmp = str.charAt(i) + tmp;
            set.add(tmp);
        }
        for (String i : set) {
            sb.append(i).append('\n');
        }
        System.out.print(sb);
    }
}

TreeMap을 이용한 풀이

19128KB 216ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        TreeMap<String, Integer> map = new TreeMap<>();
        String str = br.readLine();
        String tmp = "";
        for (int i = str.length() - 1; i >= 0; i--) {
            tmp = str.charAt(i) + tmp;
            map.put(tmp, i);
        }
        for (String i : map.keySet()) {
            sb.append(i).append('\n');
        }
        System.out.print(sb);
    }
}