2866 문자열잘라내기
https://www.acmicpc.net/problem/2866

이 문제를 보고 나서 문제도 이해가 안되서 과연 내가 풀 수 있을까? 라는 의문이 들었었다...

일단 문제 자체를 이해하는데 시간을 많이 소요하였다.
처음에는 문제가 수직방향으로 모든 문자들이 같으면 수행종료 라는줄 알았는데
다시 보니 수직방향 문자열을 만들고 수직방향 문자열들과 비교해서 중복되면 수행종료 였었다 ㅋㅋㅋㅋ

그래서 문제를 이해 한다음에는
처음으로 구현한것이 비교를 할수 있게끔 수직방향 문자열들을 만들어주는 것이었다.
여기까지는 되게 쉬웠는데

하나의 행을 삭제할때마다
수직방향 문자열들을 하나씩 비교하는것을 구현하려고 했으나
그냥 막 비교를 하자니 아무리 생각해도 무지막지한 시간이 소요된다는걸 느꼇고

DPS같은걸로 반복상태를 저장해서 최소화 시켜볼까? 라고 생각을 하였지만
반복하는 과정이 중복되지를 않아서... 이거는 아닌거같아서 포기하였다.

도저히 반복과정을 줄일 수 있는 방법이 생각이 안나서

생각을 다르게 해서 중복없는 자료구조에 대해서 생각하다가
자바에 Set이라는 것이 있는것을 확인을 하였고
구글링으로 Set, HashSet 자료구조를 공부를 해서
적용을 시켜서 풀어봤습니다.

Set의 종류

1. Set
   • 순서대로 입력되지 않음.
   • 중복된 원소를 허용하지 않음.
2. HashSet
   • 객체를 저장하기 전에 먼저 객체의 hashCode()메소드를 호출해서 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않습니다.
   • 매우 빠르게 삽입, 삭제, 탐색이 가능.
3. LinkedSet
   • 다른 Set들과 동일하게 중복은 허용하지 않으나 .add() 한 순서대로 값이 저장된다.
4. TreeSet
   • 오름차순으로 값을 정렬해 가지고 있으며 다른 set보다 대량의 데이터를 검색할 시 훨씬 빠르다.

다행히 바로 문제를 맞았습니다.

골드문제 수준은 문제가 요구하는 자료구조 및 알고리즘 선택을 잘하면
바로 풀수는 있는데
문제는 제가 자료구조 또는 알고리즘 종류들을 엄청나게 모른다는것...........
그래서 맨땅에 헤딩하면서 공부하려고 합니다....

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

        String[] rcInput = br.readLine().split(" ");

        int r = Integer.parseInt(rcInput[0]);
        int c = Integer.parseInt(rcInput[1]);

        String[] strs = new String[r];
        String[] columns = new String[c];
        Set<String> set;
        int count = 0;

        for(int i = 0; i < r; i++) {
            strs[i] = br.readLine();
        }

        for(int i = 0; i < c; i++) {    // 열 반복
            String temp = "";
            // 첫번째 행은 고려할 필요가 없음.
            for(int j = 1; j < r; j++) {    // 행 반복
                temp += strs[j].charAt(i);
            }
            columns[i] = temp;
        }

        boolean isFail = false;
        for(int i = 0; i < r; i++) {    // 행 반복
            set = new HashSet<>();
            for(int j = 0; j < c; j++) {    // 열 반복
                String str = columns[j].substring(i);
                if(set.contains(str)) {
                    isFail = true;
                    break;
                }
                else
                    set.add(str);
            }
            if(isFail)
                break;
            count++;
        }

        System.out.println(count);
    }