Interstellar555

Level1

 문제

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

• 한 상자에 사과를 m개씩 담아 포장합니다.
• 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

• (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
  • 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

 풀이

문제만 잘이해하면 어렵지 않게 풀 수 있다.

중간에

• (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

이 문장이 모든걸 설명해줘서 처음 글을 읽었을때는 최고품질의 k를 알려주면서 왜 최저를 이용하는가 고민에 빠졌지만

복잡하게 접근할 필요가 없었던 문제였던거 같다.

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

using namespace std;

int solution(int k, int m, vector<int> score) {
    int answer = 0;
    sort(score.begin(), score.end());
    
    while ( score.size() >= m ){
        vector<int> vecTemp;
        for( int i = 0; i < m; ++i ){
            
            vecTemp.push_back(score[score.size()-1]);
            score.pop_back();
        }
        sort(vecTemp.begin(), vecTemp.end());
        
        answer += vecTemp[0] * m;
    }
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/135808

Level1

 문제

입출력 예

 풀이

일반적인 로또와 같이 당첨되는 룰을 가지고 있다.

0의 갯수를 눈여겨봐야한다는걸 바로 캐치하면 쉽게 풀리는 문제였다.

#include <string>
#include <vector>

using namespace std;
int getRank(int a);
vector<int> solution(vector<int> lottos, vector<int> win_nums) {
    vector<int> answer;
    
    int correctCnt = 0;
    int zeroCnt = 0;
    for ( int i = 0 ; i < win_nums.size(); ++i ){
     
        for ( int j = 0 ; j < lottos.size(); ++j ){
            
            if ( win_nums[i] == lottos[j]){
                ++correctCnt;
                break;
            }
        }
    }
    
    for ( int j = 0 ; j < lottos.size(); ++j ){
            
            if ( lottos[j] == 0){
                ++zeroCnt;
            }
    }
    
    
    answer.push_back(getRank(correctCnt+zeroCnt));
    answer.push_back(getRank(correctCnt));
    
    return answer;
}

int getRank (int a ){
    switch(a){
        case 0:
        case 1:
            return 6;
            
        case 2:
             return 5;
            
        case 3:
             return 4;
            
        case 4:
             return 3;

        case 5:
            return 2;

        case 6:
            return 1;  
    }
    
}

다른사람의 풀이

int func(int n){
    if(n == 6) return 1;
    else if(n == 5) return 2;
    else if(n == 4) return 3;
    else if(n == 3) return 4;
    else if(n == 2) return 5;
    else return 6;
}

vector<int> solution(vector<int> lottos, vector<int> win_nums) {
    vector<int> answer;

    // 0의 갯수를 담는 변수
    int zero = 0;
    for(int i = 0; i < lottos.size(); i++){
        if(lottos[i] == 0) zero++;
    }

    // lottos와 win_nums에서 일치하는 번호 갯수를 담는 변수
    int check = 0;
    int visited[6] = {0,};
    for(int i = 0; i < lottos.size(); i++){
        for(int j = 0; j < win_nums.size(); j++){
            if(visited[i] == 0 && lottos[i] == win_nums[j]){
                visited[i] = 1;
                check++;
            }
        }
    }

    answer.push_back(func(zero+check));
    answer.push_back(func(check));
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/77484?language=cpp

Level1

 문제

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 1 ≤ b < a ≤ n ≤ 1,000,000
• 정답은 항상 int 범위를 넘지 않게 주어집니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 빈 병 20개 중 18개를 마트에 가져가서, 6병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 8(20 – 18 + 6 = 8)개 입니다.
• 빈 병 8개 중 6개를 마트에 가져가서, 2병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 4(8 – 6 + 2 = 4)개 입니다.
• 빈 병 4 개중 3개를 마트에 가져가서, 1병의 콜라를 받습니다. 이때 상빈이가 가지고 있는 콜라 병의 수는 2(4 – 3 + 1 = 2)개 입니다.
• 3번의 교환 동안 상빈이는 9(6 + 2 + 1 = 9)병의 콜라를 받았습니다.

 풀이

b값을 고려하고 푼다면 쉽게 해결된다.

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    
    bool loopState = true;
    int tempA =n;// 받게되는 콜라
    int tempB =0;// 남은 빈병
    while (loopState){
        
        
        int tempC = tempA;
        tempA = (tempC/a)*b;
        tempB = tempC%a;
        
    
        answer += tempA;
        
        if ( (tempB + tempA) < a ){
            loopState = false;    
        }
        else {
            tempA += tempB;
        }
        
    }
    
    
    return answer;
}

다른사람의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    while(n >= a){
        answer += n/a*b;
        n = n - n/a*a + n/a*b;
    }

    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/132267

Level1

 문제

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.[제한사항]

• board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

 풀이

처음 접근은 배열 값들이 세로로 들어가는 것으로 이해해서 접근하여 실패하는 것을 확인한뒤 문제를 다시 확인하고 접근.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> vecDummy;
    for ( int i = 0 ; i < moves.size(); ++i ){
        
        int boardNum = moves[i];
        
        //cout<<board[boardNum].pop_back();
        int boardData = board[boardNum-1].back();
         board[boardNum-1].pop_back();
         if( boardData == 0)
             continue;

         vecDummy.push_back(boardData);
        cout<<boardData;
         int size = vecDummy.size();
        if ( vecDummy.size() > 0 && vecDummy[vecDummy.size()-1] == boardData ) {
            
            //vecDummy.pop_back();
            //vecDummy.pop_back();
            ++answer;
        }
        
        
        //for ( int i = 0 ; i )
        
        
        
    }
    
    return answer;
}

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> vecDummy;
    for ( int i = 0 ; i < moves.size(); ++i ){
        int boardIndex = moves[i] -1;
        int boardData = 0;
        for(int j=0; j <board.size(); ++j){
            
            if ( board[j][boardIndex] == 0)
                continue;
            
            boardData = board[j][boardIndex];
            board[j][boardIndex] = 0;
            break;           
        }
        if ( vecDummy.size() > 0 && vecDummy[vecDummy.size()-1] == boardData ){
            vecDummy.pop_back();
            answer += 2;
        }
        else if ( boardData > 0 ) {
            vecDummy.push_back(boardData);    
        }
    }
    
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/64061?language=cpp

Level1

 문제

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

입출력 예

입출력 예 설명

입출력 예 #1

1부터 5까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2]개입니다. 모두 공격력 제한 수치인 3을 넘지 않기 때문에 필요한 철의 무게는 해당 수들의 합인 10이 됩니다. 따라서 10을 return 합니다.

입출력 예 #2

1부터 10까지의 약수의 개수는 순서대로 [1, 2, 2, 3, 2, 4, 2, 4, 3, 4]개입니다. 공격력의 제한수치가 3이기 때문에, 6, 8, 10번 기사는 공격력이 2인 무기를 구매합니다. 따라서 해당 수들의 합인 21을 return 합니다.

 풀이

처음 단순하게 하나씩 전부 접근했더니 시간초과가 되었다.

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for ( int i = 1; i <= number; ++i ){
        
        int cnt = 1;
        for ( int j = 1; j < i; ++j ){
        
            if ( i % j == 0){
                ++cnt;
            }
            
        }
        
        if ( cnt > limit){
            cnt = power;
        }
        answer += cnt;
        
        
    }
    return answer;
}

