[백준] No.5525 IOIOI 01

 

5525번: IOIOI

IOIOI...IOIOI를 나타내는 Pn이 주어진다.

이때 I와 O로만 이루어진 어떤 문자열(S)을 입력받으면, 그 안에 Pn이 몇 개 있냐?하는 문제이다.

만약 Pn이 IOI이고, S가 IOIOI라면 2개를 세줘야 한다.

S가 IOIOOOIOIOI라면 처음에 하나, 뒤에 2개해서 총 3개를 세줘야 한다.

 

처음에는 단순하게 생각했다.

Pn의 길이를 입력받으면 그에 대응하는 Pn 문자열을 생성한다.

그 다음 문자열 슬라이싱을 사용해 S와 하나하나 비교하는 방법으로 카운팅 해준다.

쉽게 말하면 브루트 포스 방법으로 문제를 접근했다.

 

# ---------- Function ----------
def makePn(n: int) -> str:
    length = 2 * n + 1
    Pn = list("I" * length)
    
    for i in range(length):
        if i % 2 != 0: Pn[i] = "O"
    
    return ''.join(Pn), length

우선 Pn에 해당하는 문자열을 만들어주는 함수를 작성했다.

Pn 문자열의 특징은 길이가 언제나 홀수라는 거다. 그리고 I가 언제나 O보다 하나 많다.

그럼 Pn은 N과 N+1이라고 할 수 있다. Pn의 길이 입력은 O의 개수와 동일하다.

또한, 언제나 I로 시작하여 I로 끝난다. 즉 인덱스가 짝수라면 I, 홀수라면 O라는 말이다.

 

이를 바탕으로 2n+1 길이만큼의 I를 생성해준다.

그리고 홀수인 부분만 O로 바꾼 뒤 join 함수를 사용하여 문자열을 return한다.

이때 나중에 사용해주기 위해 Pn의 길이도 같이 return한다. 

 └ 정확하게는, 길이를 다시 계산하기보다, 한 번 계산한 것을 다시 이용하려고 같이 return했다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Main ----------
N = int(input())
length = int(input())
S = input().rstrip()

compareText, compareLength = makePn(N)
count = 0

for i in range(length - compareLength + 1):
    if S[i:i+compareLength] == compareText:
        count += 1
        
print(count)

위에서 생성한 Pn과 Pn의 길이를 각각 compareText, compareLength에 담아준다.

그리고 반복문으로 입력받은 S에서 compareLength만큼 슬라이싱한다.

그리고 compareText와 동일하다면 1씩 세주면서 정답을 확인한다.

 

Python3으로 처음 제출했을 때 Subtask 절반만 맞았다.

혹시 몰라 PyPy3로도 제출해보니 똑같이 반점. 전체적인 방향성을 잘못 잡았다는 생각이 든다.

시간이 어디서 가장 오래 걸릴까 생각해보았다.

Pn을 생성할 때도 시간이 걸리겠지만, 슬라이싱한 후 일일이 비교하는 게 오래 걸리리라 생각했다.

그래서 전체 길이를 구한 뒤, 빼는 방법을 생각해냈다.

 

구상 단계라 변수를 조금 마구잡이로 작성했었다. 구상 중에도 변수를 통일하면 나중에 읽을 때 더 좋을 것 같다.

IOIOI에 해당하는 어떤 문자열이 있다고 해보자. 그리고 이 문자열의 길이는 L이다.

여기서 N에 따라서 몇 개의 IOI가 들어갈지 수학적으로 딱 정의할 수 있을 것 같았다.

N이 1부터 3일 때까지 작성해놓고 비교해보니, 시작점의 개수를 세는 것과 같았다.

 

위의 그림을 예시로 들면 L은 IOIOIOIOIOI로 I가 6개 나오는 문자열이다.

즉 시작할 수 있는 위치가 6개 있다는 거다.

N이 1일 때, IOI가 되고 시작 가능한 I의 위치는 1개이다. 뒤에 있는 I는 시작할 수 없는 I이다.

N이 2일 때, IOIOI가 되고, 시작할 수 없는(뒤에 있는) I는 2개이다.

즉, L에서 I의 문자열을 세고, 시작할 수 없는 문자열을 빼면 된다.

(마치 range에서 범위를 지정해줄 때, 문자열 길이만큼 빼주는 느낌이다.)

 

문자열 S가 있을 때, 맨 처음에 존재하는 I를 빼면 나머지 O와 I의 개수(N)가 같아진다. 

그리고 L에서 I의 개수는 n + (n+1)에서 n+1에 해당한다.

여기서 (L+1) // 2 - N이라는 식 하나를 얻을 수 있었다.

 

문제를 풀다가 의문이 들었다.

L의 길이를 구해서 계산하는 식은 구했는데, 그래서 L의 길이를 어떻게 구하지?

어디를 시작점으로 잡고 어디를 종점으로 잡아야 가능하지? 조건문은 어떻게 작성해야 하지?

 

우선은 기준점이 O인지 I인지 신경쓰지 말고 탐색을 시작했다.

그러면 위처럼 O시작O종료, O시작I종료, I시작O종료, I시작I종료라는 4가지 경우의 수만 나온다.

결국 그럼 맨 처음 문자열(START 변수)과 맨 마지막 문자열(END 변수)에서 O를 세면 되는 문제였다.

의사 코드를 그려보고 직접 코드 작성을 나섰다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Main ----------
N = int(input())
S_length = int(input())
S = list(input().rstrip())

우선 빠른 입력을 위한 sys 호출과, 조건들을 입력받았다.

 

# ---------- Main ----------
START = S[0]
Pn_length, result = 1, 0

