백준 5555 반지

설명

문자를 contains로 비교하면 엄청 간단한 문제였을듯하지만, 문자를 원형으로 봐야 한다는 제약이 있었다.

 

그래서 문자를 뗏다 붙였다가 하는 방법을 고민하던 중, StringBuilder를 써서 delete하고 append하면 어떨까 생각이 들었다. append는 속도가 나쁘지 않을것 같은데, delete는 어떤가해서 찾아보니, 속도가 나쁘지 않았기에 활용해서 문제를 풀 수 있었다. 

 

[deleteCharAt]

deleteCharAt(int index) 메서드는 StringBuilder에서 특정 인덱스의 문자를 제거하는 방법으로, 일반적으로 성능이 매우 빠릅니다.

성능 관련 사항:
시간 복잡도: StringBuilder의 deleteCharAt 메서드는 O(n) 시간 복잡도를 가집니다. 이는 제거할 문자의 뒤에 있는 모든 문자를 앞으로 이동시켜야 하기 때문입니다. 하지만, StringBuilder가 내부적으로 배열을 사용하므로, 문자열의 길이에 비해 상대적으로 빠르게 수행됩니다.

문자 수에 따른 성능: 문자열의 길이가 매우 길 경우, 인덱스가 문자열의 시작 부분에 가까울수록 성능이 더 좋으며, 끝 부분에 가까울수록 성능 저하가 발생할 수 있습니다. 그러나 일반적인 사용에서는 큰 성능 문제는 발생하지 않습니다.

일반적인 사용: 대부분의 경우, deleteCharAt 메서드는 빠르게 수행되며, 성능 문제를 고려할 필요는 없습니다. 만약 반복적으로 많은 문자를 제거해야 하는 경우, 성능을 최적화하기 위해 다른 접근 방식을 고려할 수 있습니다.

결론적으로, 일반적인 상황에서는 deleteCharAt이 느리다고 느낄 가능성은 낮습니다. 성능 문제가 우려된다면, 특정 상황에서 벤치마킹을 통해 확인하는 것이 좋습니다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    // 5555
    public static void main(String[] args) throws IOException {
        process();
    }

    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        int N = Integer.parseInt(br.readLine());
        int resultCnt = 0;
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            // 문장이 그대로 존재하는 경우
            if(input.contains(line)) {
                resultCnt++;
                continue;
            }

            // 문장이 원형으로 존재하는 경우
            StringBuilder sb = new StringBuilder(input);
            for (int j = 0; j < input.length(); j++) {
                char c = sb.charAt(0);
                sb.deleteCharAt(0);
                sb.append(c);
                String s = sb.toString();
                if(s.contains(line)) {
                    resultCnt++;
                    break;
                }
            }
        }

        bw.write(resultCnt + " ");
        bw.flush();
        bw.close();
    }
}