Junnnho

Programmers : https://programmers.co.kr/learn/courses/30/lessons/42841

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다.

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다.

그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자는 맞지만, 위치가 틀렸을 때는 볼

* 숫자와 위치가 모두 맞을 때는 스트라이크

* 숫자와 위치가 모두 틀렸을 때는 아웃

예를 들어, 아래의 경우가 있으면

A : 123 B : 1스트라이크 1볼.

A : 356 B : 1스트라이크 0볼.

A : 327 B : 2스트라이크 0볼.

A : 489 B : 0스트라이크 1볼.

이때 가능한 답은 324와 328 두 가지입니다.

질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때,

가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요.

programmers level2 숫자 야구 문제입니다.

숫자를 사용하는 범위가 매우 작기 때문에 모든 경우의 수를 고려해도 괜찮은 완전 탐색류에 해당하는 문제입니다.

가장 먼저, 비교해줄 수 있는 모든 숫자를 표현해주시고

현재 받은 숫자와 모든 숫자를 전부 비교해서 가능한 숫자만 추려내주시면 됩니다.

설명은 주석을 달아놓았으니, 보시면 이해되실 겁니다.

#include <string>
#include <vector>

using namespace std;

bool check_baseball(int k, int num, int s, int b) { // 두 숫자의 strike, ball을 판단
    int ss = 0, bb = 0;

    // 간편한 비교를 위해서 스트링을 사용했습니다.
    string kk = to_string(k);
    string numnum = to_string(num);

    for (int i = 0; i < 3; i++) {
        for (int k = 0; k < 3; k++) {
            // 만약 두 숫자가 같다면
            if (kk[i] == numnum[k]) {
                if (i == k) ss++; // 같은 인덱스인 경우 strike!
                else bb++; // 아닌 경우 ball!
            }
        }
    }

    if (s == ss && b == bb) return true; // 비교를 통해 가능한 숫자인지 판단해줍니다
    else return false;
}

int solution(vector<vector<int>> baseball) {
    int answer = 0;

    bool can_num[1000]; // 가능한 모든 숫자!
    for (int i = 0; i < 1000; i++) can_num[i] = false; // 일단 모두 사용 불가능으로 초기화했습니다.

    // 1~9까지 3자리 수를 만드는데
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            for (int k = 1; k <= 9; k++) {
                // 서로 중복되는 경우는 없기 때문에 다음과 같은 조건을 줍니다
                if (i == j || i == k || j == k) continue;
                // 조건에 부합하지 않는다면 이 수는 사용가능한 숫자겠네요!
                can_num[i * 100 + j * 10 + k] = true;
            }
        }
    }

    for (int i = 0; i < baseball.size(); i++) {
        // 질문을 가지고 와서
        int num = baseball[i][0];
        int s = baseball[i][1];
        int b = baseball[i][2];

        for (int k = 111; k < 1000; k++)
            // 만약 현재 숫자가 비교가능한 숫자면 check_baseball 함수를 통해 비교해줍니다
            if (can_num[k]) can_num[k] = check_baseball(k, num, s, b);
    }

    for (int i = 111; i < 1000; i++) if (can_num[i]) answer++; // true인 모든 숫자가 경우의 수가 됩니다.

    return answer;
}

Programmers : https://programmers.co.kr/learn/courses/30/lessons/42839

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

programmers level 2 소수찾기 문제입니다.

예를 들어서 문제를 설명하겠습니다.

예제에 있는 "17"의 경우 1, 7을 이용해서 수를 만들 수 있고

이 때 소수를 만들 수 있는 경우는 7, 17, 71 이렇게 3가지입니다.

결국 String이 주어지면 각 자릿수를 이용해서 모든 수를 조합해보고, 소수를 만들 수 있는 경우가 몆개냐! 를 묻습니다.

이 문제를 풀기 위해서 에라토스테네스의 체 알고리즘을 사용했습니다.

이정도 알고리즘은 기본 중의 기본이니 꼭 사용할 줄 아셔야합니다.

