[BOJ] 5525 IOIOI

IOIOI

풀이

• 주어진 문자열 S에 조건으로 주어진 Pn 문자열이 몇개 있는지를 구하는 문제라, 처음에 그냥 Pn을 만들어 두고, substring 이용해서 비교하는 식으로 했다. 그랬더니 50점 . . .

  🙅‍ 50점 풀이

      import java.util.*;
      import java.io.*;
      public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          int M = Integer.parseInt(br.readLine());
          StringBuilder sb = new StringBuilder();
          for(int i=0;i<N;i++){
              sb.append("IO");
          }
          sb.append("I");
          int answer = 0;
          String str = br.readLine();
          char[] strArr = str.toCharArray();
          for(int i=0;i<strArr.length;i++){
              if(strArr[i]=='I' && (i+2*N+1)<=strArr.length){
                  String substr = str.substring(i,i+2*N+1);
                  if(substr.equals(sb.toString())){
                      answer++;
                  }
              }
          }
          System.out.println(answer);
          }
       }

• 아무리 생각해도 내 머리로는 100점을 어떻게 맞아야할지 모르겠었다. 결국 코드 참고 ㅎㅎ;

  🙆‍♀️ 100점 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
     public static void main(String[] args) throws Exception{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int N = Integer.parseInt(br.readLine());
         int M = Integer.parseInt(br.readLine());
         //OI가 N개 들어가는지 확인하고, 앞에 I가 있는지를 확인하면 된다.
         int answer = 0;
         int[] memo = new int[M];
         char[] str = br.readLine().toCharArray();
         for(int i=1;i<M-1;i++){
             if(str[i]=='O' && str[i+1]=='I'){
                 memo[i+1] = memo[i-1]+1;
                 if(memo[i+1]>=N && str[i-2*N+1]=='I'){
                     answer++;
                 }
             }
         }
         System.out.println(answer);
     }
  }

  그니까 핵심은? Pn 문자열은, "OI"가 N번 들어가고, 맨 앞에 "I"가 붙은 문자열 이라고 생각하면 쉽다는 거다.

  memo[i]는, i까지 봤을 때 "OI"가 나온 횟수이다.
  코드를 보면, 내가 보고 있는 문자열에서 "O"를 만나면, 그 다음 index, 그니까 i+1 번째 문자가 I인지 확인한다.
  즉 "OI"를 만났으면, memo[i+1]=memo[i-1]+1 을 해줌으로써, 그 전까지 OI가 나온 횟수에 +1을 해준다.
  인덱스가 i+1, i-1로 보는 이유는 "I"를 기준으로 "OI" 갯수를 세주고 있기 때문이다.

  그렇게 세 주고 난 다음에,
  지금 내가 보고 있는 memo[i+1]>=N 즉, "OI"가 N개 다 나온 경우, str[i-2*N+1]='I' 를 확인해주는데,
  이것은 앞에서 말한 것 처럼 "OI" 갯수가 N개인지 확인한 뒤, 맨 앞 문자열이 "I"인지를 확인하는 것이다.
  이 조건까지 충족한다면 answer를 하나 늘려준다.

나중에 풀었을 때 이 풀이가 기억날지 모르겠다..^^ 와닿지 않았다.... 하지만 이겨내 견뎌내 해내