프로그래머처럼 생각하기

• 폰켓몬

문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

numsresult

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 3번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

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

int solution(vector<int> nums){
    int answer = 0;
    unordered_map<int, int> map;
    int half = nums.size()/2;
    
    for(int i=0; i<nums.size(); i++){
        map[nums[i]]++;
    }
    
    if(half >= map.size()){
        answer = map.size();
    } else {
        answer = half;
    }
    
    return answer;
}

unordered_map을 활용해서 푼 문제입니다

• 약수의 개수와 덧셈

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

leftrightresult

입출력 예 설명

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

#include <string>
#include <vector>

using namespace std;

int solution(int left, int right) {
    int answer = 0;
    vector<int> check(right+1);
    for(int i=left; i<=right; i++){
        for(int divisor=1; divisor<=right; divisor++){
            if(i%divisor == 0){
                check[i]++;
            }
        }
        if(check[i]%2 == 0){
            answer += i;
        } else {
            answer -= i;
        }
    }
    
    return answer;
}

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예

nresult

입출력 예 설명

입출력 예 #1

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현

• 따라서 7을 return 해야 합니다.

입출력 예 #2

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현

• 따라서 229를 return 해야 합니다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(int n) {
    int answer = 0;
    stack<int> s;
    while(n>0){
        s.push(n%3);
        n = n/3;
    }
    
    int reverse_base3 = 1;
    while(!s.empty()){
        int top = s.top();
        s.pop();
        answer = answer + top*reverse_base3;
        reverse_base3 *= 3;
    }
    
    return answer;
}

하나하나 함수구현을 했는데 다른분 답을보니 쉽게 하셧더라구요 ㅠ

카펫

문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown    yellow    return

출처

※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다.
※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.

우리는 언제나 문제에 마주하면 "어떻게 해야할까?" 를 먼저 생각해야합니다.

처음으로 눈에 띈것은 예제에
brown + yellow = return갑의 0번째 * 1번째 라는 규칙이 있습니다.

#include <string>
#include <vector>
#include <math.h>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int carpet = brown + yellow;
    
    for(int i=2; i<=carpet; i++){
        if(carpet % i == 0){
            if(i >= floor(carpet/i)){
                answer.push_back(i);
                answer.push_back(carpet/i);
                break;
            }
        }
    }
    return answer;   
}

첨엔 이런식으로 풀이를 생각했지만 테스트케이스 4, 6, 7에서 실패가 납니다.

만약 brown = 22, yellow = 8인 경우

ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
ㅁㅇㅇㅇㅇㅇㅇㅇㅇㅁ
ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ
[10, 3]이 돼야하는데 

ㅁㅁㅁㅁㅁㅁ
ㅁㅁㅇㅇㅁㅁ
ㅁㅁㅇㅇㅁㅁ
ㅁㅁㅇㅇㅁㅁ
ㅁㅁㅁㅁㅁㅁ

[6, 5]이런식으로 되기 때문입니다

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int carpet = brown + yellow;
    
    for(int i=2; i<=carpet; i++){
        if(carpet % i == 0){
            int width = i;
            int height = carpet/i;
            if(width >= height){
                if((width-2) * (height-2) == yellow){
                    answer.push_back(i);
                    answer.push_back(height);
                    break;
                }
            }
        }
    }
    return answer;   
}

검색결과 width와 height이름으로 하는것이 더 깔끔하고 직관적으로 보여서 변수를 선언하고
위에서 말한듯 우리는 상하좌우 brown을 각 1칸씩 즉 상하에 2 좌우에 2를 빼고 곱한값이 yellow와 같다면 우리가 찾는 답을 얻을 수 있습니다.

어떤분들은 첫 for문에서 i=carpet/2로 시작하고 i를 빼면서 하시던데 이렇게 해도 시간은 잘 나오기에 저는 증가식으로 했습니다.

예외적인 테스트케이스로 어려움을 겪는것... 예상치 못한 변수나 상황들이 당황케하는데 코테 문제풀이는 마치 우리네 인생이 아닐까요?

모의고사

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answersreturn

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> student1 = {1, 2, 3 , 4, 5};
    vector<int> student2 = {2, 1, 2, 3, 2, 4, 2, 5};
    vector<int> student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    int answer1=0, answer2=0, answer3=0;
    
    for(int i=0; i<answers.size(); i++){
        if(answers[i] == student1[i%student1.size()]) answer1++;	// 0~4
        if(answers[i] == student2[i%student2.size()]) answer2++;	// 0~7
        if(answers[i] == student3[i%student3.size()]) answer3++;	// 0~9
    }
    
    int maxCount = max(answer1, max(answer2, answer3));	
    //max를 사용하기위해 cmath 헤더추가
    
    if(maxCount == answer1) answer.push_back(1);
    if(maxCount == answer2) answer.push_back(2);
    if(maxCount == answer3) answer.push_back(3);
    
    return answer;
}

// 프로그래머스 최다추천 답안
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> one = {1,2,3,4,5};
vector<int> two = {2,1,2,3,2,4,2,5};
vector<int> thr = {3,3,1,1,2,2,4,4,5,5};

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> they(3);
    for(int i=0; i<answers.size(); i++) {
        if(answers[i] == one[i%one.size()]) they[0]++;
        if(answers[i] == two[i%two.size()]) they[1]++;
        if(answers[i] == thr[i%thr.size()]) they[2]++;
    }
    int they_max = *max_element(they.begin(),they.end());
    for(int i = 0; i< 3; i++) {
        if(they[i] == they_max) answer.push_back(i+1);
    }
    return answer;
}

아무래도 나의 답과의 차이라하면
1. 정답에대한 카운트를 나는 각각 하나씩 int형으로 받은것과 추천답안에서는 vector로 받은 것
2. cmath 안 max 사용과 *max_element
3. 각 하나씩 if문을 사용한것과 마지막 if문을 for문안에 넣어서 보다 깔끔히 표현한것

첨엔 자바로 풀어서 사실 cpp문법으로 거의 옮겨쓴것과 다를바 없지만 이 코드에서는 아무래도 

for(int i=0; i<answers.size(); i++){
        if(answers[i] == student1[i%student1.size()]) answer1++;	// 0~4
        if(answers[i] == student2[i%student2.size()]) answer2++;	// 0~7
        if(answers[i] == student3[i%student3.size()]) answer3++;	// 0~9
    }

이 부분이 가장 중요한것 같다.