[프로그래머스] Lv.1 문제 PART 15(C++)

프로그래머스 코딩 테스트 : Lv.1 문제(C++)

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&page=3&languages=cpp&levels=1

코딩테스트 연습 | 프로그래머스 스쿨

---

프로그래머스 Lv.1 문제 : [1차] 비밀지도

https://school.programmers.co.kr/learn/courses/30/lessons/17681

프로그래머스

---

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다.

그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다.

다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

---

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

---

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

---

입출력 예

---

코드

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

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    
    for (int i = 0; i < n; i++) {
        int num = pow(2, n - 1);
        string temp = "";
        
        while (num > 0) {
            bool iswall = false;
            
            if (arr1[i] >= num) {
                arr1[i] %= num;
                iswall = true;
            }
            if (arr2[i] >= num) {
                arr2[i] %= num;
                iswall = true;
            }
            
            if (iswall)
                temp += "#";
            else
                temp += " ";
            
            num /= 2;
        }
        
        answer.push_back(temp);
    }
    
    return answer;
}

// 다른 사람의 풀이 1 : 비트 연산자를 사용해서 해결하는 방법

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for(int i=0; i <n; i++){
        arr1[i] = arr1[i]|arr2[i];
        string ans = "";
        for(int j = 0; j<n; j++){
            if(arr1[i] % 2 == 0) ans = " " + ans;
            else ans = "#" + ans;
            arr1[i] = arr1[i] >> 1;
        }
        answer.push_back(ans);
    }
    return answer;
}

// 다른 사람의 풀이 2 : insert까지 사용해서 해결하는 방법

#include <string>
#include <vector>
std::vector<std::string> solution(int n, std::vector<int> arr1, std::vector<int> arr2) {
    std::vector<std::string> answer(n, "");
    for(int i = 0; i < arr1.size(); i++) {
        int temp = arr1[i] | arr2[i];
        int w = n;
        while(w--) {
            answer[i].insert(0, (temp % 2) ? "#" : " ");
            temp >>= 1;
        }
    }
    return answer;
}

---

결과

---

프로그래머스 Lv.1 문제 : 콜라 문제

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

프로그래머스

---

문제 설명

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.
콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?
단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다.

상빈이가 푼 방법은 아래 그림과 같습니다.

우선 콜라 빈 병 20병을 가져가서 10병을 받습니다.

받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다.

5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다.

받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다.

이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다.

이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다.

기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다.

상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다.

상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다.

상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

---

제한사항

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

---

입출력 예

입출력 예

입출력 예 설명

---

코드

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    
    while (n >= a) {
        int num1 = n / a;
        int num2 = n % a;
        
        answer += num1 * b;
        
        n = num1 * b + num2;
    }
    
    return answer;
}

// 다른 사람의 풀이 1 : 삼항 연산자로 해결하는 방법

int solution(int a, int b, int n) {
    return (n > b ? n - b : 0) / (a - b) * b;
}

// 다른 사람의 풀이 2 : 좀 더 단순하게 해결하는 방법

#include <string>
#include <vector>

using namespace std;

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

---

결과

---

프로그래머스 Lv.1 문제 : 명예의 전당 (1)

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

프로그래머스

---

문제 설명

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다.

매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다.

즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다.

k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다.

예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

---

입출력 예

입출력 예

입출력 예 설명

---

코드

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

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> temp;
    int min;
    
    for (auto num : score) {
        temp.push_back(num);
        
        sort(temp.begin(), temp.end());
        
        if (temp.size() > k)
            min = *min_element(temp.end() - k, temp.end());
        else
            min = *min_element(temp.begin(), temp.end());
        
        answer.push_back(min);
    }
    
    return answer;
}

// 다른 사람의 풀이 1: erase를 사용해서 해결하는 방법

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

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer, tmp;

    for(auto s : score){
        tmp.push_back(s);
        sort(tmp.begin(), tmp.end(), greater<int>());
        if(tmp.size() >= k) tmp.erase(tmp.begin() + k, tmp.end());
        answer.push_back(tmp.back());
    }

    return answer;

}

// 다른 사람의 풀이 2 : 우선순위 큐를 사용해서 해결하는 방법

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

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> rank;
    for(int i = 0; i < score.size(); i++){
        if(i < k) rank.push(score[i]);
        else{
            if(rank.top() <= score[i]){
                rank.pop();
                rank.push(score[i]);
            }
        }
        answer.push_back(rank.top());
    }
    return answer;
}

---

결과

---

여담

이번 문제들은 조금 난이도가 있었던 것 같고 아쉬운 점도 많다.

첫 번째 문제는 비트 연산자를 아예 생각 못했던 점, 그리고 마지막 문제에서 큐까지는 생각했다가 우선 순위 큐를 생각 못하고 결국 벡터로 돌아서 min_element로 억지로 해결했던 점이 아쉬웠다.

조금 더 쉽게, 간결하고 이쁘게 해결할 수 있는 문제들을 조금 돌아 돌아서 풀었던 것같아서 참 아쉽다.

갈 길이 멀다...