[백준 5430번] AC

난이도: 골드 V

문제 링크: https://www.acmicpc.net/problem/5430

5430번: AC

 

백준 5430번 문제 AC

 

각 테스트 케이스별로 입력은 다음과 같이 들어옵니다.

RDD

4

[1,2,3,4]

즉 맨 첫줄과 세 번째 줄은 string 형식이고, 두 번째 줄은 int 형식이 됩니다.

 

이 문제를 해결하려면 두 가지 포인트를 신경써야 합니다.

1. 입력받은 string 형태의 수열을 실제 int형 배열로 변환하기

2. 시간 제한 문제

 

1의 경우, 예전에 제가 블로그에 올렸던 C++에서 문자열을 쉽게 자르는 방법이 있습니다 (링크).

문자열의 맨 앞과 뒤에 대괄호가 들어오므로 이를 제거하고, 공백 대신 콤마 (,)를 기준으로 문자열을 자른 후,

stoi를 이용하여 string을 int로 변환해서 넣어주면 됩니다.

 

2의 경우, 배열에 걸리는 각 연산의 시간 복잡도를 고려해 봅니다.

R 연산의 경우, 배열을 뒤집어야 합니다. 따라서 원소의 개수만큼 쓰기 연산을 해야 합니다 (O(n)).

함수의 최대 길이는 10만 개이므로, R이 10만 번 있는 경우 총 10만 번 뒤집는 연산을 하게 됩니다.

그리고 이는 배열을 한 번도 뒤집지 않은 것과 결과가 같습니다.

 

따라서 제가 접근한 방법은, R이 등장한 횟수를 세는 것입니다.

R이 홀수이면 최종적으로 1번 뒤집은 것과 같은 결과가 되며, 짝수이면 뒤집지 않은 것과 같은 결과가 됩니다.

또한, D 연산을 위해, 현재 R의 상태를 모니터링합니다.

D연산이 나오기까지의 R의 총 등장 횟수가 홀수라면, 뒤집지 않았을 때 기준으로 맨 뒤의 원소를 제거하고, 짝수라면 뒤집지 않았을 때 기준으로 맨 앞의 원소를 제거합니다.

이 횟수를 각각 센 후, 일괄적으로 원소를 제거하고 뒤집으면 됩니다.

 

이 외에 error가 출력되는 경우라면, D의 등장 횟수가 배열의 총 원소의 개수보다 많은 경우가 됩니다.

따라서 D를 세고, 입력받은 n과 비교해 보면 됩니다.

 

코드로 보면 더 이해하기 수월할 것입니다.

 

문자열을 다루는 내용은 코딩 테스트에서도 정말 많이 다루는 부분입니다.

이런 문제를 통해 익숙해지면 좋습니다.

 

채점 결과

첫 번째 런타임 에러는 "error"를 출력할 때를 잘못 설정했고 (문자열이 비었는데 문자열의 원소에 접근하려 하였음),

두 번째 시간 초과는 D연산을 수행할 때 원소를 하나씩 제거하여 일어난 결과입니다. (string.pop_back() 등).

위 점을 고쳐서, 새로운 벡터 next에 assign할 때 필요한 원소만 복사하는 방식으로 접근하여 정답 판정을 받았습니다.