[백준] IOIOI JAVA

알고리즘/코딩테스트-백준

[백준] IOIOI JAVA

kwang2134 2024. 9. 22. 16:05

728x90

[백준] IOIOI - SILVER I 5525번

접근

KMP (Knuth-Morris-Pratt)
LPS (Longest Prefix Suffix)

풀이

오랜만의 백준에서의 문제풀이로 문자열 내 특정한 패턴이 몇 번 등장하는지 체크하는 IOIOI 문제이다. 해당 문제는 서브태스크가 존재하는 문제로 문제에서 주어진 N과 M의 범위는

1 ≤ N ≤ 1,000,000
2N+1 ≤ M ≤ 1,000,000

으로 매우 큰 범위의 값을 가지지만 서브 태스크 1번의 경우 N ≤ 100, M ≤ 10,000로 어떻게 풀어도 50점은 맞을 수 있는 문제라는 것이다. 문제에서 주의할 점은 IOI 형태의 패턴 등장 횟수를 구해야 하는데 처음과 마지막이 같은 I로 겹치는 상황이기 때문에 그 부분만 처리를 주의해주면 된다.

우선 내가 50점만(?) 받겠다 하면 사용할 수 있는 코드이다.

//서브 태스크 1번 50점 코드

import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

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());
        int m = Integer.parseInt(br.readLine());

        String s = br.readLine();

        StringBuilder sb = new StringBuilder();
        sb.append("I");

        for (int i = 0; i < n; i++) {
            sb.append("OI");
        }

        Pattern pattern = Pattern.compile(sb.toString());
        Matcher matcher = pattern.matcher(s);

        int count = 0;
        int index = 0;

        while (matcher.find(index)) {
            count++;
            index = matcher.start() + 1;
        }

        System.out.println(count);

        br.close();
    }
}

우선 입력 받은 n을 통해 패턴을 생성한 뒤 정규 표현식을 사용해 Pattern 클래스에 패턴을 등록하고 Matcher 클래스에 문자열을 등록한 뒤 문자열 안에 패턴이 매칭될 때마다 count를 증가시켜 주는 방법이다. matcher.find(index)를 사용해 문자열의 index 부터 검색을 시작하고 패턴이 발견되면 카운트를 증가시킨 뒤 index 값을 변경해 패턴이 검색된 후 다음 인덱스부터 다시 검색을 시작하게 한다. 이 방법은 O(N x M) 으로 서브태스크 1번만 통과가 가능하고 변수의 범위가 넓어진 서브태스크 2번은 통과할 수 없다.

제한 시간 내에 서브태스크 2번 통과를 위해선 KMP (Knuth-Morris-Pratt) 알고리즘과 LPS (Longest Prefix Suffix) 배열을 사용하여 문자열 검색을 진행해 주어야 한다. KMP 알고리즘은 패턴이 일치하지 않을 때 패턴의 일부가 이미 일치했다는 정보를 활용하여 검색을 최적화하는 방법으로 이전에 일치한 접두사와 접미사를 활용하여 비교 지점을 조정하는데 접두사와 접미사 중 가장 긴 길이를 저장하는 배열이 LPS 배열이다.

    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();

        StringBuilder sb = new StringBuilder();
        sb.append("I");

        for (int i = 0; i < n; i++) {
            sb.append("OI");
        }
        
        int count = countPattern(s, sb.toString());

        System.out.println(count);
        br.close();
    }

초반 패턴을 구해주는 과정은 이전과 동일하다.

    private static int[] makeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];  
        int length = 0; 
        int i = 1;

우선 LPS 배열을 만드는 메서드 부터 보면 LPS 배열은 패턴과 동일한 길이를 가진 배열로 선언해 준다. length는 이전 lps의 길이를 나타낼 변수이고 LPS 배열의 0번 인덱스는 무조건 0으로 1번 인덱스부터 초기화를 진행한다.

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;  
                lps[i] = length;  
                i++; 
            } else {
                if (length != 0) {
                    length = lps[length - 1]; 
                } else {
                    lps[i] = 0;  
                    i++;  
                }
            }
        }

        return lps;

패턴을 순회하며 값을 저장하게 되는데 패턴의 현재 인덱스 문자와 length 값의 문자와 같다면 lps 배열의 현재 인덱스 값에 length 값을 증가시켜 저장하고 다음 문자로 넘어간다. 그리고 현재 인덱스 문자와 length 값의 문자가 다르다면 현재 값이 0이 아닐 경우 LPS 배열을 참조해서 값을 줄이고 현재 값이 0이라면 현재 인덱스 문자의 lps 값을 0으로 초기화 한 뒤 다음 문자로 넘어간다. 코드만 봐서는 어떤 내용인지 잘 이해하기가 힘든데 예시를 통해 구해지는 과정을 보면 좀 더 이해하기가 편할 것이다.

