[99클럽 4기 코테 스터디 TIL 17일차] 기술 연계마스터 임스 (feat. 스택, 스택에 넣었다 빼기)

1) 문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

5
S12K2

예제 출력 1 복사

4

 1$1$, 2$2$, S$S$ - K$K$, 2$2$로 스킬을 성공적으로 총 4번 사용했다.

예제 입력 2 복사

4
1LKR

예제 출력 2 복사

1

 1$1$로 스킬을 성공적으로 1번 사용했다.

 L$L$ - R$R$로 스킬이 사용이 가능하나, 중간에 연계되어 사용돼야 하는 K$K$가 있어 성공적으로 사용이 불가능하다.

예제 입력 3 복사

4
SSKK

예제 출력 3 복사

2

 S$S$를 2번 연속 사용하고, K$K$를 2번 사용하여 스킬을 성공적으로 2번 사용했다.

 

 

 

 

 

2) 내가 구현한 코드

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        String str = br.readLine();
        Stack<String> LR_stack = new Stack<>();
        Stack<String> SK_stack = new Stack<>();

        for(int i=0; i<N; i++){
            if(str.charAt(i) == 'L'){
                LR_stack.push("L"); //넣기
            }else if(str.charAt(i) == 'R'){
                if(LR_stack.isEmpty()) break;
                LR_stack.pop(); //빼기
                answer++;
            }else if(str.charAt(i) == 'S'){
                SK_stack.push("S"); //넣기
            }else if(str.charAt(i) == 'K'){
                if(SK_stack.isEmpty()) break;
                SK_stack.pop(); //빼기
                answer++;
            }else{
                answer++;
            }
        }
        bw.write(""+answer);
        bw.flush();
        br.close();
        bw.close();

    }
}

 

 

3) 추가 문제

미들러 - 밤양갱

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

챌린저 - 작업

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