백준 #1343 - 폴리오미노

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

1343번: 폴리오미노

그리디 알고리즘으로 분류된 1343번 폴리오미노 입니다.

 

요새 게임 만드는거 공부한다고 알고리즘에 소홀했습니다.

알고리즘 스터디 하고있는데 문제 한번 잘못냈다가 고생을해서 쉬운 문제로 고르다보니

간만에 해도 재밌네요 ㅎㅎ 잡소리는 여기까지 하고 설명 가겠습니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1343
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine().Replace('X', 'A');
            var strList = new List<string>();
 
            int index = 0;
            int targetIndex = 0;
 
            while(index < input.Length && targetIndex < input.Length)
            {
                if (input[index] == input[targetIndex])
                    targetIndex++;
                else
                {
                    strList.Add(input.Substring(index, targetIndex - index));
                    index = targetIndex;
                }
            }
            strList.Add(input.Substring(index, targetIndex - index));
 
            if (strList.Find(x => x.Length % 2 != 0 && x.StartsWith("A")) != null)
                Console.WriteLine("-1");
 
            else
            {
                strList.ForEach(x =>
                {
                    if (x.StartsWith(".")) Console.Write(x);
                    else if (x.Length % 4 == 0) Console.Write(x);
                    else Console.Write(x.Substring(0, x.Length - 2) + "BB");
                });
            }
        }
    }
}
 

바로 예시로 가는게 나을거 같습니다.

 

폴리오미노 : AAAA , BB

 

ex) XXXX....XXXXXX....XX...

문제 입력이 이런식으로 주어지는데요 간단하게 설명하자면 저 X들을 AAAA, BB로 채우면 되겠습니다.

다만 X가 4개있으면 AAAA 또는 BBBB 이런식으로 채울수 있는데 사전순으로 앞으로 오게 채우면 되겠습니다.

 

즉 AAAA를 먼저 채워주고 남는칸에 BB를 채워주면 됩니다.

 

먼저 입력받은 문자열의 X를 전부 A로 바꿔줬습니다. => Replace

그럼 AAAA....AAAAAA....AA... 이런 식으로 나옵니다. ('.'의 갯수는 별로 관심이 없기에 대충 적었습니다.)

 

다음 저 문자열을 A의 덩어리와 .의 덩어리로 나눠 리스트에 넣었습니다.

AAAA, ..... AAAAAA, ......, AA, ...

 

다음 A로 시작하는 문자열을 전부 보는데 폴리오미노 길이가 4또는 2니까 길이가 2로나눈 나머지가

0이 아닌 것들은 폴리오미노로 채워질수 없습니다. 예외처리 해줍시다.

 

다음 4로 나눠봐서 나머지가 0이라면 모두 A로 채워지고 나머지가 있다면 B를 써서 채워야 한다는

얘기가 되겠습니다.

 

Length % 4 ==0 인것과 아닌것으로 나눠서 BB를 붙여주고 출력해줬습니다.