10주차 프로그래머스 2단계 3문제(숫자의 표현/최댓값과 최솟값/최솟값만들기)

이번주의 목표

요즘 다른 자격증 공부를 하느라 바쁘지만 그래도 쉬운 문제라도 감안떨어지게 매주 어떤식으로든 풀려고 한다. 이번주는 

숫자의 표현/최댓값과 최솟값/최솟값만들기 이렇게 세문제를 풀어보려고 한다. 9월부터는 좀더 본격적으로 어려운 문제들을 다시 풀어보려고 한다. 

 

 

숫자의 표현

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int n) {
    int answer = 0;
    int s = 0; 
    vector<int> a(1, 0); // a[0] = 0;
    for(int i = 1; i <= 10000; i++){
        s += i;
        a.push_back(s);
    }
    for(int i = n; i >= 1; i--){
        for(int j = i-1; j >= 0; j--){
            if(a[i] - a[j] == n){
                answer++;
                break;
            }else if(a[i] - a[j] > n){
                // 다음으로 가도 더 커지기 때문에, 사이값이 더 크면 브레이크
                break;
            }
        }
    }
    return answer;
}

1) 합의 누적을 구한다. 즉 a[0] = 0, a[1] = 1, a[2] = a[1] + 2, a[n] = a[n-1] + n

 

2) 그리고 n일때부터 포문을 반복하는데, 

각 루프에서는 a[i] - a[i-1] ,  a[i] - a[i-2], .... a[i] - a[1], a[i] - a[0] 을 체크한다.

이때 n과 같으면 경우를 찾은거라 1을 올리고 루프를 빠져나온다. 

 

3) 여기까지만 해도 정답은 다 맞지만 효율이 구리다.

조건을 하나 더 추가해서  a[i] - a[j] > n ( i > j >= 0) 이면 브레이크 한다. 왜냐하면 어차피 더 계산해봤자 값이 점점 커질거라 구할 필요가 없기 때문이다. 

 

최댓값과 최솟값

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

string solution(string s) {
    string answer = "";
    string cur = "";
    int flag = false;
    int mmax = 0; 
    int mmin = 0; 
    for(int i = 0; i < s.size(); i++){
        if(s[i] == ' '){
            // cout << cur << "\n";
            int temp = stoi(cur);
            if(flag == false){
                // 첨 대입
                mmax = temp;
                mmin = temp;
                flag = true;
            }else{
                if(mmax < temp){
                    mmax = temp;
                }
                if(mmin > temp){
                    mmin = temp;
                }
            }
            cur = "";
        }else{
            cur += s[i];
        }
    }
    // cout << cur << "\n";
    int temp = stoi(cur);
    if(mmax < temp){
        mmax = temp;
    }
    if(mmin > temp){
        mmin = temp;
    }
    // cout << mmin << " " << mmax;
    answer = to_string(mmin) + " " + to_string(mmax);
    return answer;
}

이건 글자짜리는게 귀찮았던 문제. 

 

 

 

최솟값만들기

풀이

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int s = A.size();
    for(int i = 0; i < s; i++){
        answer += (A[i] * B[s-i-1]);
        // cout << A[i] << " " << B[s-i-1] << "\n";
    }

    return answer;
}

이건 어려운가 했다가 정말 쉬운 문제란걸 좀있다 깨달았다. 

 

 

후기

이번주는 보안기사를 하느라 바쁜데, 이제야 프로그래머스의 2단계 문제가 진짜 2단계 수준이라 그래도 시간을 많이 쓰지 않고 간단히 세문제를 다 풀었다. 9월초까지는 이렇게라도 쉬운 문제라도 좀 풀다가, 고난도 문제로 다시 복귀해야겠다. 쉬운 문제를 쉽게 풀줄아는것도 중요하니 꾸준히 갈고 닦아야겠다. 

 

그래도 10주, 정확히는 3월 첫째주부터 꾸준히 알고리즘을 제대로 공부해오고 있어서 보람이 있다!!!