20231124_카드뭉치(프로그래머스)

오늘의 TIL은 알고리즘 코드카타의 문제 카드 뭉치로

 

두 개의 배열 cards1, cards2를 주어줬을 때, 이 두 개의 배열로 goal이라는 배열을 만들 수 있는가를 묻는 문제이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/159994

 

이 문제를 해결하는데 있어서 어떻게 하면 좀 더 빠르게 풀 수 있을지를 고민했는데,

처음에는 for 문을 이용하여 문제를 해결하려했지만, 잘 해결되지 않아 다른 방법을 고안해낸 것이

 

goal을 기준으로 goal과 같은 단어를 포함하는 경우에는 진행하고 포함하지 않는 경우에는 No를 return하는 것이였다.

또, 중간의 것은 사용할 수 없기에 두 배열의 첫번째만을 사용하므로

goal[0] == cards1[0] 혹은 goal[0] == cards2[0]인 경우에

goal[0]과 그와 같은 cards1[0] 혹은 cards2[0]을 지우는 방식으로 진행하기로 기획했다.

 

이 과정에서 배열과 리스트의 차이점을 다시 한 번 깨달았는데,

배열의 경우 크기가 정해져있고 하나를 지우려면 전부를 지우고 하나 작은 크기로 새로 만들어야되므로

배열을 사용하는 것은 시간적으로 많이 소모될 것으로 판단해 리스트를 사용하기로했다.

 

따라서 나온 코드는 아래와 같은데,

 

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

public class Solution {
    public string solution(string[] cards1, string[] cards2, string[] goal) {
        string answer = "Yes";
        
        List<string> str1 = new List<string>(cards1);
        List<string> str2 = new List<string>(cards2);
        List<string> goalList = new List<string>(goal);
        
        while (goalList.Count > 0)
        {
            if (str1.Count == 0 && str2.Count == 0)
            {
                answer = "No";
                break;
            }
            if (goalList.Count > 0)
            {
                if (str1.Count > 0 && goalList[0] == str1[0])
                {
                    goalList.RemoveAt(0);
                    str1.RemoveAt(0);
                }
                else if (str2.Count > 0 && goalList[0] == str2[0])
                {
                    goalList.RemoveAt(0);
                    str2.RemoveAt(0);
                }
                else
                {
                    answer = "No";
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

우선 cards1, cards2, goal을 전부 List로 변환한 뒤에,

goal과 str1, str2를 비교하는 작업을 진행했다.

만약 goal이 남아있는데 str1, str2가 모두 소모했다면, No를 return하도록

goal이 남아있는 경우에는 goal의 첫 단어가 str1의 첫 단어와 같은지 혹은 str2의 첫 단어와 같은지

비교한 뒤에 같은 단어가 있다면 goal과 해당하는 리스트의 첫 단어를 지우는 방식으로 진행하여

goal의 단어를 모두 지우는데 성공하면 Yes를 return하는 방식이다.

 

오늘도 알고리즘 문제를 푸는데 좀 더 색다르게 풀 수 있도록 노력을 많이하였는데,

시간이 남는 경우에는 이런 식으로 좀 더 다채로운 방식으로 문제를 풀면서 머리를 말랑말랑하게 하도록 할 것이다.