약수의 갯수를 직접 손으로 체크도 해보고 인터넷 글도 확인해보니 N/2값 보다는 크지 않다는 접근하게 되어 반복문을 절반 돌리니 해결되었다.

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

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for ( int i = 1; i <= number; ++i ){
        
        int cnt = 1;
        for ( int j = 1; j <= i/2; ++j ){
            if ( i % j == 0){
                ++cnt;
            }
        }
        
        if ( cnt > limit){
            cnt = power;
        }
        answer += cnt;
        
        
    }
    return answer;
}

다른사람의 풀이

코드도 깔끔하고 속도도 더빠른 다른사람의 풀이가 있었다.

using namespace std;

int count(int n) {
    int cnt = 0;
    for(int i=1; i*i<=n; i++) {
        if(n%i) continue;
        if(i*i == n) cnt += 1;
        else cnt += 2;
    }
    return cnt;
}

int solution(int number, int limit, int power) {
    int acc = 0;
    for(int n=1; n<=number; n++) {
        int cnt = count(n);
        acc += (cnt > limit ? power : cnt);
    }
    return acc;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/136798

Level1

 문제

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

입출력 예

 풀이

아래 처럼 단순히 두개의 string 배열을 다 접근하게 되면은 시간초과가 되어버린다.

	if( Y.size() > X.size() ){
        string temp;
        temp = X;
        X = Y;
        Y = temp;
	}

	for ( int i = 0; i <= 9; ++i){
        while ( X.find(to_string(i))  != string::npos && Y.find(to_string(i))  != string::npos ){
            X.replace(X.find(to_string(i)), 1, "");
            Y.replace(Y.find(to_string(i)), 1, "");
            answer.append(to_string(i));
        }
        
	}
    
    
//     for( int i = 0 ; i < Y.size(); ++i){ 
//         if ( X.find(Y[i]) != string::npos){
//             X.replace(X.find(Y[i]), 1, "");
//             string a;
//             a += Y[i];
//             answer.append(a);
//         }       
//     }

    sort(answer.begin(),answer.end());
    reverse(answer.begin(),answer.end());
 
    if ( answer.empty()){
     answer = "-1";
    }
    else if (answer[0] == '0' ){
        answer = "0";
    }

시간초과가 되어 방식을 바꾸어서 접근을 했다.

먼저 각 스트링 배열을 정렬하여 접근하기로했다.

한번 돌면서 두개를 동시에 체크하기로했다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string solution(string X, string Y) {
    
    string answer = "";

    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    
    int indexX = 0;
    int indexY = 0;

    int loopState = true;
    
    while ( loopState ){
        
        if ( (X.size()<=indexX) || (Y.size()<=indexY)){
            break;
        }
        
        if ( X[indexX] == Y[indexY] ){
            answer+= X[indexX];
            ++indexX;
            ++indexY;
        }
        
        else if ( X[indexX] > Y[indexY] ){
            ++indexY;
        }
        
        else if ( X[indexX] < Y[indexY] ){
            ++indexX;
        }

    }

    sort(answer.begin(),answer.end());
    reverse(answer.begin(),answer.end());

    if ( answer.empty()){
     answer = "-1";
    }
    else if (answer[0] == '0' ){
        answer = "0";
    }
    
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/131128

Level1

 문제

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

제한사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

입출력 예

 풀이

문제를 이해하는데 시간이 조금 걸렸다.

문제를 이해하면 쉽게 풀리는 문제였다.

입출력 banana를 예로 들면

문제 첫글자 x는 b가 된다.

다음 x가 아닌 다른글자라는건 a가되고

두 문자열의 길이가 같아지는 순간 멈추는 조건이니

x에 들어간 b가 1

x가 아닌 a가 1이므로 ba로 분리

분리가 되었으므로 다시 처음 작업부터

x = n

x가 아닌 다른글자 a 

둘다 카우트가 1이 되므로 na로 분리 하는식으로 진행

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    int iX = 0;
    int iY = 0;
    char chX;
    
    for ( int i = 0; i < s.size(); ++i){
    
            if ( iX == 0 ){
               chX = s[i];
            }
             if ( s[i] == chX ){
                ++iX;
            }
        else{
            ++iY;
        }
        
        
        
        if ( iX == iY){
            iX = 0;
            iY = 0;
            ++answer;
        }
        
        
    }
    
    if ( iX != iY)
        ++answer;
    
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/140108

Level1

 문제

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

제한사항

• 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

입출력 예

 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    
    for (int i = 0 ; i < s.size(); ++i){
    
        
        int index = -1;
        for (int j = i-1 ; j >= 0; --j){
        
            if ( s[i] == s[j]){
                index = i - j;
                 break;
            }
        }
        answer.push_back(index);
        
    }
    return answer;
}

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/142086?language=cpp#