[백준] no5525: IOIOI

문제

: M에 포함된 2N+1길이의 IOI...OI의 개수 구하기

N: 필터링할 문자열 내 O의 개수 (즉, N이 2면, O이 두개 들어가므로, IOIOI. 즉 2N+1의 길이를 갖는다)

S: 탐색할 문자열 길이

M: 탐색할 문자열

 

문제 링크 : https://www.acmicpc.net/problem/5525

---

원리

1. OI의 개수를 구하는 것

2. OI조건이 성립하는동안 연속적으로 count해주며 개수를 파악하는것

3. OI조건이 맞는다면 그 맨 앞이 I가 맞는지 확인해줘 한다는 것

4. OI조건이 안맞는 특이점이 찾아오면 그 바로 다음부터 OI를 다시 세기 시작하는 것

5. 반복은 OI조건이 맞다면 +2씩, OI조건이 안맞는다면 +1씩 이동하면 반복해야한다는 것

 

---

풀이방법

1. 1~2번 방법과 같은 단순 반복의 경우, 모든 경우의 수를 전부 탐색해줘야 하여 시간초과가 난다.

2. 3번의 경우 N에 맞는 조건이 충족되는 경우를 연속적으로 카운트 해주고,

    만약 조건이 안맞는 특이점이 오면, 처음부터가 아닌 그 다음점부터 세어주기때문에 시간이 단축된다.

---

나의 코드

1. 이중 반복 비교 [ 백준 시간 초과 / 로컬 테스트 시간 70~160ms ]

import java.io.*;

public class no5525 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int S = Integer.parseInt(br.readLine());
        String low = br.readLine();
        String base = "I";
        for(int i = 0 ; i < N+(1*N) ; i++) {
            if(base.charAt(base.length()-1)=='O') base += "I";
            else base += "O";
        }

        int count = 0;
        for(int i=0 ; i<S-(N+2) ; i++ ) {
            for(int j=0 ; j<base.length() ; j++) {
                if(low.charAt(i+j)!=base.charAt(j)) break;
                if(j==base.length()-1) count++;
            }
        }

        System.out.println(count);
    }
}

 

2. 문자열을 추출하여 직접 비교 [ 백준 시간 초과 / 로컬 테스트 시간 120~150ms ]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int S = Integer.parseInt(br.readLine());
    String M = br.readLine();
    String base = "I";
    for(int i = 0 ; i < N+(1*N) ; i++) {
        if(base.charAt(base.length()-1)=='O') base += "I";
        else base += "O";
    }

    int count = 0;
    for(int i=0 ; i<S-(N+2) ; i++ ) {
        String compare = M.substring(i, base.length()+i);
        if(compare.equals(base)) count++;
    }

    System.out.println(count);
}

 

3. 문자열을 추출하여 직접 비교 [ 백준 통과 / 로컬 테스트 시간 70~150ms ]

import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 기준이 될 문자열에 포함된 O의 개수 (즉, 기준 문자열의 길이는 2N+1 이 된다.)
        int S = Integer.parseInt(br.readLine()); // 비교할 문자열 M의 길이
        String M = br.readLine();  // 비교할 문자열

        int count = 0; // "OI"의 개수를 count할 임시 변수
        int answer = 0;  // 결과값을 담을 변수
        int num = 1;  // 반복 조건용 변수. IOI중 OI만 셀 것이므로, I를 제외하기위해 1부터 시작
    
        // 2개씩 셀 것이므로, 0부터 S-2번 인덱스 까지 세기 위함 
        while(num<S-1) {
            // 만약 OI가 나오면,
            if(M.charAt(num) == 'O' && M.charAt(num+1) == 'I') {
                // 일단 하나 세고,
                count++;
                // 비교해야할 단위랑 일치하면, 
                if(count==N) {
                    // 맨 앞이 I인지 확인해서, I면 IOI...OI이므로 answer++
                    if(M.charAt(num-(count*2-1))=='I') answer++;
                    // 처음 세아린 만큼 -1 해줌 (즉, OIOI...OI의 맨 앞 OI만큼 센 거 빼줌)
                    count--;
                }
                // OI가 세트니까 2칸씩 움직어야하므로 +2
                num += 2;
            }
            else {
                // OI가 안나오면 그 부분 반복은 count초기화하고 시마이. 다음 칸으로 넘어감(이때는 OI가 아니므로 한칸만 이동)
                count = 0;
                num++;
            }
        }
        System.out.println(answer);
    }
}

 

 

---

레퍼런스 코드

참고 링크 : https://kwin0825.tistory.com/139