백준 1544번 사이클 단어 Java

: ) YOUNG·2024년 1월 31일
1

알고리즘

목록 보기
306/417
post-thumbnail

백준 1544번
https://www.acmicpc.net/problem/1544

문제



생각하기


  • 문자열을 시계방향으로 회전시키는게 핵심인 문제이다.

동작


    private static boolean find(String s) {
        if (set.contains(s)) return true;

        StringBuilder sb = new StringBuilder();
        sb.append(s);
        int len = s.length();
        for (int i = 1; i < len; i++) {
            sb.append(sb.charAt(0)).deleteCharAt(0);
            if (set.contains(sb.toString())) {
                return true;
            }
        }

        return false;
    } // End of find()

find()메소드에서 같은 문자열이 있는지를 찾아내는데 문자열을 하나씩 뜯어서 시계방향으로 회전시키면서 찾는다.

회전 방법은 기존의 전체 문자열s를 먼저 StringBuilder sb에 넣고, 문자열 길이 - 1만큼 반복한다.


가장 앞에 있는 문자 sb.charAt(0)은 가장 뒤로 붙여주고, 가장 앞에있는 문자는 다시 deleteCharAt(0)을 통해서 지워준다.

이렇게 시계방향으로 사이클을 돌면서 같은 문자열이 있는지 찾을 수 있다.



결과


코드



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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static HashSet<String> set;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        set.add(br.readLine());
        for (int i = 1; i < N; i++) {
            String temp = br.readLine();
            if (!find(temp)) {
                set.add(temp);
            }
        }

        sb.append(set.size());
        return sb.toString();
    } // End of solve()

    private static boolean find(String s) {
        if (set.contains(s)) return true;

        StringBuilder sb = new StringBuilder();
        sb.append(s);
        int len = s.length();
        for (int i = 1; i < len; i++) {
            sb.append(sb.charAt(0)).deleteCharAt(0);
            if (set.contains(sb.toString())) {
                return true;
            }
        }

        return false;
    } // End of find()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        set = new HashSet<>();

    } // End of input()
} // End of Main class

0개의 댓글