[Java] BOJ 2866 문자열 잘라내기

2866번: 문자열 잘라내기

---

오답 코드

• ArrayToString 함수 : 2차원 배열을 세로 문자열로 만들어주는 함수
• O(N^3)의 시간복잡도를 가지게 되면서 시간초과 발생

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int R, C;
    static char[][] arr;
    static Set<String> set1, set2;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new char[R][C];
        for (int i = 0; i < R; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        int cnt = 0;
        for (int i = 0; i < R - 1; i++) {
            set1 = new HashSet<>();
            set2 = new HashSet<>();
            
            for (int j = 0; j < C; j++) {
                String str1 = ArrayToString(i, j);
                String str2 = ArrayToString(i + 1, j);
                set1.add(str1);
                set2.add(str2);
            }

            if (set1.size() == set2.size()) {
                cnt++;
            } else if (set1.size() > set2.size()) {
                break;
            }
        }

        System.out.println(cnt);
    }

    private static String ArrayToString(int r, int c) {
        StringBuilder sb = new StringBuilder();
        for (int i = r; i < R; i++) {
            sb.append(arr[i][c]);
        }
        return sb.toString();
    }
}​

---

정답 코드

• 필요한 세로 문자열을 미리 생성해두고 필요할때 substring으로 잘라서 활용
• O(N^2)로 시간복잡도 감소

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int R, C;
    static char[][] arr;
    static String[] strings;
    static Set<String> set1, set2;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new char[R][C];
        for (int i = 0; i < R; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        strings = new String[C];
        for (int i = 0; i < C; i++) {
            strings[i] = ArrayToString(0, i);
        }

        int cnt = 0;
        for (int i = 0; i < R - 1; i++) {
            set1 = new HashSet<>();
            set2 = new HashSet<>();
            
            for (int j = 0; j < C; j++) {
                set1.add(strings[j].substring(i, R));
                set2.add(strings[j].substring(i + 1, R));
            }

            if (set1.size() == set2.size()) {
                cnt++;
            } else if (set1.size() > set2.size()) {
                break;
            }
        }

        System.out.println(cnt);
    }

    private static String ArrayToString(int r, int c) {
        StringBuilder sb = new StringBuilder();
        for (int i = r; i < R; i++) {
            sb.append(arr[i][c]);
        }
        return sb.toString();
    }
}