프로그래머스 lv 3. 42895 N으로 표현 c++ **다시 풀어보기**

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

 

#include <bits/stdc++.h>

using namespace std;

int solution(int N, int number){
    set<int> dp[9];
    int tmp=0;
    for(int i=1; i<=8; i++){
        tmp= tmp*10 +N;
        dp[i].insert(tmp);
    }
    for(int i=1; i<=8; i++){
        for(int j=1; j<=i; j++){
            for(auto x:dp[j]){
                for(auto y: dp[i-j]){
                    dp[i].insert(x+y);
                    dp[i].insert(x-y);
                    if(x!=0 && y!=0){
                        dp[i].insert(x*y);
                        dp[i].insert(x/y);
                    }
                }
            }
        }
        if(dp[i].find(number)!=dp[i].end()) return i;
    }
    return -1;
}

 

set 이라는 자료구조를 사용하는 것에대 대해서 잘 이해해야한다. 

이때에 set 이라 말하는 것은 unordered_set 과 set 모두를 의미한다. 

 

C++의 `std::unordered_set`과 `std::set`은 서로 다른 내부 구현 자료구조를 사용합니다.

1. **`std::unordered_set`:**
   - `std::unordered_set`은 해시 테이블(Hash Table)을 기반으로 한 자료구조입니다.
   - 해시 테이블은 각 요소를 고유한 해시값으로 매핑하고, 이 해시값을 사용하여 빠르게 요소에 접근할 수 있도록 합니다.
   - 요소의 삽입, 삭제, 검색에 대한 시간 복잡도는 평균적으로 O(1)입니다. 하지만 최악의 경우에는 충돌(Collision)이 발생할 수 있어 O(n)이 될 수도 있습니다.
   - `std::unordered_set`은 순서를 보장하지 않습니다. 요소들은 해시값에 따라 정렬되어 있지 않습니다.

2. **`std::set`:**
   - `std::set`은 균형 이진 탐색 트리(Balanced Binary Search Tree)를 기반으로 한 자료구조입니다. 대개 레드-블랙 트리가 사용됩니다.
   - 균형 이진 탐색 트리는 요소를 정렬된 순서로 저장하여 검색, 삽입, 삭제에 대한 시간 복잡도가 평균적으로 O(log n)입니다.
   - `std::set`은 요소들을 정렬된 순서로 유지합니다. 따라서 `begin()`에서 `end()`까지 순회하면 정렬된 순서대로 요소에 접근할 수 있습니다.
   - `std::set`은 순서를 보장합니다.

따라서, 선택하는 자료구조는 사용하고자 하는 연산의 특성에 따라 달라집니다. 해시 테이블은 빠른 검색이 필요한 경우에 유용하며, 균형 이진 탐색 트리는 정렬된 순서로 요소에 접근해야 하는 경우에 유용합니다.

 

C++의 `std::unordered_set`과 `std::set`은 중복된 요소를 처리하는 방식에서 차이가 있습니다.

1. **`std::unordered_set`:**
   - `std::unordered_set`은 중복된 요소를 허용하지 않습니다. 삽입 시에 이미 동일한 키(요소)가 존재하는 경우, 해당 요소는 새로운 요소로 교체되지 않고 무시됩니다.
   - 이는 해시 테이블을 기반으로 하고 있기 때문에, 각 요소는 고유한 해시값을 가지며 중복된 값을 갖지 않습니다.
   - 예를 들어, 다음 코드에서 `unordered_set`에는 중복된 숫자 1이 하나만 남습니다.

     ```cpp
     #include <iostream>
     #include <unordered_set>

     int main() {
         std::unordered_set<int> mySet;
         mySet.insert(1);
         mySet.insert(2);
         mySet.insert(1);  // 중복된 1은 무시됨
         
         for (const auto& element : mySet) {
             std::cout << element << " ";
         }

         return 0;
     }
     ```

     출력: `1 2`

2. **`std::set`:**
   - `std::set`도 중복된 요소를 허용하지 않습니다. 키(요소)는 정렬된 순서로 유지되며, 이미 존재하는 키를 삽입하려고 할 때 해당 삽입은 무시됩니다.
   - 정렬된 이진 탐색 트리를 기반으로 하고 있으며, 중복된 값이 허용되지 않도록 설계되어 있습니다.
   - 예를 들어, 다음 코드에서 `set`에는 중복된 숫자 1이 하나만 남습니다.

     ```cpp
     #include <iostream>
     #include <set>

     int main() {
         std::set<int> mySet;
         mySet.insert(1);
         mySet.insert(2);
         mySet.insert(1);  // 중복된 1은 무시됨
         
         for (const auto& element : mySet) {
             std::cout << element << " ";
         }

         return 0;
     }
     ```

     출력: `1 2`

따라서, 어떤 경우든 중복된 요소는 삽입 시에 무시되며, 각 자료구조는 중복을 허용하지 않도록 설계되어 있습니다. 선택하는 자료구조는 다른 특성들에 따라 달라지므로, 사용하고자 하는 상황에 맞게 선택해야 합니다.

 

위의 내용을 잘 참고해서, 

set에 대해서 이해하자. 

이때에 중복을 허용해서 담을 수 있게 해주는 set은 multiset이다. 

unordered_multiset, multiset

 

이때에 unordered_set과 set의 경우 결국 내부 구현은 hash를 이용하는것과 rbtree를 이용하는 것의 차이점에 대해서 명확하게 이해를 하고 사용해야한다. 

 

추가적으로 다른 사람의 풀이들을 찾다보니 위의 문제를 dfs를 이용해서 푸는 형태의 코드도 발견하였는데, 

이렇게도 생각해볼 수 있을것같다. 

#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 8
using namespace std;

int gloN, res = MAX + 1;
void dfs(int number, int curNum, int cnt) {
    if( cnt > MAX ) return;
    else if( curNum == number ){
        res = min(res, cnt);
        return;
    }
    int n = 0;
    for(int i = 1;i<= 6;i++) {
        n = n*10 + gloN; 
        dfs(number, curNum + n, cnt + i);
        dfs(number, curNum - n, cnt + i);
       if(curNum != 0) {
        dfs(number, curNum * n, cnt + i);
        dfs(number, curNum / n, cnt + i);
       }
    }
}

int solution(int N, int number) {
    gloN = N;
    dfs(number,0,0);
    return (res == 9) ? -1 : res;
}

 

참고로 시간으로 따지면 훨씬 느리다. 

그래도 결국 해당 기능을 구현할 수 있는 코드는 방향성이 꼭 한가지는 아니라는것을 생각하고 문제를 접근하면 위와 같은 해결법도 떠올릴 수 있을것이다.