BOJ 2929 - 머신 코드

문제

BOJ 2929 - 머신 코드

머신 코드는 대문자로 시작하는 명령어들로 구성된 문자열이다. 각 명령어(마지막 제외)는 길이가 4의 배수여야 하며, 부족한 만큼 NOP를 채워야 한다. 필요한 NOP의 총 개수를 구하라.

입력

대문자와 소문자로 이루어진 문자열이 주어진다. 대문자는 명령어의 시작을 나타낸다.

출력

마지막 명령어를 제외한 각 명령어의 길이를 4의 배수로 맞추기 위해 필요한 NOP의 총 개수를 출력한다.

예제

풀이

대문자를 기준으로 문자열을 분리한 뒤, 마지막 명령어를 제외하고 각 명령어의 길이를 4의 배수로 올리는 데 필요한 패딩을 계산한다.

1. 정규식 (?=[A-Z])으로 대문자 앞에서 문자열을 분리한다
2. 첫 번째 빈 문자열과 마지막 명령어를 제외한 나머지를 순회한다
3. 각 명령어의 길이를 4로 나눈 나머지가 0이 아니면 4 - 나머지만큼 NOP가 필요하다
4. 필요한 NOP 개수를 모두 합산하여 출력한다

핵심 아이디어: 마지막 명령어는 패딩이 필요 없으므로 제외하고, 나머지 명령어에 대해서만 4의 배수 정렬을 수행한다.

코드

import re
 
t = input()
p = re.split("(?=[A-Z])", t)
 
cnt = 0
for i in range(1, len(p) - 1):
    a = len(p[i]) % 4
    if a != 0:
        cnt += 4 - a
print(cnt)

복잡도

• 시간: O(N) — 문자열 길이만큼 순회
• 공간: O(N) — 분리된 명령어 리스트 저장