[백준 알고리즘] 1544번 : 사이클 단어 (Java) 문제 풀이

2 초

128 MB

1797

923

720

53.973%

문제

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다.

N개의 단어가 주어졌을 때, 서로 다른 단어가 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다.

출력

첫째 줄에 서로 다른 단어가 몇 개인지 출력한다.

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

1544번: 사이클 단어

문제에 대한 이해

단어를 입력받고 브루트포스로 이용하여 비교해야한다.

어떻게 풀 것인가?

단어를 입력받아 해당 단어가 기존에 있던 단어의 사이클 단어인지 비교한다.

기존에 있던 모든 단어들 중 입력받은 단어와 글자 수가 같은 단어들을 골라 해당 단어를 한 글자씩 돌려가며 입력받은 단어와 비교한다. 

비교 중 완전히 같은 단어가 만들어지면 입력단어는 기존 단어의 사이클 단어이므로 패스

기존에 있던 모든 단어들과 비교해봤지만 같은 단어가 만들어지지 않았다면 새로운 단어이므로 리스트에 입력

이를 반복하여 총 리스트에 입력된 단어들의 개수를 출력하면 된다

시간복잡도

O(N^2)이다.

공간복잡도

O(N)이다.

풀면서 놓쳤던점

쉽게 풀었다.

이 문제를 통해 얻어갈 것

브루트포스로 모든 경우의 수를 생각해야한다.

내 코드 

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

// 백준알고리즘 1544번 사이클 단어

public class Main {
    static int N;
    static ArrayList<String>[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new ArrayList[N];
        int result = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = new ArrayList<>();
            String str = br.readLine();
            for(int j=0; j<str.length(); j++){
                arr[i].add(str.substring(j)+ str.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 (str.equals(arr[j].get(k))) chk = false;
                }
            }
            if (chk)
                result++;
        }

        System.out.println(result);
    }
}