[백준] 2866번. 문자열 잘라내기(JAVA)

문제

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

---

풀이(14분)

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

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

        int R = Integer.parseInt(st.nextToken()); // R 행
        int C = Integer.parseInt(st.nextToken()); // C 열
        char[][] arr = new char[R][C];

        for(int i = 0; i < R; i++){
            String line = br.readLine();
            for(int j = 0; j < C; j++){
                arr[i][j] = line.charAt(j); // 입력받아 character로 저장
            }
        }

        Set<String> set = new HashSet<>(); // 문자열 중복을 검사
        List<String> list = new ArrayList<>(); // 최초로 만들어진 문자 리스트
        int count = 0; // 정답을 저장할 count
        StringBuilder sb; // 문자열을 만들어갈 스트링빌더
        for(int i = 0; i < C; i++){
            sb = new StringBuilder();
            for(int j = 0; j < R; j++){
                sb.append(arr[j][i]); // 세로로 문자열 만들기
            }
            set.add(sb.toString()); // 최초의 set
            list.add(sb.toString()); // 최초 단어 list 추가
        }

        if(set.size() != list.size()){ // 만약 처음부터 다르다면
            System.out.println(count); // 바로 0 출력
            return;
        }

        for(int i = 1; i < R; i++){
            set = new HashSet<>();
            for(int j = 0; j < C; j++){
                set.add(list.get(j).substring(i,R)); // 하나씩 빼고 문자열 추가
                if(j+1 != set.size()){ // 만약 문자열에 추가된 후에 크기가 다르다면
                    System.out.println(count); // 중복된 것이므로 정답 출력
                    return;
                }
            }
            count++; // 중복이 안 되었다면 count++
        }

        System.out.println(count); // 최종 정답 출력
    }
}

---

문제 풀이 전략

 

세로로 문자열을 만들어나가야 했기에 초기 시작을 어떻게 해야 할지 고민했다.

 

결론은 모든 문자열을 만들어 둔 뒤 (이때의 계산이 1000 x 1000이 사용된다.) 이것을 잘라나가며 set에 넣는 것이다.

 

가로로 하나씩 날려가며 다음과 같은 작업을 한다.

 

1. 날린 문자열을 set에 추가한다.

2. set의 크기와 현재 몇 열까지 추가되었는지를 비교한다.

3. set의 크기와 열을 가르키는 인덱스+1이 다르다면 중복된 문자열이 존재한다는 소리이다.

4. 중복되었다면 곧바로 정답을 출력한다.

5. 중복되지 않았다면 count++를 해준다.