[백준] S5 5555번 반지 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

5555번: 반지

[문제] 

당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다.

찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라.

[입력]

입력은 총 2 + N 줄 이다.

첫 번째 줄에는 1 자 이상 10 자 이하의 대문자로 구성된 찾고자 하는 문자열이 적혀있다.

두 번째 줄에는 반지의 개수 N (1 ≦ N ≦ 100)이 적혀있다.

2+i 줄(1 ≦ i ≦ N)엔 i개의 반지에 새겨져있고, 10 문자로 이루어진 문자열이 적혀있다.

[출력]

찾고자하는 문자열을 포함 반지의 개수를 나타내는 정수를 한 줄로 출력하라.

 

 

---

[풀이]

1. 반지에 새겨진 문자열의 마지막부터 문자열이 완성되는 경우가 있다.

2. 이를 해결해주기 위해 반지에 새겨진 문자를 한 번 더 뒤에 붙여주었다.

3. 그 후, contains를 사용해 찾는 문자열이 있는 경우 cnt를 증가시켜 주고 이를 출력하였다.

[접근]

1. 처음에는 슬라이딩 윈도우 기법으로 문제를 해결하려고 했다.

2. 하지만 contains를 사용하면 더 편하게 풀 수 있을 것 같아 이를 이용하여 해결하기로 하였다.

3. 반지에 적힌 문자열을 뒤에 1번 더 붙여주게 되면 한 바퀴를 돌아가게 된 경우에도 찾는 문자열을 판별할 수 있다.

4. 이를 이용해 ring 뒤에 추가로 ring을 붙여주고 contains를 사용해 문자열이 있는 경우 값을 추가하도록 하여 해결했다.

[코드]

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

public class Main_S5_5555 {
	static String str; // 찾고자 하는 문자열
	static int n; // 반지의 수
	static int cnt; // str이 새겨진 반지의 수
	static String ring; // 반지에 새겨진 문자열

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		str = br.readLine();
		
		n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			ring = br.readLine();
			String st = ring.substring(0, ring.length() - 1);
			
			ring += st; // 반지에 새겨진 글 뒤에 추가로 합치기
			
			if (ring.contains(str)) // 포함되어있다면 증가
				cnt++;
		}
		
		// 출력
		System.out.println(cnt);
	}
}