포스트

IOIOI(5525)

게시 업데이트
By Kim Jung Wook 8 분읽는 시간

IOIOI(5525)

1차 풀이과정

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

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    String s = br.readLine();
    char[] ch = s.toCharArray();
    
    int res = 0;
    for(int i = 0; i < m - 2*n; i++) {
      
      boolean flag = true;

      if(ch[i] == 'I' && ch[i+1] == 'O' && ch[i+2] == 'I') {

        boolean pair = true; // true면 홀, flase 짝
        for(int j = 1; j <= 2*n; j++) {
          if(!flag) break;
          if(pair) {
            if(ch[i+j] == 'O') flag = true;
            else flag = false;
            pair = !pair;
          } else {
            if(ch[i+j] == 'I') flag = true;
            else flag = false;
            pair = !pair;
          }
        }
        
        if(flag) res++;
      }
    }
    
    sb.append(res);

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}
  1. char 배열을 순회하며, I가 나올경우 n에 따른 idx를 더하여 순서대로 O와 I가 나오는지 체크하였다.
  2. I 이후에 O가 나오는지 체크, O 다음에 I가 나오는지 체크
  • 50점 성공. 메모리 14452 KB, 시간 : 148 ms
  • 시간초과로 100점을 못 맞았다.

2차 시도

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

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    String s = br.readLine();
    char[] ch = s.toCharArray();
    
    boolean[] ioi = new boolean[m];
    
    int idx = 0;
    for(int i = 0; i < ch.length - 2; i++) {
      if(ch[i] == 'I') {
        if(ch[i+1] == 'O' && ch[i+2] == 'I') ioi[idx] = true;
        idx++;
      }
    }
    
    int res = 0;
    for(int i = 0; i <= idx - (n-1); i++) {
      if(ioi[i]) {
        boolean flag = true;
        for(int j = 1; j < n; j++) {
          if(!flag) break;
          if(!ioi[i+j]) flag = false;
        }
        if(flag) res++;
      }
    }
    
    sb.append(res);

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
}
  1. boolean 배열을 하나 만들었고, char 배열 순회 시 I를 만나면 뒤에 O와 I가 순서대로 오는지 체크하여 true값을 넣었다.
  2. 그 후 n의 값만큼 true가 연속되는지 안되는지 갯수를 파악하였다.
  • 50점 성공. 메모리 14320 KB, 시간 : 140 ms
  • 시간초과로 100점을 못 맞았다.

최종 결과

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

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    String s = br.readLine();
    char[] ch = s.toCharArray();
    int[] ans = new int[m];
    
    int idx = 1;
    int res = 0;
    for(int i = 0; i < ch.length - 2; i++) {
      if(ch[i] == 'I') {
        if(ch[i+1] == 'O' && ch[i+2] == 'I') ans[idx] = ans[idx-1] + 1;
        else ans[idx] = 0;
        
        if(ans[idx] >= n) res++;
        
        idx++;
      }
    }
    
    sb.append(res);

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
}
  1. 계속되는 시간초과로 for문을 줄이고자 하였다.
  2. 그럼 for문을 한 번 돌때, IOI의 연속성을 기록을 해야 한다고 생각했다.
  3. 왜냐하면 IOIOIOI 라고 한다면, n=2인 경우 첫번째 I로 시작되어 두번째 세번째 I로 끝나는 경우와 두번째 I로 시작되어 세번째 네번째로 끝나는 경우 2개의 답이 나와야한다
  4. 여기서 문제는 두번째 I의 경우 첫번째 I인 경우만 따지고 넘어가게 되면 정답은 1로 나올 것이기 때문이다.
  5. I를 만날 때 메모라이즈 기법을 사용해보려고 하였다.
  6. 메모라이즈를 위한 배열하나를 만들어주고, 이를 메모리배열이라고 한다.
  7. I를 만나면 뒤에 O와 I가 순서에 맞게 나오는지 판단한다.
  8. 6의 내용이 true라면 메모리배열의 idx값에 1을 넣어준다. false라면 해당 idx의 값에는 0으로 초기화한다. 즉, IOI가 연속되지 않고 끊겼다는 것이다. (IOIIO..)
  9. char 배열 순회를 이어간다. 또 I를 만나면 이전 메모리배열의 I의 값에 +1을 해준다.
  10. 먄약 또 만난 I가 이전 I와 연속된다면 (IOIOI..)라면 첫번째 I는 1, 두번째 I는 2가 되는 것이다.
  11. 만약 다른 경우 IOIIOI 라면, 메모리배열에서 처음 I의 값은 1, 두번째 I의 값은 0, 세번째 I의 값이 다시 1이 되는 것이다.
  12. 이렇게 메모리 배열에 IOI가 연속되고 있는지 안되고 있는지를 카운트하며 주어진 n의 값에 따라 정답을 카운트하였다.
1
2
3

- 성공
- 메모리 : 26012 KB
- 시간 : 284 ms

보안점

  1. 문제를 쉽게 접근하려고 for문을 여러번 썼다. 개인적인 생각으로 직관성은 좋다고 생각한다.
  2. 왜냐하면 연산이 없이 직관적으로 처리를 했다고 생각하기 때문이다.
  3. 하지만 연산을 추가하고 한다면 응답시간을 더 줄일 수 있다는 것을 새삼 느끼게 되었다
  4. 이 문제야 정답이 있으니 for문을 줄이려고 노력했지만, 평소에 내가 짠 코드가 최선의 코드인지 응답시간을 더 줄일 수 있는지 고민해봐야 하겠다.
  5. 백준 문제를 풀고 다른 사람의 응답시간과 메모리를 비교해보기는 하지만, 알고리즘 문제가 아닌 실무에서 코드는 정답이 없기 때문에 지속해서 들여다보고 고민해보고
  6. 리팩토링 하는 것이 중요하다고 생각되어진다.
알고리즘, 문제
알고리즘문제