CodeDrive

문제:

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

•   문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있따.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력:

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력:

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이방법:

 풀 수 있는 방법은 다양하지만 시간 제한이 빡세게 걸려있던 문제였다. 따라서 일반 string에서 제공해주는 함수인 replace를 사용한다면 시간제한에 막혀서 해결하지 못할 것이다.

최대한 시간복잡도를 적게하면서 풀 수 있는 방법이 무엇일까 생각해보았는데 stack을 이용하는 것이였다. stack은 넣는 것과 빼는 것이 O(1)로 시간복잡도가 적게 발생한다. 또한 폭발 문자열만큼 stack의 끝 부분을 계속해서 확인하면 실시간(?)으로 뺄 수 있으므로 번거롭게 검토를 하는 과정또한 불필요할 것이다.

 따라서 string을 하나씩 answer라는 stack에 넣고 끝 부분이 bomb과 같아질 때마다 그 부분을 빈 리스트로 만들어줌으로써 pop과 같은 기능을 하도록 했다. 이 과정을 모두 마친 뒤에 answer라는 배열에 값이 남아있다면 이를 join으로 이어주고 비어있다면 남아있는 문자가 없는 경우이므로 FRULA를 출력하도록 하였다.

문제링크:

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

문제:

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] != Y[i]인 i의 개수이다. 예를 들어, X="jimin", Y="minji"이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

 1. A의 앞에 아무 알파벳이나 추가한다.

 2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력:

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

풀이방법:

문자열을 비교하는 단순한 알고리즘을 사용하면 된다. 알파벳을 추가할 때 앞인지 뒤인지가 중요한 것이 아니라 추가하는 행위자체가 중요한 것이다. 따라서 즉 A와 B가 얼마나 다른지가 중요한 것이다. A를 한칸씩 밀어가면서 일치하지 않을 때마다 count를 하나씩 늘리고 이 것이 최소가 되는 count을 저장해주면 된다.

문제링크:

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

문제:

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 길이 n이 매개변수로 주어질 때 , n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.

풀이 방법:

 되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12952