for i in range(1, S_length):
    if S[i-1] != S[i]:
        Pn_length += 1
        
    else:
        END = S[i-1]
        
        # Calculating
        O_count = (START, END).count("O")
        Pn_length -= O_count
        
        Pn_length = (Pn_length + 1) // 2
        if Pn_length > N: result += Pn_length - N 
        
        START = S[i]
        Pn_length = 1
        
print(result)

위에서 구상한 순서들을 코드로 옮겨주었다.

우선 O인지 I인지 개의치않고 START 변수에 담아준다. 그리고 1번째 인덱스부터 끝까지 탐색한다.

이전과 다르다면(S[i-1] != S[i]), 길이를 하나 늘려준다. 이전과 같다면(else), 정해진 계산식을 진행해준다.

END 변수에 S[i-1]를 넣고, Pn_length에서 O의 개수를 빼준다. 그리고 (L+1) // 2 - N 식을 계산해준다.

두 식을 하나로 합쳐도 되지만, 가독성 때문에 우선은 나눠주었다. refactoring 때 수정하면 된다.

이때 Pn_length가 N의 길이보다 짧다면 계산할 수 없기 때문에 조건문을 추가해주었다.

계산을 다 하고나면 현재 문자열(S[i])을 START에 넣고, 길이를 초기화하고 끝이 난다.

 

분명 정답이라는 생각으로 코드를 제출했는데, 틀렸습니다가 나를 반겼다.

평소에 틀렸습니다가 나타나면 어디가 잘못 됐을지 생각을 해서 찾아내는데 이번 만큼은 없었다.

의심가는 부분이 작성할 때도 없었고, 시간 초과가 발생하리라는 생각도 들지 않았다.

그래서 직접 마구잡이 입력을 하면서 테스트를 해보았고, 한 가지 이상한 반례를 찾았다.

 

입력한 문자열 S를 한 번 코드에 따라서 나누어보겠다.

IO_OI_IOIOIOIOIOIOIOIO_O_OIOIOI_IOIOIOIOIOIOIO

 

N으로 2를 입력해주었기에 IOIOI가 몇 개 있는지 검사해야 하는 경우이다.

0 0 0 6 6 7 출력 부분에서 가장 처음 0은, 정답 변수가 초기화가 되었나 확인하는 용도로 출력했다.

즉 실질적으로 0 0 0 6 6 7이 나왔다는 이야기이다.

IO: 완성할 수 있는 부분이 없다. 0이 맞다.

OI: 완성할 수 있는 부분이 없다. 0이 맞다.

IOIOIOIOIOIOIOIO: I가 8개, N은 2 따라서 6이 맞다.

O: 완성할 수 있는 부분이 없다. 0을 더해 6이 맞다.

OIOIOI: 하나가 있다. 1을 더해 7이 맞다.

IOIOIOIOIOIOIO: ...어라? 얘는 어디갔지?

 

코드를 확인해보니 내 코드에는 if-else가 핵심이다. 그중에서도 else가 핵심이다.

위 반례처럼 IOIOIO...로 나아가서 else로 빠지지 않고 마지막에 if로 끝날 때, 마지막을 계산하지 않고 끝이 나던 것이다.

 

# ---------- Main ----------
FLAG = "N"

for i in range(1, S_length):
    if S[i-1] != S[i]:
        FLAG = "if"
        
    else:
        FLAG = "else"
        
if FLAG == "if":
    END = S[-1]
        
    # Calculating
    O_count = (START, END).count("O")
    Pn_length -= O_count
    
    Pn_length = (Pn_length + 1) // 2
    if Pn_length > N: result += Pn_length - N
        
print(result)

어떻게 해결할 수 있을까...고민하다가 더럽더라도 우선 틀린 부분이 저 곳이 맞는지 확인해보았다.

깔끔하게 쓰고 싶었는데, 생각나는 방법이 FLAG 변수밖에 없었다.

if를 들어가면 FLAG에 if를, else를 들어가면 FLAG에 else를저장한다.

그리고 만약 if문을 마지막으로 돌아서 빠져나오면(FLAG가 if라면), 같은 방법을 한 번 더 실행한다. 

 

다행히도 내가 생각한 부분만 잘못 되었고, 수정하자 정답을 맞출 수 있었다.

하지만 아무리 생각해도 코드가 너무 더럽다.

똑같은 부분을 반복문 밖에 한 번 더 쓴다? 이건 용납할 수 없다.

 

# ---------- Main ----------
N = int(input())
S_length = int(input()) + 1
S = list(input().rstrip()); S += S[-1]

# ---------- Comment ----------
# L8 int(input()) > int(input()) + 1

# Counter Example
# 2 41 IOOIIOIOIOIOIOIOIOIOOOIOIOIIOIOIOIOIOIOIO > 12(AC)

생각해보니 마지막에 else를 거치지 않고 종료를 한다는 점이 문제인 거다.

그럼 마지막에 무조건 else로 빠지게 하면 되는 것이었다.

즉 같은 문자열을 마지막에 하나 더 더해주면 해결할 수 있었다.

S += S[-1]을 해주면 어떤 문자열이 들어오든 마지막 2개는 같은 문자열이다. 즉 마지막에 else를 실행한다.

문자열 길이를 늘려주었으니 S_length에도 1을 더해주는 것을 잊지 말자.

 

같은 매커니즘으로 돌아갈 테니, 이 코드 또한 100점을 맞았다.

생각했던 것보다는 어려웠는데, 막 또 그렇게까지 어렵지는 않은? 그런 문제였다.

 

P.S.1

스터디를 하거나 요즘 타블렛을 쓸 일이 많아졌다.

타블렛 글씨 연습도 해야 하나 싶다