/<> 백준 5430: AC - C#

Darkpppet·2021년 7월 5일
Csharp백준알고리즘

백준

목록 보기
2/5

/<> 백준 5430: AC

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

solved.ac

  • Gold V [STANDARD]
  • CLASS 3

문제

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

코드

채점번호 30400130
https://www.acmicpc.net/source/30400130

using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;

int t = int.Parse(Console.ReadLine());

for (int i = 0; i < t; i++)
{
    string p = Console.ReadLine().Replace("RR", "");

    int n = int.Parse(Console.ReadLine());

    string input = Console.ReadLine();
    List<int> array = n == 0 ? new() : new(Array.ConvertAll(input.Substring(1, input.Length - 2).Split(','), int.Parse)); 

    if (p.Count(x => x == 'D') <= n)
    {
        int[] dCounts = Array.ConvertAll(p.Split('R'), x => x.Length);
	
        int leftCount = 0;
        int rightCount = 0;
	
        for (int j = 0; j < dCounts.Length; j++)
        {
            if (j % 2 == 0)
                leftCount += dCounts[j];
            else
                rightCount += dCounts[j];
        }
	
        array.RemoveRange(0, leftCount);
        array.RemoveRange(array.Count - rightCount, rightCount);
	
        if (p.Count(x => x == 'R') % 2 != 0)
            array.Reverse();
	
        if (array.Count > 0)
        {
            StringBuilder outputBuilder = new();
            outputBuilder.Append("[");
            for (int j = 0; j < array.Count - 1; j++)
                outputBuilder.Append($"{array[j]},");
            outputBuilder.Append($"{array[^1]}]");
            Console.WriteLine(outputBuilder.ToString());
        }
        else
        {
            Console.WriteLine("[]");
        }
    }
    else
    {
        Console.WriteLine("error");
    }
}

설명

이 문제를 문제 그대로 시뮬레이션 하는 프로그램을 만든다 생각해보자.
그렇다면 대충 아래와 같은 코드가 될 것이다.

List<int> array = new() { ,,, };

foreach (char function in functions)
{
    swtich (function)
    {
        case 'R':
            array.Reverse();
            break;

        case 'D':
            array.RemoveAt(0);
            break;
    }
}

이 코드에서, R함수의 array.Reverse()와 D함수의 array.RemoveAt(0)의 시간 복잡도는 모두 O(n)O(n)이다. 즉, 총 시간복잡도는 O(mn)O(mn)의 제곱 시간 복잡도가 나온다. 그리고 매우 높은 확률로 제곱 시간 복잡도 알고리즘은 시간 초과를 받게 될 것이다.

실제로 제출해 보면, 시간초과가 나온다.

시간 초과를 받지 않기 위해, 새로운 방법을 생각 해 보자.

List<int> array = new() { ,,, };

bool isLeft = true;

foreach (char function in functions)
{
    swtich (function)
    {
        case 'R':
            isLeft = !isLeft;
            break;

        case 'D':
            array.RemoveAt(isLeft ? 0 : array.Count - 1);
            break;
    }
}

R함수가 배열을 뒤집는 대신, D함수로 버릴 위치를 바꿔 준다. 그리고 D함수에선, 버릴 위치에 따라 앞쪽에서 버리거나 뒤쪽에서 버린다.

이 때, R함수의 isLeft = !isLeft의 시간 복잡도는 O(1)O(1)이고, D함수의 array.RemoveAt(0)의 경우는 O(n)O(n), array.RemoveAt(array.Count - 1)의 경우는 O(1)O(1)의 시간 복잡도를 갖게 된다.

이 방법도 최악의 경우에는 O(mn)O(mn)의 제곱 시간 복잡도가 나오지만, 아무래도 이전 방법처럼 항상 O(mn)O(mn)의 시간 복잡도를 갖지는 않으므로, 실제로 제출 해 보면 통과한다.

