백준 1544 자바 - 사이클 단어 (BOJ 1544 JAVA)

문제 : boj1544

 

 

  최대 50길이의 String이 최대 50개 주어진다. 그럼 매번 단어가 주어질 때 마다 해당 단어의 사이클 단어를 전부 미리 만들어둔다고 해도, 최대 50x50 = 2500개의 단어밖에 나오지 않는다! 따라서 그냥 복잡하게 생각할 것 없이 2500개를 전부 만들면서 모든 단어끼리 비교해보면 된다. 로직은 다음과 같다.

 

1. n개의 ArrayList를 생성한다.

 

2. i번째 단어를 입력받을 시 i번 단어로 만들 수 있는 모든 사이클 단어를 만들어서 i번째 ArrayList에 집어넣는다.

 

3. 1번째부터 i-1번째 ArrayList들을 각각 전부 순회하며 동일한 단어가 있었는지 확인한다.

 

4. '3'에서 없었다면 cnt를 1 증가시킨다. i를 1 증가시키며 i가 n이 될때까지 2~4를 반복한다.

 

5. cnt를 출력한다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<String>[] arr = new ArrayList[n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = new ArrayList<>();
            String cur = br.readLine();
            for (int j = 0; j < cur.length(); j++)
                arr[i].add(cur.substring(j) + cur.substring(0, j));

            boolean chk = true;
            for (int j = 0; chk && j <= i-1; j++) {
                for (int k = 0; chk && k < arr[j].size(); k++) {
                    if (cur.equals(arr[j].get(k))) chk = false;
                }
            }
            if (chk)
                cnt++;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}