[프로그래머스/Lv3] N으로표현_C++

[프로그래머스/Lv3] N으로표현_C++

---

문제 내용

• 숫자 A를 숫자 B로만 구성된 숫자의 사칙연산으로 표현한다.
  
• 표현하는 과정에 사용되는 B의 사용횟수를 구해야 한다.
  

입출력 예

• • 입력: 5
    

  • 출력: 12
    

    12 = ( 55 + 5 ) / 5

• • 입력: 2
    

  • 출력: 11
    

    11 = 22 / 2

문제 풀이

• 가독성을 위해 주석으로도 설명하겠다.
  
• N,NN,NNN… 이 방식의 수열을 string->int 을 이용해서 수열을 담는 배열을 생성한다.
  
• 이 숫자들을 통해 만들어 질 수 있는 조합들을 배열에 넣어 줄 것이다.
• 여기서 배열이 중요한데 배열은 중복되어 생성되는 숫자를 담을 필요가 없으니 set을 이용한다.
  
  • set은 insert만 되어도 알아서 중복를 제외 시키고 정렬시킨다.
    
• 그래서 생성되는 vector는 각각의 set을 가지고 있고 set은 초기에 [n] , [nn] , [nnn]… 식으로 가지고 있는다
  
• 여기서 vector의 index는 N의 count의 기준이 될 것이며, 전 인덱스 상에서느 사칙연산된 결과를 다음 set에 insert한다
  
  • 다음 set에 insert한 이유는 연산시에 나온 결과는 N을 중복하여 사용한 결과 이기 때문에 count 증가를 위해 다음 set에서 발견 되어야 한다.
    
• end까지 4중 for문을 반복하며 count의 갯수를 찾아준다.
  

풀이 CODE

#include <string>
#include <vector>
#include <set>
#include <math.h>
#include <iostream>
using namespace std;

int solution(int N, int number) {
    vector<set<int>> arr(8);
    string num = to_string(N);
    string new_num =num;
    for(int i=0; i<8;i++){  // [[N],[NN],[NNN],[NNNN]......] 이런식으로 넣어 줄꺼임
        arr[i].insert(stoi(new_num));   // 숫자로 바꿔 set에 넣어준다.
        new_num += num;      // 문자열로 쉽게 더해주고       
    }
    
    if(N == number)  // N과 number이 같은경우 예외 처리 해준다.
       return 1;     // 밑에 for 문에서는 [0,1] 조합에 의해 N이 [2] 인덱스에 처음 생성되어서 오류가 생긴다.
    
    
    // set 이기 때문에 알아서 중복은 사라짐
    for(int i=1; i<8; i++){    // count의 기준이 되는 곳 -> i=1 -> NN i=2 -> NNN
        for(int j=0; j<i; j++){ 
            for(auto &x : arr[j]){    // set을 돌면서 새로운 조합을 추가 해 줄것이다.
                for(auto &y : arr[i-j-1]){                // [0,0] 인덱스 조합해 [1] 인덱스에 넣어줌
                    arr[i].insert(x+y);                 // [0,1] [1,1] 인덱스 조합해서 [2] 인덱스에
                    arr[i].insert(x*y);                 // .....
                    arr[i].insert(x-y); 
                    if(y !=0) arr[i].insert(x/y);       // set은 인덱스로 따로 접근이 어려워 iter로 접근
                }
            }
        }
        if (arr[i].find(number)!= arr[i].end()) // set은 찾지 못하면 end를 뱉음
            return i+1;          // 처음에 N 1개를 무조건 가지고 있으므로
    }
   
     
    return -1; // 예외적일 경우 -1 반환

}