이정도로 만족할 수 없기 때문에, 조금 더 많이 효율적인 알고리즘을 생각 해 보았다.

  1. 함수 조합을 입력 받을 때, RR을 모두 제거하여 입력 받는다.
  2. 함수 조합의 D의 개수가 배열의 원소 개수보다 많으면 바로 error를 발생시킨다.
  3. 함수 조합을 R을 기준으로 분리하고, 각 분리된 부분의 D의 개수를 원소로 갖는 배열을 만든다.
  4. 3에서 만든 배열의 짝수 인덱스 원소를 각각 모두 더하고, 홀수 인덱스 원소도 각각 모두 더한다.
  5. 4에서 더한 짝수 인덱스 원소들 만큼 배열의 왼쪽에서 버리고, 홀수 인덱스 원소들 만큼 배열의 오른쪽에서 버린다.
  6. 함수 조합의 R의 개수가 홀수 개라면, 배열을 뒤집는다.

위 알고리즘의 모든 단계는 선형 시간 복잡도에 작동한다. 즉, 위 알고리즘은 선형 시간 복잡도를 갖는다.

이제 위 알고리즘을 코드로 작성 해 보자.

  1. 함수 조합을 입력 받을 때, RR을 모두 제거하여 입력 받는다.
string p = Console.ReadLine().Replace("RR", "");

함수 조합 RR은 배열을 뒤집고 다시 뒤집기 때문에 결과적으로 아무 행동도 하지 않는다. 따라서 함수 조합의 RR을 모두 지워도 결과는 같다. 또한 이 과정 후에는, 함수 조합에 R이 두 개 이상 연속으로 나타나지 않는다.

  1. 함수 조합의 D의 개수가 배열의 원소 개수보다 많으면 바로 error를 발생시킨다.
if (p.Count(x => x == 'D') <= n)
{
    ///
}
else
{
    Console.WriteLine("error");
}

배열의 원소의 개수는 정해져 있고, 그 이상 버리는 것은 불가능하다. 그리고 함수 조합의 함수 순서에 상관없이 이 불가능 여부는 알 수 있으므로, 먼저 확인 해 준다.

  1. 함수 조합을 R을 기준으로 분리하고, 각 분리된 부분의 D의 개수를 원소로 갖는 배열을 만든다.
int[] dCounts = Array.ConvertAll(p.Split('R'), x => x.Length);

1의 과정 결과, R은 두 개 이상 연속으로 나오지 않으므로, 함수 조합을 R을 기준으로 분리한 결과는 오직 D만 있다. (맨 처음이 R인 경우, 분리된 첫 번째는 빈 문자열일 수 있다.)

  1. 3에서 만든 배열의 짝수 인덱스 원소를 각각 모두 더하고, 홀수 인덱스 원소도 각각 모두 더한다.
int leftCount = 0;
int rightCount = 0;
		
for (int j = 0; j < dCounts.Length; j++)
{
    if (j % 2 == 0)
        leftCount += dCounts[j];
    else
        rightCount += dCounts[j];
}
  1. 4에서 더한 짝수 인덱스 원소들 만큼 배열의 왼쪽에서 버리고, 홀수 인덱스 원소들 만큼 배열의 오른쪽에서 버린다.
array.RemoveRange(0, leftCount);
array.RemoveRange(array.Count - rightCount, rightCount);

짝수 인덱스의 원소들은 배열 왼쪽에서 버리는 것을 나타내고, 홀수 인덱스의 원소들은 배열 오른쪽에서 버리는 것을 나타낸다. 짝수 인덱스는 R이 짝수 번 나타난 후의 D의 개수이고, 홀수 인덱스는 R이 홀수 번 나타난 후의 D의 개수와 같기 때문이다.

  1. 함수 조합의 R의 개수가 홀수 개라면, 배열을 뒤집는다.
if (p.Count(x => x == 'R') % 2 != 0)
    array.Reverse();

배열을 뒤집는 과정 없이, 앞 뒤에서 버리기만 했으므로, 결과가 뒤집어져야 할 경우 뒤집어 준다.

실제로 두 번째로 설명한 제곱 시간 복잡도 알고리즘의 답은 약 2000ms로 통과하고, 마지막으로 설명한 선형 시간 복잡도 알고리즘의 답은 약 400ms로 통과한다.

여담으로, 결과 배열을 출력할 때, 코드가 좀 지저분한데, Linq의 Aggregate() 메소드를 사용하면 조금 더 깔끔하게 표현 가능 할 것이다.

profile
Darkpppet
이전 포스트

/<> 백준 11444: 피보나치 수 6 - C#

다음 포스트

/<> 백준 13705: Ax+Bsin(x)=C - C#

0개의 댓글