Interstellar555

Level1

 문제

정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.제한 조건

• arr은 길이 1 이상인 배열입니다.
• 인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다.

입출력 예

 풀이

문제의 설명에 빠진 부분이 있어서 조금 헤맸다.

설명에서 값만 제거하고 리턴하라거나 그대로 리턴해야한다던가의 제한조건같은게 없어서

풀이할때 sort를 이용해서 가장 마지막 값만 제거해서 풀었다.

위에 주어진 문제만 통과하고 테스트케이스는 전부 틀려서 당황스러웠다.

처음 풀이에는 sort문제라는것은 인지 못하고 제일 작은 수가 여러개 인경우의 예외처리를 하고 풀었다.

그래도 여전히 전부 틀리다고 나왔다.

다음 풀이에는 소스코드 처럼 주어진 배열내에서 제일 작은수만 넣지 않고 풀어서 해결했다.

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

using namespace std;

bool compare(int a, int b);

vector<int> solution(vector<int> arr) {
    vector<int> answer;
    if ( arr.size() == 1){
        answer.push_back(-1);
        return answer;
    }
        
    vector<int> dummy = arr;
    
    sort(arr.begin(), arr.end(), compare);
    
    int iMin = arr[arr.size()-1];
    for( int i = 0 ; i < dummy.size(); ++i ){
        
        if ( iMin != dummy[i]){
            answer.push_back(dummy[i]);
        }
    }
    
    
    return answer;
}


bool compare(int a, int b){
    
    return a>b;
    
}

다른사람의 풀이

min_element라는 함수로 접근해서 간단한 풀이

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

vector<int> solution(vector<int> arr) {
    if (arr.size() == 1) {
        return { -1 };
    }
    arr.erase(std::min_element(arr.begin(), arr.end()));
    return arr;
}

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

Level1

 문제

입출력 예

 풀이

문제를 읽고 표를 제대로 볼 수 있다면 쉽게 풀리는 문제이다.

표에서 명예의전당 부분을 1일차 2일차 나누어져있는 부분을 세로로 보지 않고,

가로로 보아서 값이 왜 이렇게 되어있는가 잘못된 생각을 했었다.

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

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    
    vector<int> vecTemp;
    int index = 0;
    while (  answer.size() < score.size() ){
    
        if (answer.size() < k ){
            vecTemp.push_back(score[index]);
            ++index;
        }
        else {
            
            if ( vecTemp[0] < score[index] ){
                vecTemp[0] = score[index];
            }
            ++index;
        }
        
        sort(vecTemp.begin(),vecTemp.end());
        
        answer.push_back(vecTemp[0]);
    }
    
    
    
    return answer;
}

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

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