솜이의 데브로그

백준 5525번 ) IOIOI (java) 본문

Algorithm/백준

백준 5525번 ) IOIOI (java)

somsoming 2021. 9. 30. 22:03

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

 

5525번: IOIOI

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇

www.acmicpc.net

 

문제

 

 

풀이

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

public class Main {
	
	public static int solution(int n, int m, String s) {
		int answer = 0;
		String p = "";
		
		for(int i=0; i<n; i++) {
			p+="IO";
		}
		p+="I";
		
		for(int i=0; i<m; i++) {
			if(s.startsWith(p)) answer++;
			s=s.substring(1);
		}

		return answer;
	}
	
	
	public static int solution2(int n, int m, String s) {
		int answer=0;
		int cnt =0;
		
		char[] arr = s.toCharArray();
		for(int i=1; i<m-1; i++) {
			if(arr[i-1]=='I' && arr[i]=='O' && arr[i+1]=='I') {
				cnt++;
				if(cnt==n) {
					cnt--;
					answer++;
				}
				i++;
			}else cnt=0;
		}
		
		return answer;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		String S = br.readLine();
		
		System.out.println(solution2(N, M, S));
	}
}

 

 

 

설명

 

solution 의 경우, 서브태스크에서 1번만 만족한다.

Pn 문자열을 직접 생성 후, s 를 substring으로 앞에서부터 제거하며 해당 문자열로 시작하는지 카운트하는 방법이다.

비효율적인 풀이인듯

 

 

Solution2

Pn 문자열은 O가 n개 있는 문자열이다. 따라서 O를 기준으로 IOI 패턴이 n번 반복됨을 알 수 있다.

 

그러므로 반복문 i=1 부터 m-1 까지 돌면서, O를 기준으로 앞뒤로 I가 등장하는지를 카운트하고, IOI 패턴이 있는 경우 패턴의 카운트 수를 1씩 늘린다. 또 해당 패턴인 경우, i를 2 증가시켜야 하므로 if 문 안에서 i++ 를 진행한다.

마지막으로 패턴 카운트 수가 n과 일치하는 경우 (즉 Pn이 완성 된 경우) 답안을 1 늘리고, 다음 패턴도 진행되는지 확인해야하므로 패턴 수는 1 감소 시킨다.

 

패턴에 일치하지 않으면 애초에 Pn이 성립될 수 없으므로 패턴 카운트는 0으로 설정하고, i는 1씩 증가시키며 패턴이 나타나는지 확인한다.

위의 방법으로 진행하면 100점이 나온다.

 

 

 

느낀점

나는 아직 50점........

생각해내기 어려운정도는 아닌것같은데 머리에 딱 떠오르지 않는다.

슬프다....... 열심히하자^_ㅠ