인덱스	문자	length	값
0	A	0	초기화, LPS[0] = 0
1	A (B)	0	A와 B 불일치, LPS[1] = 0
2	AB (A)	1	A와 A 일치, length 증가 (1), LPS[2] = 1
3	ABA (B)	2	AB와 AB 일치, length 증가 (2), LPS[3] = 2
4	ABAB (A)	3	ABA와 ABA 일치, length 증가 (3), LPS[4] = 3
5	ABABA (C)	4	ABAB와 C 불일치, length를 LPS[3] = 2로 갱신
5	ABABA (C)	2	ABA와 C 불일치, length를 LPS[1] = 0으로 갱신
5	ABABA (C)	0	ABAB와 C 불일치, LPS[5] = 0
최종 LPS 배열: [0, 0, 1, 2, 3, 0]

동작 과정을 표로 나타낸 것이다. length 값은 접두사와 접미사가 일치하는 길이를 나타내는 것으로 ABA에서 접두사 A와 접미사 B가 일치하기 때문에 현재 2번 인덱스의 값이 1로 저장되어 A라는 문자가 겹칠 때 저장된 인덱스 1 값을 통해 1번 인덱스인 B부터 검색을 다시 진행할 수 있는 것이다.

자세한 동작은 코드와 함께 보자

    public static int countPattern(String text, String pattern) {
        int[] lps = makeLPSArray(pattern);

        int count = 0;  
        int i = 0;      
        int j = 0;

KMP 알고리즘 메서드로 앞에 만들어둔 메서드를 통해 LPS 배열을 만들어 가져온다. 그리고 패턴 등장 횟수를 저장할 변수와 문자열 인덱스 i와 패턴용 인덱스 j를 선언했다.

	 while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;  
                j++;  
            }

문자열을 순회하며 현재 패턴 인덱스의 문자와 문자열 인덱스에 해당하는 문자가 같다면 각각 인덱스 값을 올린다.

 	    if (j == pattern.length()) {
                count++;  
                j = lps[j - 1];              
            }

패턴 인덱스가 패턴의 길이에 도달해 일치하는 패턴을 찾았다면 count 값을 증가시켜 주고 패턴의 인덱스를 변경해 주는데 배열의 마지막 값으로 인덱스를 변경해 주는데 이 문제에 나오는 IOI에 대해 보면 현재 패턴이 끝나면서 나온 문자가 I이고 다시 패턴이 시작하며 나오는 문자 또한 I이기 때문에 I를 건너뛴 O부터 검색을 진행하기 위한 인덱스 설정이라고 보면 된다.

	    else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];  
                } else {
                    i++;  
                }
            }
        }

        return count;

만약 현재 인덱스의 패턴 문자와 문자열 문자가 다를 경우인데 패턴 인덱스가 0이 아닐 경우에 lps 배열에 들어있는 인덱스 값들을 통해 패턴 중간부터 다시 매칭을 이어 나갈 수 있는지 계속해서 검사를 하게 된다. 그렇게 만약 패턴 중간부터 다시 매칭을 이러 나갈 수 없게 된다면 결국 패턴 인덱스는 0이 되고 문자열은 다음으로 넘어가 처음부터 다시 매칭을 시작하게 된다. 위에 ABABAC를 예로 보면 ABABAC의 마지막인 C가 문자열에 문자 D와 비교가 된다면 C != D 이기 때문에 lps에 저장된 3번 인덱스로 돌아가 D와 비교를 하게 된다. 만약에 비교했던 값이 D가 아니라 B였다면 다시 ABAB가 매칭된 순간부터 검색을 이어나갈 수 있기 때문인 것이다.

전체 코드

import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

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());
        int m = Integer.parseInt(br.readLine());

        String s = br.readLine();

        StringBuilder sb = new StringBuilder();
        sb.append("I");

        for (int i = 0; i < n; i++) {
            sb.append("OI");
        }

        int count = countPattern(s, sb.toString());
        System.out.println(count);
    }

    public static int countPattern(String text, String pattern) {
        int[] lps = makeLPSArray(pattern);
        int count = 0;
        int i = 0; 
        int j = 0; 

        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == pattern.length()) {
                count++;
                j = lps[j - 1]; 
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return count;
    }

    private static int[] makeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0; 
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }
}

728x90

'알고리즘 > 코딩테스트-백준' 카테고리의 다른 글

[백준] 숨바꼭질 JAVA (1)	2024.09.25
[백준] 좌표 압축 JAVA (0)	2024.09.24
[백준] 회의실 배정 JAVA (1)	2024.09.14
[백준] 이중 우선수위 큐 & [Programmers] 이중 우선순위 큐 (0)	2024.09.12
[백준] Z JAVA (2)	2024.09.11

현재글[백준] IOIOI JAVA

kwang2134 님의 블로그

개발/ 알고리즘/깃허브 https://github.com/kwang2134

코딩테스트, blind75, 오블완, neetcode, Java, programmers, 웹 개발, BFS, spring, grind75, 프로그래머스, DP, 백준, dfs, 스프링, spring data JPA, 자바, leetcode, 알고리즘, 티스토리챌린지,

Today :
Yesterday :

kwang2134 님의 블로그