[백준] 5555번: 반지(문자열)

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

5555번: 반지

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		String s = scan.next();	// 찾고자 하는 문자열
		int sLen = s.length();	// 문자열 s의 길이
		int N = scan.nextInt();	// 반지의 개수
		String[] str = new String[N];
		String[] str2 = new String[N];
		for(int i=0; i<N; i++)
			str[i] = scan.next();
		for(int i=0; i<N; i++)
			str2[i] = "";

		int count = 0;
		
		for(int i=0; i<N; i++) {
			str2[i] += str[i].substring(str[i].length()-sLen+1, str[i].length());
			str2[i] += str[i];
			str2[i] += str[i].substring(0, sLen-1);
		}

		
		for(int i=0; i<N; i++) {
			// 문자열에 찾고자 하는 문자열(s)가 포함하는 경우
			if(str2[i].contains(s)) {
				count ++;
				continue;
			}
		}
		
		System.out.println(count);
		scan.close();
	}

}

풀이

문제에서 '문자열의 시작과 끝이 연결된 형태' 를 어떻게 처리해야 할지 고민을 좀 했다.

 

찾고자하는 문자열 - "XYZ"

주어진 문자열 - "YZAAAAAAAX"

 

위와 같은 경우에도 문자열의 시작과 끝이 연결되어 있기 때문에, X를 가장 앞으로 보내면 "XYZ" 라는 문자열은

포함되어 있다고 본다.

 

따라서 주어진 문자열에서 뒤에 문자열을 앞에붙이고, 앞에 문자열을 뒤에 붙여서 검색했다.

찾고자 하는 문자열은 "XYZ" 이고, 주어진 문자열은 "YZAAAAAAAAAX" 일때, 

찾고자하는 문자열길이의 -1 만큼 앞뒤로 붙여준다.

 (-1인 이유는 시작과 끝이 연결되어서 찾고자 하는 문자열이 되는경우를 생각하기 위해서다. -1을 안해도 상관은 없을 것 같다... 설명이 어렵다...)

 

그럼 주어진 문자열 "YZAAAAAAAX" 을 기준으로 보면

문자열 끝 2자리를 앞에 붙인다.

str2[i] = "AX"

str2[i] += str[i].substring(str[i].length()-sLen+1, str[i].length());

 

다음으로 기존의 문자열을 붙인다.

str2[i] = "AXYZAAAAAAAX"

str2[i] += str[i];

 

다음으로 문자열 앞 2자리를 뒤에 붙인다.

str2[i] = "AXYZAAAAAAAXYZ"

 

그 후 만들어진 문자열 배열 str2를 탐색하면서 찾고자 하는 문자열(s)가 존재하면 count를 증가시킨다.

 

 

 

다른풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String output;
        int count = 0;
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            output = br.readLine();
            output += output;
 
            if (output.contains(str)) {
                count++;
            }
        }
        System.out.println(count);
 
    }
}

 배열을 만들 필요도 없고, 문자열을 입력받을 때 마다 비교해준다.

위에서는 앞 뒤 연결을 위해 주어진 문자열을 2개를 합쳤다.

"ABC" -> "ABCABC"

훠어어얼씬 간단하고 좋은 코드다.