[BOJ] 5525 IOIOI

https://www.acmicpc.net/problem/5525

5525번: IOIOI

 

 

1/ 조건

1) P_N은 I로 시작하여 I와 O가 번갈아가며 나오며 2N+1의 길이를 갖는 문자열이다.

2) I와 O로만 이루어진 문자열 S와 정수 N이 이주어졌을 때, S 안에 P_N이 몇 개 포함되어 있는지 구해야 한다.

 

2/ 설계

시간 제한에 대한 감이 오지 않았다. 일단 순회를 반복하는 방식으로  풀어보고자 했다.

구체적으로 말하자면 문자열을 처음부터 순회하되, I를 만나면 그 I를 첫 번째 원소로 하는 P_N이 있는지 여부를 확인하는 알고리즘이다.

 

3/ 구현

n = int(input())
m = int(input())
s = input()

lst = 'IO'
flag = 0
idx = 0
cnt = 0
while idx < m:
    if s[idx] == 'I':
        for i in range(2*n+1):
            # 문자열의 끝에 도달했을 때 조건 처리
            if idx+i == m:
                if i == 2*n and s[idx+i] == 'I':
                    cnt += 1
                flag = 1
                break
            # 만약 원하는 문자가 나타나지 않았을 경우 그 범위까지는 P_N이 없다는 뜻
            if s[idx+i] != lst[i%2]:
                idx += i
                break
        else:
            cnt += 1
            # P_N에는 P_K(단, K < N)가 2칸마다 등장하므로 
            idx += 2
        if flag:
            break
    else:
        idx += 1

print(cnt)

 

처음 생각한 것과 다르게 코드가 길었다. 여기서 감(ㅋㅋ)이 안 좋았다.

 

 

4/ 결과

시간 초과.

 

 

5/ 돌아보기

냉수 마시고 정신을 좀 차리니 P_500000에서 P_250000을 찾는 경우와 그 근처에서 시간이 많이 소요될 수 있다는 것을 느꼈다. 연산을 크게 줄이기 위해서는 재방문하는 일이 없어야 한다고 생각했고, 타뷸레이션 하듯 모든 방문의 결과를 기록한 뒤 그 위에서 한 번에 P_N을 찾아내는 방법이 가능할 것 같았다.

 

 

6/ 재설계

'현재 인덱스를 마지막 원소로 하는 P_K가 존재하는가, 존재한다면 그 K는 얼마인가'라는 물음을 구현하고자 했다. 이러한 기록은 한 번의 순회로 형성 가능하며 이후에 그 기록을 다시 한 번 순회하면서 I로 끝나되 K >= N인 기록의 갯수를 세면 되겠다고 생각했다. 단 2번의 순회만 있으므로 시간 초과는 나지 않을 거라고 판단.

 

 

7/ 구현

n = int(input())
m = int(input())
s = 'O'+input()     # i = 0일 때의 예외 처리를 피하기 위해서 문자열 앞에 O를 붙여주었다
record = [0]*(m+1)

for i in range(1, m+1):
    # 이전 문자와 다르면 무조건 P_N의 부분문자열이다
    if s[i-1] != s[i]:
        record[i] = record[i-1]+1
    # II일 경우
    elif s[i] == 'I':
        record[i] = 1
    # OO일 경우
    else:
        record[i] = 0

cnt = 0
# 2n+1까지의 인덱스에서는 무조건 record가 0이므로
for i in range(2*n+1, m+1):
    if record[i] >= 2*n+1 and s[i] == 'I':
        cnt += 1

print(cnt)

 

 

8/ 결과

야호!

 

 

9/ 한 번 더?

다른 분들의 제출을 보는데 나보다 메모리도 덜 쓰고 시간도 빠른 풀이가 있어서 봤다. 훑어보니 list를 사용하지 않고 변수 하나로 그 역할을 처리하신 풀이였다. 바로 다시 풀어보기로 했다.

 

n = int(input())
m = int(input())
s = input()

