[C#] 시소 배열

백준 문제

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

1. 후기

단순 시뮬레이션...은 몰랐고 태그를 안보고 푸는 연습 중 이라 대충 자료구조 쓰면 풀겠네라는 생각을 했다.

그냥 큐 2개 만들어서 숫자 빙글빙글 돌리고 누적합 써먹으면 풀리겠지 했는데~

뭣...

while (!(frontQueue.Count == backQueue.Count || frontQueue.Count + 1 == backQueue.Count))
{
    var tmp = backQueue.Dequeue();
    frontQueue.Enqueue(tmp);
    frontQueueSum += tmp;
    backQueueSum -= tmp;
}

아마도 숫자를 옮기는 과정이 문제라고 생각하고 수정했다.

list로 바꿔서 removerange도 써보고, (구현하기 귀찮아서) 최후의 보류로 남겨둔 배열 + 투포인터 + 누적합을 사용하기로 했는데

index값 계속 틀려서 나는 왜 이렇게 머리가 나쁠까 라는 생각이 들었다. 중간에 왜 틀린지 찾을수가 없어서 테케를 랜덤으로 직접 만들기도 했다. 이건 경험이라고 생각함.

지식 다 써먹고 나니 트리를 구현해야 하나, 한 구간 지우고 나머지 누적합을 구하는 어썸한 수식이 있는지, 실버1 문제에서 얼마나 많은 것을 바라는 걸까 고민하다가 문득 눈에 띈 코드가...

Console.WriteLine(backSum);

StringBuilder로 바꾸니 눈물나게도 4%의 벽을 뚫을 수 있었다. 처음 큐 2개 코드로도 풀어져서 더더욱 슬펐다.

2. 실행 결과

3. 코드

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

class Baekjoon
{
    private void Solution(int n, int[,] arr)
    {
        var answer = new StringBuilder();
        var nums = new int[500001];
        var startIndex = 0;
        var nextIndex = 0;
        double frontSum = 0;
        double backSum = 0;
        
        for (var i = 0; i < n; i++)
        {
            if (arr[i, 0] == 1)
            {
                nums[nextIndex] = arr[i, 1];
                backSum += arr[i, 1];
                nextIndex += 1;

                var count = nextIndex - startIndex;
                if (count % 2 == 0)
                {
                    var midIndex = startIndex + count / 2 - 1;
                    frontSum += nums[midIndex];
                    backSum -= nums[midIndex];
                }
            }
            else
            {
                var count = nextIndex - startIndex;

                if (frontSum > backSum)
                {
                    answer.AppendLine(backSum.ToString());
                    backSum = 0;
                    nextIndex = startIndex + count / 2;
                }
                else
                {
                    answer.AppendLine(frontSum.ToString());
                    frontSum = 0;
                    startIndex += count / 2;
                }

                count = nextIndex - startIndex;
                if (count == 1)
                {
                    frontSum = 0;
                    backSum = nums[startIndex];
                }
                else if (backSum == 0)
                {
                    var last = count / 2 - 1;
                    for (var j = count - 1; j != last; j--)
                    {
                        frontSum -= nums[startIndex + j];
                        backSum += nums[startIndex + j];
                    }
                }
                else
                {
                    var last = count / 2;
                    for (var j = 0; j != last; j++)
                    {
                        backSum -= nums[startIndex + j];
                        frontSum += nums[startIndex + j];
                    }
                }
            }
        }
        
        for (var i = startIndex; i < nextIndex; i++)
        {
            answer.Append(nums[i]);
            answer.Append(' ');
        }
        answer.Length -= 1;

        Console.WriteLine(answer);
    }

    private static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine()!);
        var arr = new int[n, 2];

        for (var i = 0; i < n; i++)
        {
            var temp = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
            arr[i, 0] = temp[0];
            arr[i, 1] = temp[0] == 2 ? 0 : temp[1];
        }

        new Baekjoon().Solution(n, arr);
    }
}