[프로그래머스 고득점 kit] N으로 표현 c++ (dp, 완전 탐색)

문제 링크

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

프로그래머스

 

문제해설

입력으로 N=3 이 주어지면, 사용할 수 있는 숫자는

3,33,333,.....,333333333( 최대 9개의 N사용 가능 ) 이다.

이 숫자들을 통해  사칙연산을 일정 횟수 수행하여 만들어지는 수들을 set에 저장해나간다.

여기서 "몇개의 N" 을 사용해서 구해지는지를 알아야 최소 값을 찾을 수 있기에, "몇개의 N으로 만들어진 수인가?" 에 대해서도 구해야한다.

처음에는 dp[숫자] 배열을 통해, 해당 숫자가 몇번만에 만들어졌는지를 구성했지만, 이 경우 해당 숫자가 배열 범위를 넘어갈 수 도 있다는 생각에 set 배열을 최대 연산 횟수인 9의 크기로 만들었다.

Set[i]: i개의 N으로 만들 수 있는 모든 수를 저장.

그리고 ' t1개의 N이 사용된 수'  와 ' t2개의 N이 사용된 수' 를 사칙연산하여 적절한 set에 추가해나가는 것으로 모든 가짓수를 찾은 뒤, 가장 적은 N으로 N을 찾을 수 있는 경우의 수를 리턴한다.

 

set
자동 정렬되는 컨테이너입니다. 키들을 저장하고, 이진 탐색 트리를 기반으로 합니다. 탐색 시간은 O( log n ) 입니다. 삽입과 제거가 빈번해지면 느립니다. 

undorderd_set
std::map과 동일한 문제로 나오게 되었습니다. 자동 정렬되지 않는 set이라고 생각하면 됩니다. 해쉬 테이블 기반으로 합니다. 탐색시간이 O(1) 이며 최악의 경우 O(n) 입니다. 버킷 때문에 메모리 사용량이 증가할 수 있습니다.

 

주의사항
set은 데이터가 정렬된 순서로 유지되어야 하기 때문에, 데이터를 삽입할 때마다 해당 데이터의 정렬된 위치를 찾기 위해 계속해서 탐색을 시도

 

 

    set<int> ss;
    ss.insert(-1);
    int cnt=1;
    for(auto ss1:ss){  //for문이 계속해서 insert 된 인덱스까지 탐색하려고 하기에 무한 루프 발생.
        printf("%d\n",ss1);
        ss.insert(cnt++);
    }

    set<int> ss;
    ss.insert(-1);
    int cnt=1;
    for(auto ss1:ss){  //for문이 insert된 1을 계속해서 탐색 x 이기에 1을 insert 후 종료
        printf("%d\n",ss1);
        ss.insert(cnt++);
    }

 

정답 코드

#include <string>
#include <vector>

#include<unordered_set>
using namespace std;
int solution(int N, int number) {
    int answer = 0;
    unordered_set<int> s[12];
    int num=N,mn=98765;
     for (int i = 1; i <= 9; i++) {
         s[i].insert(num);
         num = 10 * num + N;
     }
    int cnt=100;
    for(int t1=1;t1<=9;t1++){
            for(int t2=1;t2<=9;t2++){
                if(t1+t2>=9)break;
                 for(auto s1:s[t1]){
                    for(auto s2:s[t2]){
                        s[t1+t2].insert(s1+s2);
                        s[t1+t2].insert(s1*s2);
                        s[t1+t2].insert(s2-s1);
                        if(s1!=0)
                            s[t1+t2].insert(s2/s1);
                    }
                 }
            }
        
    }
    for(int i=1;i<=9;i++){
        if(s[i].find(number)!=s[i].end())return i;
    }
    return -1;

    return answer;
}