[Java] 백준(실버-1) 5525번 - IOIOI
문제 풀이Permalink
이번 문제는 문자열 문제로 문제의 서브테스크를 모두 충족해야 100점을 받을 수 있다.
아이디어 도출Permalink
처음에는 단순히 이중 for문으로 Pn 만큼 추가로 순회하며 IOI를 체크했지만, 시간초과가 발생하였다. 그래서 시간복잡도를 O(n)으로 줄이기 위해 DP 테이블을 이용하였다.
문제 풀이를 위한 아이디어는 다음과 같다.
- Pn에 해당하는 문자열인지 확인하기 위해 S의 2번째 원소부터 순회를 시작한다.
- S를 순회하면서, 현재 위치까지 Pn만큼의 문자열을 만들어 Pn과 같다면, DP 테이블 위치에 1씩 카운트를 누적하도록 갱신한다.
- 이후, DP 테이블의 현재값이 N보다 크거나 같다면, Pn이 포함되어 있는 것이기에 카운트를 1씩 증가시킨다.
Pn이 S에 포함되어 있는지를 DP 테이블의 값을 보고 판단하기에 시간복잡도를 O(n)으로 줄일 수 있었다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드Permalink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
String S = br.readLine();
// M만큼의 길이를 가지는 DP 테이블 선언
int[] D = new int[M];
// 결과 갯수를 담을 변수
int result = 0;
// M의 최소 길이는 IOI인 3부터 시작하기에
// 2번째 위치부터 Pn이 포함되는지를 확인하기 위해 순회한다.
for(int i=2; i<M; i++) {
// 현재 위치까지 Pn(IOI)만큼 길이가 3인 문자열을 만든다.
String temp = S.substring(i-2, i+1);
// 만든 temp가 "IOI"와 같다면 DP 테이블에 카운트를 1씩 갱신한다.
if(temp.equals("IOI")) {
D[i] = D[i-2] + 1;
}
// DP 테이블의 값이 N보다 크거나 같다면 Pn이 포함되어 있는 것이기에 result를 1씩 증가시킨다.
if(D[i] >= N) {
result++;
}
}
bw.write(result+"\n");
}
}
}
출처Permalink
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.