(에라토스테네스 :  https://junho0956.tistory.com/35)

좀 더 소수에 근접하게 수를 빠르게 만들 수 있는 방법이 있을까 고민해봤는데.. 떠오르질 않더라구요

그래서 완전탐색과 같이 모든 경우의 수에 접근했습니다.

저는 DFS를 이용해서 아래와 같이 접근했습니다! (백트래킹 이라고 할 수 있겠네요)

dfs(현재까지 만든 수, 더 사용할 수 있는 수)

dfs 과정마다 현재까지 만든 수를 소수인지 확인해주는 작업을 꼭 해주시고,

같은 수가 중복될 수 있으니 찾은 숫자는 따로 처리해주세요!

설명은 주석을 달아놓았으니, 보시면 바로 이해되실껍니다~

#include <string>
#include <vector>
#include <iostream>
#define e7 10000000 // e7 : 1e7이 사용이 안되서 만들었어요. 1천만 입니다
using namespace std;

bool sosu[e7]; // 소수는 e7까지 접근가능합니다
bool find_it[e7]; // 소수를 찾은 경우 사용했음을 나타내기 위해 사용합니다
bool use[7]; // 각 자리수에 접근할 녀석이에요
string str; // 스트링은 전역으로 사용했습니다

void make_eratos() { // 에라토스테네스의 체
    for (int i = 2; i < e7; i++) sosu[i] = true;
    for (int i = 2; i * i < e7; i++)
        if (sosu[i])
            for (int k = i * i; k < e7; k += i) sosu[k] = false;
}

int dfs(int make_num, int able) { // 탐색부분
    // 더이상 사용할 수 있는 수가 없으면 소수인지 바로 판단해주세요
    if (!able) {
        if (sosu[make_num]) {
            if (find_it[make_num]) return 0;
            find_it[make_num] = 1;
            return 1;
        }
        else return 0;
    }
    
    int ret = 0;
    // 항상 현재까지 만든 수가 소수인지 확인하는 작업!
    if (sosu[make_num] && !find_it[make_num]) find_it[make_num] = 1, ret++;

    for (int i = 0; i < str.size(); i++) { // 모든 수에 접근합니다.
        if (!use[i]) { // i번째 자리수를 사용안했다면?
            int join_num = make_num; // 새로운 수를 만들어주세요
            join_num *= 10;
            join_num += str[i] - '0';
            use[i] = 1; // 이 자리를 사용했음을 나타냅니다
            ret += dfs(join_num, able - 1);
            use[i] = 0; // 이 자리의 사용이 끝났음을 나타냅니다
        }
    }

    return ret;
}

int solution(string numbers) {

    str = numbers;
    make_eratos(); // 일단 소수부터 만들게요
    return dfs(0, numbers.size());

}

programmers : https://programmers.co.kr/learn/courses/30/lessons/42629#qna

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

Level 2 <Heap> 라면공장 문제입니다.

이 문제 처음에는 정말 어렵더라구요..

어떻게 하면 밀가루를 최소한의 횟수로 공급받으면서 K 날짜가 될때까지 버틸 수 있을까

이 문제를 풀기 위해서 dfs로 재귀를 돌려보다가 DP까지 적용시켜서 시도해봤는데 모두 실패했습니다.

그러다가 문제가 heap 분류에 있었다는 것을 떠올렸고

대체 어떻게? heap으로 이 문제를 푸는거지 생각해봤는데

다시보니 되게 간단하더라구요.. 너무어렵게 생각했었습니다.

현재 날짜를 today라고 하면, 이 today가 될때 까지 사용한 밀가루가 있을테고 공급받은 밀가루도 있을 것입니다.

밀가루 양 상관없이 K날짜까지 버틸 수 있는 최소한의 공급횟수!

==> 오늘 날짜인 today까지를 기준으로 받을 수 있는 공급 밀가루를 최대한 많은 순서로 받으면 되는 것이였습니다.

즉 오늘날짜가 만약 4일이다.

=> 4일까지 공급받을 수 있는 밀가루를 heap에 저장해두시구요

heap중에서 가장 큰 밀가루 값을 꺼내서 이 밀가루 양만큼 최대한 버텨주면 되는겁니다.

만약 꺼낸 밀가루 양이 20이라면, 24일까지는 버틸 수 있는 얘기고 -> 4일~24일까지 오는 날짜에 받을 수 있는 밀가루를 또 heap에 저장 --> heap에서 가장 큰 값 꺼내기! --> 반복..

참고로 K 날짜가 되는 날 아침을 기준으로 하기때문에 K날짜인 아침날 stock가 0이 되어도 괜찮다는건

문제를 읽으셨다면 아실꺼라고 생각합니다.

이게 무슨뜻이냐.. K-1날짜까지만 버텨주면 된다. 라는 의미가 되겠네요

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {

    priority_queue<int, vector<int>, less<int> > q;

    int cnt = 0; // 공급받을 횟수!
    int s = 0; // 어떤 인덱스(공급날짜)부터 검색할 것인지를 위해
    int today = stock; // 오늘날짜는 0일부터 시작하기 때문에 stock를 더해서 시작해주면 되겠네요

    while (today < k) {
        // s(공급날짜 시작일의 인덱스)부터 today를 비교해가며 공급받을 수 있는 날을 heap에 저장
        for (int i = s; i<dates.size(); i++, s++) { // s날짜는 조건에만 부합하다면 항상 +1씩 증가하겠네요!
            if (dates[i] <= today) q.push(supplies[i]);
            else break;
        }
        cnt++;
        today += q.top(); // 버틸수있는 날짜를 더해줍니다
        q.pop();
    }

    return cnt;
}

programmers : https://programmers.co.kr/learn/courses/30/parts/12263

programmers DP(동적계획법) level3 N으로 표현 문제입니다.

원래 dp 문제를 풀때 최적화되는 과정을 생각해보고

최적화를 위한 코드를 짜는게 맞긴한데

이 문제는 dp문제지만 어떤식으로 최적화를 해야되는건지 솔직히 모르겠다.

그래서 평소 dp문제를 풀 때 처럼 재귀로 문제를 풀었지만, 최적화..는 하지 못했다.

만약 dp를 제대로 풀기 위한 최적화방법을 고려해본다면..

N으로 만들 수 있는 모든 수 N,NN,NNN,NNNN,... 을 미리 8자리까지 만들어놓고

음.. dp[a][b] 의 2차원형태로 접근해본다면

a는 위에 미리 만들어놓은 값들, b는 만들어낼 수 있는 값들 (0~?????)

dp[a][b] 는 cnt 가 되겠다.

사실 문제풀때는 N을 8번 사용하라는 얘기 때문에 반복문을 8까지 돌렸는데

생각해보면 표현할 범위의 최대가 32000 이기 때문에

아무리 큰 숫자를 만든다고 해도 32000을 9로 곱한 수 인 288000 가 확인해볼 최댓값이 되겠다.

결국 8까지 돌려볼 필요도 없고, 최대 6자리까지만 만들어봐도 이 문제를 해결하는데 문제 없을 것 같았다.

 그래서 반복문을 6까지만 돌려 실행시켜봤는데 역시 AC를 받았다.

문제에 대한 설명은 코드에 있다