[백준][C++] 5430 AC

5430. AC

5430번: AC

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

 

---

 

 

알고리즘 설계 1

 

처음에는 정석대로 R과 D를 시뮬레이션했다. 

 

 

 

코드 1

// 일부분
for (char c : command)
{
	if (c == 'R')
	{
		reverse(list.begin(), list.end());
		//list.reverse();
	}
	else
	{
		if (list.empty())
		{
			isError = true;
			break;
		}
		else
		{
			list.erase(list.begin());
		}
	}
}

 

이렇게 정석대로 진행했지만, 결과는 시간 초과 ㅠ_ㅠ... 

문자열의 길이가 최대 100,000이므로, 명령의 길이도 100,000. 만약에 명령에 R만 있다면, 최악의 경우 길이가 100,000인 문자를 100,000번 리버스 시켜야하는 것이다.

내가 봐도 비효율적인 알고리즘... 골드 문제를 너무 쉽게 생각한 것 같다.

 

---

 

알고리즘 설계 2

그래서 리버스를 과감하게 없애주는 알고리즘을 구상했다.

 

 

1. [N, N, N] 형태의 주어진 숫자들을 NNN의 문자열로 바꾼다.

 

2. 현재 문자가 R일 때는 bool형 변수 isReverse를 현재 값과 반대로 해준다.

 

3. 현재 문자가 D일 때

• !isReverse(초기값): 문자열의 0번째를 제거해준다.
• isRverse: 문자열의 마지막 요소를 제거해준다.
• 만약 제거할 것이 없다면, 에러로 간주한다.

4. 명령이 끝난 후

• isRevese: 문자열을 리버스 시켜 출력한다.
• !isReverse: 문자열을 출력한다.

 

 

최종 코드 

#include<iostream>
#include<deque>
#include<string>
#include<algorithm>
using namespace std;

void printarr(deque<int>& list, bool reverse);

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int count;
	cin >> count;

	while (count--)
	{
		string command, arr, num = "";
		int length;
		bool isError = false, isReverse = false;
		deque<int> list;

		cin >> command >> length >> arr;

		// 문자열 파싱
		for (int i = 1; i < static_cast<int>(arr.size()); i++)
		{
			if ((arr[i] == ',' || arr[i] == ']') && !num.empty())
			{
				list.push_back(stoi(num));
				num = "";
			}
			else
			{
				num += arr[i];
			}
		}

		// 명령어 실행
		for (char c : command)
		{
			if (c == 'R')
			{
				isReverse = !isReverse;
			}
			else
			{
				if (list.empty())
				{
					isError = true;
					break;
				}
				else
				{
					if (isReverse)
						list.pop_back();
					else
						list.pop_front();
				}
			}
		}

		// 결과 출력
		if (isError)
		{
			cout << "error\n";
		}
		else
		{
			printarr(list, isReverse);
		}
	}
}

void printarr(deque<int>& list, bool isR)
{
	if (isR)
	{
		reverse(list.begin(), list.end());
	}

	cout << '[';
	for (int i = 0; i < list.size(); i++)
	{
		cout << list[i];
		if (i != list.size() - 1) cout << ',';
	}
	cout << "]\n";
}

 

[N, N, N] 형태로 나오는 원소를 NNN 형태로 바꾸는 아이디어를 구상하는 부분이 재미있었다.

 

또, R 명령을 시뮬레이션하지 않고 bool값으로 상태만 표현해주는 아이디어가 신기했다. 효율적인 구상의 중요성을 다시 배울 수 ㅣ있었다.