문제:

 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 뗴면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50,50,100,60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커(100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1<=n<=100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이 방법:

 열 단위로 끊어가면서 동적계획법을 적용하면 된다. 한 열에서 뗄 수 있는 경우의 수는 총 3가지이다.

  1 . 위, 아래 둘다 뜯지 않을 경우

  2.  위만 뜯을 경우

  3.  아래만 뜯을 경우

따라서 이 규칙대로 뜯어나가면서 최댓값을 찾아나가면 된다.

 i번째 열에서 1번의 경우로 뜯기 위해선 i-1열에는 1,2,3 모든 경우의 수가 올 수 있다. 따라서 i-1열의 값 중 최댓값을 그대로 가져오면 된다.

 i번째 열에서 2번의 경우로 뜯기 위해선 i-1열에는 1,3만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 위 값을 더해주면 된다.

 i번째 열에서 3번의 경우로 뜯기 위해선 i-1열에는 1,2만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 아래 값을 더해주면 된다.

이렇게 n번째 열(인덱스 상으론 n-1)까지 위와 같은 규칙으로 계속 업데이트 해준 다음에 최댓값을 찾으면 전체의 최댓값을 알 수 있게 된다.

문제 링크:

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

문제:

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으며, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

 L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

 D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

 B : 커서 왼쪽에 있는 문자를 삭제함(커서가 문장의 맨 앞이면 무시됨), 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처       럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임.

 P $ : $라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오.  단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력:

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1<=N<=500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력:

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

풀이방법:

 명령어대로 구현을 하는 것은 어렵지 않은 것 같지만 시간 제한이 빡세게 걸려있기 때문에 효율적으로 구현을 하는 것이 어려운 문제인 것 같았다. 명령어를 그냥 구현하는 것은 idx , insert함수, pop함수를 사용하면 쉽게 구현할 수 있지만 시간 초과가 발생할 것 같다. insert함수, pop함수는 각각 O(n)의 시간복잡도를 가지고 있기 때문이다. (실제로 구현해보진 않았지만 아마 날 것이다.)

 그래서 넣고 빼는 것의 시간복잡도를 줄일 수 있는 자료구조가 무엇인지 생각해보니 스택과 큐가 생각났다. (이들은 넣고 뺌이 O(1)이다.) 따라서 두 개의 스택을 이용해서 이 문제를 해결하고자 하였다.

 기본적인 개념은 커서를 기준으로 왼쪽에 있는 값들의 스택, 오른쪽에 있는 값들의 스택을 만들어 두 개의 스택을 운영했다. 커서가 이동하는 것은 왼쪽스택->오른쪽스택, 오른쪽스택->왼쪽스택으로 옮기는 행위로 판단을 하였고, B는 그냥 pop, P는 append라고 생각하면 쉽게 구현 할 수 있다. '커서가 문자의 맨 앞(뒤)이면 무시됨'과 같은 말은 스택의 크기가 0임을 판단하는 것으로 해결했다.

 명령어를 다 수행하고 출력을 할 때에는 하나의 스택에 다 몰아넣고 출력해도 되지만 파이썬의 join 함수를 사용해서 한 줄로 코드를 줄일 수 있었다.

 그리고 파이썬의 경우에는 시간초과를 해결하기 위해서 입출력시에 input() 함수를 사용하지 말아야 한다고 한다. 따라서 sys 모듈에서 sys.stdin.readline().rstrip()을 사용해서 값들을 읽었다. (rstrip()은 끝에 '\n'이 붙어있다고 해서 제거하기 위함이다.)

문제 링크:

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

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

입력:

첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이 방법:

배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.

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

문제:

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람의 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Backjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들끼리 케빈 베이컨 게임을 했을 때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 토해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6 이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 =5 이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 유저의 수 N(2<=N<=100)과 친구 관계의 수 M(1<=M<=5,000)이 주어진다. 둘째 줄부터 M

개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

출력:

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

풀이방법:

일단 모든 사람들에 대해서 케빈 베이컨의 수를 계산해야 하므로 BFS로 값을 탐색해야 한다고 생각했다.  for를 사용한 반복문은 입력값을 정리하기 위한 반복문이다. (보통 저는 bfs, dfs는 이와 같이 입력값들을 정리합니다.) answer는 각 사람 별로 count의 값을 담아주는 배열이고, 인덱스를 편리하기 관리하기 위해 1번 사람이 1번째 인덱스를 가지도록 하였다. person은 인덱스 값으로 교체해줘도 괜찮을 것 같지만 bfs 내에서 한 단계 이상 넘어간다면 여러 개의 값을 가져야 할 것 같아서 애초에 배열 값으로 넣게 되었다. 그리고 또한 자기 자신의 값을 탐색하지 않도록 자신의 값은 -1로 초기화 한 상태로 값을 넣었다.

문제링크:

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

문제:

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어 있다.

출력:

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

풀이 방법:

  문제가 엄청 어려워 보이지만 "또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. " 이 문장이 함정이라는 것을 알면 어렵지 않게 된다. 실제로 예제 입력에 대해서 계속해서 부딪히게 만들어보았더니 개미가 먼 방향으로 걸어가서 떨어지는 것과 같은 값을 얻는다는 것을 알 수 있었다. (정확한 이유는 모르겠다.)

 따라서 가장 빠른 시간은 각자 개미들이 자신이 위치에서 막대가 짧은 쪽으로 이동하도록 하고, 가장 느린 시간은 개미들이 막대가 긴 쪽으로 이동하도록 한다면 값을 구할 수 있다. 배열에 넣어서 각 값을 구하도록 했더니 시간 초과가 발생해서 각 개미마다 비교해서 최솟값, 최댓값을 구하도록해서 시간을 줄이도록 했다.

문제 링크:

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

문제:

어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 불어 있게 배치할 수는 없다.

이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력:

첫째 줄에 우리의 크기 N(1<=N<=100,000)이 주어진다.

출력:

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이 방법:

 dp문제인데 N마다 생성되는 규칙을 찾아내거나 아니면 점화식을 찾으면 된다. 따라서 찾은 점화식은 다음과 같다. 

an = a(n-1) + 2*a(n-2)

따라서 이 규칙에 따라서 값을 구해주면 된다.

문제 링크:

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

문제:

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버린느 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0<=n<=100,000)

다음 줄에는 [x1,...., xn]과 같은 형태로 배열에 들어 있는 수가 주어진다. (1 <=xi <=100)

전 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력:

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

풀이 방법:

 명령어를 수행하는 것은 별로 어렵진 않았지만, 이를 위해 사전에 입력값을 전처리하고, 다시 이를 패키징 하는 것이 귀찮았다. 입력이 [1,2,3,4]와 같이 들어오게 되는데 리스트로 들어온다는 것이 아니라, 리스트처럼 생긴 스트링으로 들어오는 것이다. 따라서 이를 구분해서 배열에 담아야 한다. 명령어를 수행하는 것은 비교적 간단하다.

 처음에는 R이 들어오면 reverse를 D가 들어오면 pop(0)을 하는 방식으로 진행했더니 시간 초과가 발생하게 되었다. reverse를 하는 연산의 시간이 크다고 해서 이를 줄이기 위해서 마지막에 딱 한 번만 하는 방식으로 바꾸게 되었다.

RR이 두 번 들어온다면 두 번 뒤집는 것이기 때문에 결국 다시 처음 배열로 돌아오는 것과 같다. 즉 R이 짝수 번 들어온다면 뒤집을 필요가 없는 것이다. D는 R이 몇 번 나왔는지에 따라 빼는 위치만 달라지게 하면 된다. R이 한 번 나와 뒤집어져 있는 상태라면 맨 앞이 아닌 맨 뒤를 빼야 정상적으로 D의 명령어가 수행되는 것이다. 따라서 이를 구분하기 위해서 ReverseCount를 만들었으며, 비정상적인 명령어를 구분하기 위해서 예외처리 구문과 Error 변수를 만들었다.

문제 링크:

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