[백준 / BOJ] 5430 AC

문제

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

5430번: AC

선영이는 AC라는 언어를 만들었다.

AC정수배열에 연산을 하기위해 만든 언어이다.

 

AC에는 R, D가 주어진다. R은 주어진 정수배열을 뒤집는 연산이고 D는 현재 정수배열의 가장앞 정수를 없애는 연산이다.

 

정수배열과 연산이 주어졌을때, 결과를 출력하는 문제였다. (지울수없는경우 error를 출력한다.)

 

풀이

구현 문제였다.

문자열 구현이 약한거같아서 일부러 찾아 푸는중인데, 역시나 구현이 쉽지는 않았다.

 

모든 연산에 대해 시뮬레이션을 수행하면, 테스트 케이스가 하나만 되도 시간초과가 날수있다.

배열 연산이 총 10만개 주어질수있고, 이때, 배열을 복사하는데 10만번 반복하기 때문에, 반복횟수는 100,000^2이 된다

 

문제의 연산에 대해 생각해보면, 굳이 배열을 복사해가며 현재상태를 만들어주지않아도 된다.

D연산의 경우 항상 현재배열의 가장 앞 정수를 없앤다.

R연산의 경우 배열을 뒤집는다.

즉, 현재까지 R연산을 입력받은 횟수가 짝수인경우, D연산은 배열의 앞부분을 지운다.

반대로 R연산을 입력받은 횟수가 홀수인경우, D연산은 배열의 뒷부분부터 지운다.

 

따라서, 다음과 같은 알고리즘을 생각할수있다.

 

출력해야할 구간을 left, right라고할때, R연산의 입력횟수에따라 left와 right값을 번갈아가며 참조하며, D연산이 입력되었을때, 참조하는 방향에서 +1 혹은 -1을 해준다. 따라서, 최종적으로 출력할 정수배열의 범위는 (left+a, right-b) 가된다. (a와 b는 적절히 빼주고 더해준 값)

 

이를 그대로 구현했다.

(실수를 줄이고, 구현중 편하게 생각하기위해 R에 나머지 연산을 하며 상태를 봐주지는 않았고, 현재 뒤집은 상태를 나타내는 bool rev변수를 만들어서 구현했다.)

 

구현중, 정수배열의 정수가 항상 한자릿수가 아닐수있다. 즉, D연산이 입력되었을때, 정수배열에서 정수를 없애기위해 left혹은 right을 여러번 더하거나 빼줘야할수있는데, 이를 구현하기위해 delL, delR(각각 왼쪽에서 지워야할 정수의 갯수, 오른쪽에서 지워야할 정수의 갯수)를 선언하고, delL,delR이 0보다 크다면, ','가 나올때까지 left 와 right에 연산(더하고빼는)을 해줬다. (r >= l 조건또한 만족해야한다. l범위는 절대 r범위를 벗어날수없으므로.)

 

따라서, delL과 delR이 0보다 크다면 D연산을 전부 진행할수없었던것 이므로 error를 출력해준다.

(좀 어렵게 구현한거같다.)

 

조심해야할 테스트케이스로 

 

1

R

1

[123]

답 : [123]

오답 : [321]

 

이 있었다.

 

현재 배열이 거꾸로 출력해야하는 정수배열일때, 무조건 뒤에서부터 출력하지말도록하자.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/5430%20AC/main.cpp

devxb/JJUNalgo