Junnnho

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

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,

전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때

카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

programmers level2 카펫 문제입니다.

아주아주 단순한 문제입니다(?)

주어진 갈색 카펫의 수와, 노란 카펫의 수로 전체 카펫의 가로, 세로 크기를 알아내는 문제입니다

* 노란 카펫은 반드시 직사각형이 되어야 한다는 것. 이것만 아신다면 문제를 해결할 수 있을거라고 생각합니다.

주어진 노란카펫의 가로, 세로 높이를 임의의 수로 초기화 한 후에,

현재 가로, 세로 높이가 노란카펫을 직사각형으로 만들 수 있는지 없는지 확인해주시면서

갈색 카펫의 수를 예측해주시면 끝입니다.

저같은 경우 노란카펫의 높이를 1로 시작해서 찾아갔습니다.

간단한 규칙이 있다면 이정도겠네요

갈색카펫의 높이 중에서 위아래를 제외한 크기 = 세로카펫 높이*2

갈색카펫의 너비 = 세로카펫 너비 * 2 + 4

좀 더 자세한 설명은 주석을 적어놓았습니다~

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    // 카펫은 직사각형이라는 특징이 있으므로
    // 노란 카펫을 직사각형으로 만들어가면서, 갈색 카펫을 고려
    // => 노란 카펫의 높이가 1일때부터 고려해주면 된다
    
    int h = 1;
    int w = yellow;
    while(1){
        int bh, bw;
        // 갈색 카펫의 양쪽 높이의 위,아래 부분을 제외한 갯수는
        // 노란 카펫의 높이 * 2
        bh = h*2;
        
        // 갈색 카펫의 위아래 가로부분의 갯수는
        // 노란 카펫의 너비 * 2 + 4
        bw = w*2 + 4;
        
        if(bh + bw == brown){
            answer.push_back(bw/2);
            answer.push_back(bh/2+2);
            break;
        }
        else{
            // 노란 카펫의 갯수를 직사각형의 갯수에 맞게 조절해준다
            int check_h = h;
            int check_w = w;
            for(int i = 1; ; i++){
                if((check_h+i) * (yellow/(check_h+i)) == yellow){
                    h = check_h+i;
                    w = yellow/(check_h+i);
                    break;
                }
            }
        }
    }
    
    return answer;
}

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;
}