[BAEKJOON] 백준 1639: 행운의 티켓 (C#)

문제 링크

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

 

 

문제

프로야구단 다숌 자이언츠에서는 야구장에 오는 손님에게 티켓을 나누어준다. 그리고 나서 그 티켓 중에 다음과 같은 규칙을 가진 티켓을 행운의 티켓이라고 하며, 그 티켓을 가진 사람들에게 상품을 나누어준다.

행운의 티켓은 정확하게 2N자리로 이루어진 티켓이다. 왼쪽 N자리의 합과 오른쪽 N자리의 합이 일치하면 그 티켓은 행운의 티켓이라고 한다.

숌은 티켓 번호를 조작하려고 한다. 어떤 문자열이 주어지면, 그 문자열의 연속된 부분 문자열중 행운의 티켓 규칙을 만족하는 최대 부분 문자열의 길이를 출력하는 프로그램을 작성하시오. 

 

 

입력

첫째 줄에 문자열 S가 주어진다. 문자열 S는 1보다 크거나 같고, 9보다 작거나 같은 수로만 이루어져 있고, 길이는 50보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 주어진 입력의 연속된 부분 문자열 중 행운의 티켓 규칙을 만족하는 부분 문자열의 최대 길이를 출력하시오. 찾을 수 없다면 0을 출력한다.

 

 

 

통과한 답안

namespace _1639
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            int n = S.Length;
            int maxLen = 0;

            for (int length = 2; length <= n; length += 2)
            {
                for (int i = 0; i <= n - length; i++)
                {
                    int half = length / 2;
                    int leftSum = 0;
                    int rightSum = 0;

                    for (int j = 0; j < half; j++)
                    {
                        leftSum += S[i + j] - '0';
                        rightSum += S[i + j + half] - '0';
                    }

                    if (leftSum == rightSum)
                    {
                        maxLen = Math.Max(maxLen, length);
                    }
                }
            }

            Console.WriteLine(maxLen);
        }
    }
}

 

숫자로 이루어진 문자열 S가 주어졌을 때, 이 문자열의 부분 문자열 중에서

길이가 2N이며 왼쪽의 N개의 문자의 합과 오른쪽의 N개의 문자의 합이 같은

부분 문자열의 최대 길이를 구하는 문제이다.

 

문제를 해결하는 방법으로는 간단하게 생각하면

길이가 2N인 부분 문자열을 모두 구하고, 각각의 부분 문자열에 대해서

조건을 만족하는 부분 문자열들 중에서 가장 긴 길이를 구하면 된다.

 

이를 코드로 작성한 것이 위의 코드인데 길이 n이 주어졌을 때,

길이가 2부터 2N(<= n)인 부분 문자열들에 대해서

leftSum과 rightSum을 구해서 이 둘이 같은 경우에

최대 길이와 이 길이 중에 큰 값을 최대 길이에 저장하도록 구현하였다.

 

특히, leftSum과 rightSum을 구하는 for문에서

문자를 숫자로 전환하는 과정에서 문자에서 '0'을 빼는 것으로 간략화한 부분과

각각의 숫자를 문자열의 인덱스를 이용하여 구한 부분이

코드를 보다 간략화하고 효율적으로 개선한 부분이라고 생각한다.