[C언어] 백준 5430 AC

 

문제

선영이는 주말에 할 일이 없어서 새로운 언어 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 

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1 

[2,1]
error
[1,2,3,5,8]
error

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

5430번: AC

 

입력받는 값에 따라서 배열을 회전 시킬지 요소 하나를 없앨지를 결정하는 파싱 문제입니다.

 

우선 문제를 푸시기 전에 배열에 들어갈 수 있는 요소의 최대 갯수를 보시면

"배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)" 입니다.

즉 최대 10만개의 요소가 들어오는 겁니다.

 

(1 ≤ xi ≤ 100) 요소로 들어오는 정수의 크기인데요

그렇다면 [](2), 정수(최대 기준 3) * 10만, ","(10만 - 1)

이 모두를 더해 봤을 때 배열 요소로 받는 문자열의 최대 길이는 400,001이 됩니다.

n의 갯수가 10만이지 n을 받는 문자열의 길이가 10만이 아니라는 겁니다.

이것을 몰라서 33%에서 많이 틀리시는 분이 있으시니 이 점을 꼭 유의하셔야 겠습니다.

 

그럼 본격적으로 문제 해석을 해 봅시다.

 

첫째 줄에는 테스트 케이스의 수가 들어오고

각 테스트 케이스의 첫째 줄에는 명령어

각 테스트 케이스의 둘째 줄에는 요소의 갯수

각 테스트 케이스의 셋째 줄에는 요소들이 들어있는 문자열

 

이렇게 들어오는 형식입니다.

 

명령어의 경우 R과 D가 있습니다.

R : 요소들이 들어있는 배열 뒤집기

D : 요소들이 들어있는 배열의 맨 앞 요소 제거

 

생각 보다 간단해 보이지만 간단하지 않습니다.

그 이유는 요소의 갯수가 최대 10만이고 명령어의 수 또한 최대 10만이라는 겁니다.

즉 10만개의 요소가 들어오고 명령어 10만이 전부 R일 경우 시간 복잡도는 최소 10만log10만 * 10만 인겁니다.

500억 정도의 연산을 하게 될텐데 그정도며 한숨 자고 와도 프로그램은 끝나지 않고 돌아가고 있을겁니다.

 

그렇다면 우리는 R명령어의 경우 실제로 배열을 뒤집지 말고 뒤집은것 처럼 행동하게끔 만들어야 합니다.

이 점때문에 D명령어도 많이 신경을 써주어야 합니다.

 

저 같은 경우 배열의 첫 번째 요소를 first, 마지막 요소를 last 변수로 인덱스를 맞추고

R명령어가 들어 왔을 때 두 변수의 값을 바꾸어 주었습니다.

 

먼저 코드를 보시죠

 

#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) {int t = a; a = b; b = t;}
int	t, q[100001], n, first, last;
char	p[100001], nums[400001];

int	D()
{
	// 요소가 0개인 경우
	if (first == last)
	{
		printf("error\n");
		return (1);
	}
    // R명령어로 배열이 뒤집어 진경우
	if (last < first)
		first--;
	else
		first++;
	return (0);
}

void	R()
{
	swap(last, first);
}

R명령어의 경우 첫 인덱스와 마지막 인덱스를 서로 바꾸어 줍니다.

 

D명령어는 첫 인덱스와 마지막 인덱스가 서로 같으면 요소의 갯수가 0개니까 예외처리를 해주고

R명령어로 인해 last 변수가 first 변수보다 작게 변한 경우와 그렇지 않은경우 각각 배열의 맨 앞요소를 처리해 줍니다.

 

void	print()
{
	int	i;
	int	j;

	// 요소가 0개인 경우
	if (first==last)
	{
		printf("[]\n");
		return ;
	}
	printf("[");
	i = first;
	j = last;
    // R명령어로 배열이 뒤집어져 있는 경우
	if (i > j)
	{
		i--;
		for(; i > j; i--)
			printf("%d,", q[i]);
	}
	else
	{
		for(; i < j - 1; i++)
			printf("%d,", q[i]);
	}
	printf("%d]\n", q[i]);
}

 

 