end = 2  # 패턴이 확인된 범위
answer = 0
pattern_cnt = 0     # 현재까지의 패턴 갯수
for i in range(m-2):
    if end < i:
        pattern_cnt = 0         # 패턴이 확인된 범위를 벗어나면 현재까지의 패턴 갯수를 초기화한다
    if s[i:i+3] == 'IOI':       # 패턴이 발견되면
        end = i+2               # 패턴의 확인된 범위를 설정하고
        pattern_cnt += 1        # 현재까지의 패턴 갯수를 1 늘려준다
        if pattern_cnt >= n:    # 만약 패턴 갯수가 목표 이상일 경우
            answer += 1         # 정답을 1 늘린다

print(answer)

훨씬 더 최적화된 풀이다!

 

 

9/ 후기

1) 2월 말부터의 화두는 '정해진 풀이를 얼마나 빠르게 떠올리고 구현할 수 있는가?'였다. 내면에 도구가 어느 정도 갖춰졌다고 생각해서 그걸 좀 더 다지는 기간이 필요하다고 판단한 것. 그래서 도전적인 문제를 풀기보다 어렵지 않은 문제를 풀었고, 풀이를 개선하기보다 다른 문제를 하나 더 풀려고 해왔다.

그 기간은 필요한 게 맞았다. 확실히 내면의 난잡했던 부분들이 꽤 가라앉았다는 걸 느낀다. 유니온-파인드나 다익스트라, 동적계획법 등등 아직 훈련해야 할 부분이 많이 남아 있긴 하지만.

요즘 교육장에서 웹을 배우기도 하고 체력이 많이 떨어지기도 해서 알고리즘 문제 해결에 대해 조금 소홀해진 느낌이다. 도전적인 문제를 풀지도 않고 그렇다고 문제를 많이 푼 것도 아닌, 그저 기록을 이어가기 위해 수준 미만의 문제를 해결하는 나날들. 나쁘다는 건 아니다. 기록을 이어가는 것만으로 충분히 자랑스럽다.

그래도 조금 더 도전적이면 더욱 좋겠지!

 

2) 풀이의 우아함. 처음에는 9번 항목의 풀이를 두고 '우아하다'는 표현을 썼다가 고쳤는데, 이런 사후에 훈련되는 미적 감각에 대해서 다시금 생각하게 되었다. 어떠한 군더더기가 없어 보다 효율적인 대상을 가리키는 표현으로써의 우아함. 소위 말하는 '아름다운 수식'과 같은 결의 표현이 아닌가 싶다. 그러한 표현이 나쁘다는 건 아닌데, 이런 감각에 대해 공감하지 못하는 사람들은 자신에게 프로그래밍을 좋아할 자격이 없다고 자책할지도 모른다는 생각에 표현을 수정했다. 쓸데없는 감상인가? 그럴지도.

 

3) 나는 문제를 풀 때 분해능을 최대한으로 높이려 드는 것 같다. '이 방식이라면 틀릴 수 없다' 같은 느낌이라고 해야 하나? 하지만 분해능이 높을수록 자원을 많이 소모하고, 따라서 우리는 최소한의 분해능으로만 문제에 접근하는 것이 옳다. 마치 투 포인터를 쓸 수 있는 문제에서는 이중 순회보다 투 포인터를 쓰는 게 옳은 것처럼.

이번 문제에서도 그렇다. 타뷸레이션과 비슷한 접근을 떠올리는 것까진 정말 잘했는데, 그걸 변수 하나로 대체할 수 있다는 사실까지는 도달하지 못했다. 아직 '분해능을 더 낮출 수 있는가?'라는 질문이 내 마음속 체크리스트에 자리잡지 못한 느낌이다.

변명을 하자면, 그것을 가늠하는 게 힘들다. 풀이를 더 컴팩트하게 만들 수 있는가? 왜 이것보다는 분해능을 더 낮출 수 없는가? 어디가 경계선인가? …모든 것은 감이다. 보다 정확히 말하자면 구조화되어 내면에 자리잡은 '전문성'이라는 이름의 휴리스틱들. 기본적으로는 문제의 양이 요구되고, 비슷하지만 다른 문제를 비교하며 고민하는 시간 또한 필요하다.

이러한 방식은 알고리즘 문제 해결뿐만이 아니라 임의의 전문성에 대해서도 똑같이 적용된다고 본다. 그것이 물리학이 되었든, 소설이 되었든, 프로그래밍 실무가 되었든. 이것을 의식하지 않고도 해내는 사람들이 있지만, 나는 아니다. 더욱 의식적이고 싶다.