[BOJ-#25497] 기술 연계마스터 임스

문제

문제 링크
임스는 연계 기술을 사용하는 게임을 플레이 중에 있다. 연계 기술은 사전 기술과 본 기술의 두 개의 개별 기술을 순서대로 사용해야만 정상적으로 사용 가능한 기술을 말한다.

하나의 사전 기술은 하나의 본 기술과만 연계해서 사용할 수 있으며, 연계할 사전 기술 없이 본 기술을 사용했을 경우에는 게임의 스크립트가 꼬여서 이후 사용하는 기술들이 정상적으로 발동되지 않는다. 그렇지만 반드시 사전 기술을 사용한 직후에 본 기술을 사용할 필요는 없으며, 중간에 다른 기술을 사용하여도 연계는 정상적으로 이루어진다.

임스가 사용할 수 있는 기술에는 $1$~$9$, $L$, $R$, $S$, $K$가 있다. $1$~$9$는 연계 없이 사용할 수 있는 기술이고, $L$은 $R$의 사전 기술, $S$은 $K$의 사전 기술이다.

임스가 정해진 순서대로 $N$개의 기술을 사용할 때, 기술이 몇 번이나 정상적으로 발동하는지를 구해보자.

단, 연계 기술은 사전 기술과 본 기술 모두 정상적으로 발동되었을 때만 하나의 기술이 발동된 것으로 친다.

입력

첫 번째 줄에는 총 기술 사용 횟수 $N$이 주어진다. ($1 \le N \le 200\,000$)

두 번째 줄에는 임스가 사용할 $N$개의 기술이 공백 없이 주어진다.

출력

임스가 정상적으로 기술을 사용한 총 횟수를 출력한다.

Code

Github 링크

import sys

input = sys.stdin.readline

test_case = int(input())

skill = list(input().rstrip())

LR = []
SK = []
cnt = 0

for i in skill :
    if i == 'S' :
        SK.extend(i)
    elif i == 'K' :
        if not SK :
            break
        else :
            SK.pop()
            cnt += 1

    elif i == 'L' :
        LR.extend(i)
    elif i == 'R' :
        if not LR :
            break
        else :
            LR.pop()
            cnt += 1
    else :
        cnt += 1

print(cnt)

코드 설명

import sys

input = sys.stdin.readline

test_case = int(input())

skill = list(input().rstrip())

LR = []
SK = []
cnt = 0

빠른 입력을 받을 수 있도록 input을 선언하고 test case의 개수를 받는다. input을 한 글자씩 리스트로 받고, LR 스킬과 SK 스킬 사용 횟수를 저장해 둘 스택을 두 개 만든다. 기술이 실행된 횟수를 세기 위해 카운트도 0으로 하나 받는다.

for i in skill :
    if i == 'S' :
        SK.extend(i)
    elif i == 'K' :
        if not SK :
            break
        else :
            SK.pop()
            cnt += 1

    elif i == 'L' :
        LR.extend(i)
    elif i == 'R' :
        if not LR :
            break
        else :
            LR.pop()
            cnt += 1
    else :
        cnt += 1

print(cnt)

skill으로 for문을 돌린다. 만약 i가 S일 경우 무조건 SK 스택에 추가한다. K일 경우, SK 스택이 비어있을 경우 무조건 break하고 스택이 비어있지 않을 경우 S를 pop한 후에 횟수를 하나 카운트한다. L과 R도 같은 방식으로 진행한다. SKLR 외에 모든 기술은 사전 기술이 필요없기 때문에 무조건 한 개 카운트한다.

리뷰

velog를 귀찮아서 미루다가 일요일 저녁에 썼는데 어쩌다가 저렇게 짠 코드인지 기억이 잘 안 나서 설명할 때 애먹었다... 앞으로는 풀고 바로 써야지. 그리고 사실 test_case는 사용하지 않는데... 입력값에 있길래 하나 받았다. 실버5 문제라 준 듯? 처음에 문제를 잘못 이해해서 틀렸습니다가 꽤 많이 떴는데 어떻게 잘못 이해했던 건지 기억이 잘 안 난다... 아마 LKR 이런 식으로 나왔을 때 처리를 다르게 했던 것 같다. 그때 잘못 이해해서 코드가 쫌 더러워졌는데 앞으로는 코드 깔끔하게 짜는 연습도 해야겠다. 그리고 시간복잡도를 위해서 append가 아니라 extend를 사용해봤는데 둘의 시간복잡도가 정확하게 어떤 차이인지도 다음에 공부해봐야겠다.