출력 함수인 print 함수입니다.

R명령어로 배열이 뒤집여져 있을 때 i의 값을 -1씩 감소 시키면서 출력 시키고

그렇지 않은경우 반대로 +1씩 증가 시키면서 출력 시키게끔 했습니다.

 

배열이 뒤집어져 있을 때 i--하면서 들어간 이유는 배열에 요소를 push하면서 마지막 인덱스가 늘어났기 때문에

i가 마지막 요소의 인덱스 + 1 이어서 -1을 해 인덱스를 맞춘겁니다.

 

배열이 안뒤집어져 있을 때도 마찬가지 입니다.

j가 마지막 인덱스 + 1 이기 때문에 연산을 j - 1까지만 하는 겁니다.

 

 

 

void	push(int num)
{
	q[last++] = num;
}

int	main(void)
{
	int	err_flag;

	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		first = 0;
		last = 0;
		err_flag = 0;
		scanf("%s %d %s", p, &n, nums);
		for(int j = 1; nums[j]; j++)
		{
			if ('0' <= nums[j] && nums[j] <= '9')
			{
				push(atoi(&nums[j]));
				while ('0' <= nums[j] && nums[j] <= '9')
					j++;
			}
		}
		for (int j = 0; p[j]; j++)
		{
			if (p[j] == 'D')
			{
				if (D())
				{
					err_flag = 1;
					break ;
				}
			}
			else
				R();
		}
		if (!err_flag)
			print();
	}
}

마지막 main 함수입니다.

정수가 담겨있는 배열을 문자열로 받아 그대로 atoi시켜 push해줍니다.

이후 명령어 처리를 해주는데 D명령어에서 오류가 난 경우 곧바로 에러 플래그 변수를 세운뒤 break 시켜

다음 반복문을 수행하게 해줍니다.

R 명령어는 그대로 R 명령어를 수행하게 하게끔 했습니다.

이렇게 모든 명령어 까지 수행을 한 뒤 D명령어에서 오류가 나지 않았다면 출력해주고 다음 반복을 실행하게끔 구현했습니다.

 

 

 

처음에는 쉬운 문제인줄 알았지만 R명령어 때문에 고생을 했고 n을 받는 문자열의

길이가 40만인걸 생각하질 않아서 많이 틀렸네요.

파싱에 대해서 좀 더 공부를 해야겠다는 생각이 드는 문제였습니다.

 

반응형

전체 코드

#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) {int t = a; a = b; b = t;}
int	t, q[100001], n, first, last;
char	p[100001], nums[400001];

int	D()
{
	if (first == last)
	{
		printf("error\n");
		return (1);
	}
	if (last < first)
		first--;
	else
		first++;
	return (0);
}

void	R()
{
	swap(last, first);
}

void	push(int num)
{
	q[last++] = num;
}

void	print()
{
	int	i;
	int	j;

	if (first==last)
	{
		printf("[]\n");
		return ;
	}
	printf("[");
	i = first;
	j = last;
	if (i > j)
	{
		i--;
		for(; i > j; i--)
			printf("%d,", q[i]);
	}
	else
	{
		for(; i < j - 1; i++)
			printf("%d,", q[i]);
	}
	printf("%d]\n", q[i]);
}

int	main(void)
{
	int	err_flag;

	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		first = 0;
		last = 0;
		err_flag = 0;
		scanf("%s %d %s", p, &n, nums);
		for(int j = 1; nums[j]; j++)
		{
			if ('0' <= nums[j] && nums[j] <= '9')
			{
				push(atoi(&nums[j]));
				while ('0' <= nums[j] && nums[j] <= '9')
					j++;
			}
		}
		for (int j = 0; p[j]; j++)
		{
			if (p[j] == 'D')
			{
				if (D())
				{
					err_flag = 1;
					break ;
				}
			}
			else
				R();
		}
		if (!err_flag)
			print();
	}
}