[백준] 14468 C# 소가 길을 건너간 이유 2

소가 길을 건너간 이유 2

14468번: 소가 길을 건너간 이유 2

문제

존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다.

이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 26마리고, A, B, ... Z라는 이름이 붙는다. 존은 52개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 52글자의 문자열에는 각 알파벳이 두 번씩 나타날 것이다.

어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.

입력

첫 줄에 52글자의 문자열이 주어진다. 각 글자는 알파벳 대문자이며, 각 알파벳이 정확히 두 번씩 나타난다.

출력

경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

예제 입력 1

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

예제 출력 1

1

힌트

A와 B의 경로는 무조건 만난다.

 

풀이

문제 이해

대체 뭔소린고... 문제 이해를 위해 3번은 읽은 것 같다.

점은 소가 들어오는 입구 또는 출구가 되며 시계방향으로 콕콕 찍혀있다. 각 알파벳이 입력에서 2번씩 등장하는데 첫번째로 등장했을 때 소가 그 지점을 통해 들어온 것이고 두번째로 등장했을 때 그 지점을 통해 나간 것이다. 

두 소의 경로가 겹치지 않으려면

1. 소가 들어오자마자 바로 다음 지점에서 나가거나
2. A~Z까지의 소가 들어온 순서의 역순으로 나가야 한다.

소가 26마리나 되어서 머리가 어질어질하므로 대충 소가 4마리만 있다고 소 마릿수를 줄여서 생각해보면 앞의 두 상황은 다음과 같다.

A A B B C C D D
또는
A B C D D C B A

이외에는 소의 경로가 겹치게 된다. 먼저 들어온 소가 나중에 들어온 소보다 먼저 나가면 나중에 들어온 소의 개수만큼 경로가 겹친다.

 

따라서 몇쌍의 소가 경로가 겹치는지 알고 싶다면 나중에 들어온 소보다 먼저 들어온 소가 빨리 점을 빠져나갈 때 남아있는 나중에 들어온 소 개수를 세야 한다.

아래와 같이 시계방향의 점 8개에 4마리의 소가 들어왔다 나간다고 할 때

A B C A B D D C

나중에 들어온 B, C가 나가기 전에 A가 나가므로 2쌍이 추가되고, C가 나가기 전에 B가 나가므로 1쌍이 추가되어 최종적으로 답은 3이 된다.

 

나의 풀이

List 가 숫자를 넣고 빼기 용이해 List를 이용하여 풀었다. 

using System;
using System.Collections.Generic;
using System.Text;
namespace Baekjoon
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder(Console.ReadLine());
            List<char> list = new List<char>();
            int count = 0;
            for(int i = 0; i<sb.Length; i++)
            {
                if (!list.Contains(sb[i])) list.Add(sb[i]);
                else
                {
                    if (list[list.Count - 1] == sb[i]) list.RemoveAt(list.Count - 1);
                    else
                    {
                        int index = list.IndexOf(sb[i]);
                        count += list.Count - 1 - index;
                        list.RemoveAt(index);
                    }
                }
            }
            Console.WriteLine(count);            
        }
    }
}

 

 

후기

이차원 배열로 푸는 방법도 있다. 그건 다음 기회에...