백준 5525번 ) IOIOI (java)

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

5525번: IOIOI

 

문제

 

 

풀이

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점........

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

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