[ BOJ ] 25497 : 기술 연계마스터 임스 ( SILVER 5 ) / C, Python

문제

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

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

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

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

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

입력

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

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

출력

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

풀이 과정

1. 하나의 사전 기술은 하나의 본 기술과만 연계해서 사용할 수 있으며, 중간에 다른 기술을 사용하여도 연계는 정상적으로 이루어진다.

2. 연계할 사전 기술 없이 본 기술을 사용했을 경우에는 이후 사용하는 기술들이 정상적으로 발동되지 않는다. -> R 과 K 가, 각각 L과 S 가 이전에 사용되지 않은 채로 등장하면 탐색을 종료한다.

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

 

이 세 가지를 유의하여 구현한다. 사전 기술인 L 과 S 를 스택 형태로 구현하면 사전 기술 - 본 기술 처리를 쉽게 할 수 있다.

C

#include <stdio.h>
#include <string.h>

char str[200005];
int main(void) {
    int n;
    scanf("%d", &n);
    getchar();
    scanf("%s", str);

    int stackL = 0;
    int stackS = 0;
    int count = 0;
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == 'L') stackL += 1;
        else if (str[i] == 'S') stackS += 1;
        else if (str[i] == 'R') {
            if (stackL == 0) break;
            else {
                stackL -= 1;
                count += 1;
            }
        }
        else if (str[i] == 'K') {
            if (stackS == 0) break;
            else {
                stackS -= 1;
                count += 1;
            }
        }
        else count += 1;
    }
    printf("%d", count);

    return 0;
}

Python

import sys
input = sys.stdin.readline

n = int(input().rstrip())
string = input().rstrip()

lstack = 0
sstack = 0
result = 0
error = 0
for s in string:
    if error == 1: continue

    if s == 'L': lstack += 1
    elif s == 'S': sstack += 1
    elif s == 'R':
        if lstack > 0:
            lstack -= 1
            result += 1
        else:
            error = 1
    elif s == 'K':
        if sstack > 0:
            sstack -= 1
            result += 1
        else:
            error = 1
    else: result += 1

print(result)