[프로그래머스/C#] N으로 표현

문제

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

프로그래머스

 

 

 

 

 

---

 

코드

 

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        List<List<int>> dp = new List<List<int>>();
        HashSet<int> hs = new HashSet<int>();
        int temp = 0;
        for(int i=0;i<9;i++)
        {
            dp.Add(new List<int>());
            if(i==0) continue;
            temp=10*temp+N;
            dp[i].Add(temp);
            hs.Add(temp);
        }
        for(int i=2;i<=8;i++)
        {   
            for(int j=1;j<=i/2;j++)
            {
                for(int k=0;k<dp[j].Count;k++){
                    int n1 = dp[j][k];
                    for(int l=0;l<dp[i-j].Count;l++){
                        int n2 = dp[i-j][l];
                        int sum = n1+n2;
                        int subtract1 = n1-n2;
                        int subtract2 = n2-n1;
                        int multiply = n1*n2;
                        int divide1 = 0;
                        if(n2!=0) divide1 = n1/n2;
                        int divide2 = 0;
                        if(n1!=0) divide2 = n2/n1;
                        if(!hs.Contains(sum)){
                            dp[i].Add(sum);
                            hs.Add(sum);
                        }
                        if(!hs.Contains(subtract1)){
                            dp[i].Add(subtract1);
                            hs.Add(subtract1);
                        }
                        if(!hs.Contains(subtract2)){
                            dp[i].Add(subtract2);
                            hs.Add(subtract2);
                        }
                        if(!hs.Contains(multiply)){
                            dp[i].Add(multiply);
                            hs.Add(multiply);
                        }
                        if(!hs.Contains(divide1)){
                            dp[i].Add(divide1);
                            hs.Add(divide1);
                        }
                        if(!hs.Contains(divide2)){
                            dp[i].Add(divide2);
                            hs.Add(divide2);
                        }
                    }
                }
            }
        }
        if(!hs.Contains(number)) answer=-1;
        else for(int i=0;i<dp.Count;i++){
            if(dp[i].Contains(number)){
                answer=i;
                break;
            }
        }
        return answer;
    }
}

 

---

 

풀이(를 가장한 소감)

냅다 소감부터 질러보자면 하느라 죽는 줄 알았다.

프로그래머스에서는 동적계획법으로 나와있지, 근데 감이 잘 안오지, 어찌어찌 하기엔 너무 효율성은 없어보이지, 자꾸 틀리지... 어찌저찌해서 풀고 다른 사람들 코드를 보니 자괴감이 오고 더더욱 동적계획법이라고 설명되어 있어야 하나 싶지..

(오히려 그래프 탐색으로 푼 사람들이 꽤 되는데다 심지어 코드도 더 깔끔했다)

 

내가 구현한 코드를 설명해보자면 일단 N, NN, NNN 형식의 숫자들은 8이하 개수로 쓸 수 있는 것까지 싹다 이차원 리스트에 넣었는데, 리스트의 인덱스가 숫자를 사용한 개수로 구현했다.

그런 다음 for문으로 탐색을 하여 (4중이나 써버렸다....) i(개수)만큼 사용하여 얻을 수 있는 숫자들의 조합을 찾아냈다.

예를 들어 i가 3이면 리스트 인덱스 1인 리스트와 2인 리스트에 있는 숫자들의 사칙연산을 통해 이미 구해진 수인지 아닌지를 판별하여 인덱스 3인 리스트에 집어넣는 방식인 셈.

 

그렇게 어떻게든 구현하려 했건만, 그래프 탐색으로 훨씬 깔끔하게 푼 사람들을 보니 눈물이 앞을 가린다...

 

---

 

다른 사람 풀이

(1)DFS

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

public class Solution {
    int answer = 9;
    public int solution(int N, int number) 
    {
        Dfs(N,number,0,0);
        if(answer>8)
            return -1;
        return answer;
    }

    void Dfs(int N, int number, int idx, int sum)
    {
        if(idx>8) return;
        if(sum==number)
            answer = idx < answer ? idx : answer;
        int tmp = 0;
        for(int i = 0; i < 8; i++)
        {
            tmp = tmp*10+N;
            Dfs(N,number,idx+i+1,sum+tmp);
            Dfs(N,number,idx+i+1,sum-tmp);
            Dfs(N,number,idx+i+1,sum*tmp);
            Dfs(N,number,idx+i+1,sum/tmp);
        }

    }
}

 

그래 이런 코드 말이다.. 눈물이 앞을 가릴수밖에 없다고.

막말로 내가 dp로 풀었다고는 하다만 내 풀이조차 dp로 안보인다고...ㅠ

DFS로 그냥 싹 탐색 돌리고서 number랑 같은 수 나오면 answer랑 횟수(idx) 값 비교해서 더 작은 값 넣는 방식 얼마나 깔끔하고 보기 좋고 직관적인가.

 

---

 

(2)

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

public class Solution
{
    Dictionary<int, HashSet<int>> resultSet = new Dictionary<int, HashSet<int>>();
    int n;
    int number;

    int[] ns = null;

    public int solution(int n, int number)
    {
        this.n = n;
        this.number = number;
        ns = new int[9];
        ns[0] = 0;
        for(int i = 1; i < ns.Length; i++)
        {
            ns[i] = ns[i - 1] * 10 + n;
        }

        for (int count = 1; count < 9; count++)
        {
            if (FindSolution(count).Contains(number))
                return count;
        }
        return -1;
    }

    HashSet<int> FindSolution(int count)
    {
        if (resultSet.TryGetValue(count, out HashSet<int> cache))
        {
            return cache;
        }

        HashSet<int> set = new HashSet<int>();
        resultSet.Add(count, set);

        set.Add(ns[count]);

        int maxLegth = count / 2;
        for(int i = 1; i <= maxLegth; i++)
        {
            var set1 = FindSolution(i);
            var set2 = FindSolution(count - i);

            foreach(int n1 in set1)
            {
                foreach(int n2 in set2)
                {
                    set.Add(n1 + n2);
                    set.Add(n1 - n2);
                    set.Add(n2 - n1);
                    set.Add(n1 * n2);
                    if (n1 != 0)
                        set.Add(n2 / n1);
                    if (n2 != 0)
                        set.Add(n1 / n2);
                }
            }
        }

        return set;
    }
}

내가 한 방식이랑 비슷하긴 하다.

이 분은 HashSet을 count 당 생성하여 해당 count로 생성할 수 있는 숫자들을 HashSet에 추가하고 이를 반환하여 number가 포함되어 있으면 count를 정답으로 반환하는 방식.

count로 생성할 수 있는 숫자들을 찾을 때도 재귀를 써서 찾는 방식도 재밌어서 포스팅해본다.