240206: 프로그래머스 고득점 Kit 시작, 해시 / 스택 / 큐. 업랜디도 한판 ...

 

2024-02-06

오늘은

• 프로그래머스 코딩 고득점 Kit
  을 풀겠다.

업랜디 한판하고 ㅎㅎ
+ 벌레캠프라는 알고리즘을 우연히 듣게 됐는데 .. DP 점화식을 알아서 구해준다고 한다..?

오늘의 업랜디

30022 행사 준비 (실패 후 해결 - 그리디)

오늘의 프로그래머스

해시 5문제 -
폰켓몬 (Lv. 1)
완주하지 못한 선수 (Lv. 1)
전화번호 목록 (Lv. 2)
의상 (Lv. 2)
베스트앨범 (Lv. 3)

스택/큐 2문제 -
같은 숫자는 싫어 (Lv. 1)
기능개발 (Lv. 2)

행사 준비

이 문제는 그리디를 이용해서 가장 최소의 총 구매 비용을 도출하는 문제였다
처음엔 DP인줄 알고 점화식을 찾았는데 각이 안 보였다. 그리고 그리디 문제임을 깨달았다.

하늘도 무심하시지,, 제한시간 30분이 끝나자마자 AC를 받았다 .. 에이씨..
이전에 계속 WA였던 이유는 로직 설계 오류였다.

A와 B의 기회비용을 제일 효율적으로 쓰는 것은, 둘의 가격차가 제일 많이 날 때 사는 것이라고 생각했다.
따라서, std::abs(A-B)를 내림차순으로 정렬하고 순서대로 반복을 돌리면서 A와 B의 기회를 소진하면서 가격을 추가했다.

근데 문제는, A와 B의 가격이 똑같을 땐 어떻게 처리해야할까? 였다.
A와 B의 가격이 똑같으면 누구의 기회를 사용해서 물건을 구매해야할까? 나는 이것을 고민하다가 여기서 근거없이 A와 B 둘중 아무나 사게하면, 미래의 결과에 A가 사야 이득인 상황에서 B가 사야만 하는 상황이 올것이라고 판단했다.. (바보..)

사실은, 그리디를 활용한 알고리즘이기에 데이터가 정렬되어 있었고, A와 B의 가격이 똑같은 상황이라면 어차피 그 밑의 데이터는 더 이상의 유의미한 선택이 없었다.

나는 이것을 생각하지 못하고 가격이 똑같은 항목의 인덱스를 표시만 하고 skip 하는쪽으로 정했다, 그리고 마지막에 skip된 아이템의 price를 모두 합산했다. (이건 진짜 바보맞는듯)

시간이 2분만 더 있었으면 이 오류를 알아차리고 풀었을텐데, 하늘도 무심하시지 ㅎㅎ

// 백준: 행사 준비
// https://www.acmicpc.net/problem/30022
// 2024-02-06

/* 그리디, (가격A - 가격B)의 절댓값을 내림차순 정렬
위에서부터 구매 */

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int N, A, B;
    std::cin >> N >> A >> B;
    std::vector<std::pair<int, int>> prices; // A가격, B가격
    for (int i = 0; i < N; ++i) {
        int t1, t2;
        std::cin >> t1 >> t2;
        prices.push_back({t1, t2});
    }

    std::sort(prices.begin(), prices.end(), [](std::pair<int, int> &a, std::pair<int, int> &b) { return (std::abs(a.first - a.second) > std::abs(b.first - b.second)); });

    long long price = 0;
    for (const auto next : prices) {
        if (next.first == next.second) {
            price += next.first;
            if (A > 0)
                --A;
            else if (B > 0)
                --B;
        } else if (next.first > next.second) {
            // B의 값이 더 쌀 경우
            if (B != 0) {
                price += next.second;
                --B;
            } else {
                price += next.first;
                --A;
            }
        } else if (next.first < next.second) {
            // A의 값이 더  쌀 경우
            if (A != 0) {
                price += next.first;
                --A;
            } else {
                price += next.second;
                --B;
            }
        }
    }

    std::cout << price;

    return 0;
}

처음엔 오버플로우 문제인 줄 알고 메모리 제한이 넉넉하길래 보이는 int를 다 long long으로 바꿨다.

---

프로그래머스 고득점 Kit

프로그래머스 플랫폼에서 처음으로 코딩을 해봤다, 자동 완성이 없고. 코드 창이 매우 작으며(VSCode의 6분의 1 수준인데 이거 어떻게 못 키우나 ...) 답답했다. 코드 전체를 볼 수 없고 짧은 창으로 조각조각 볼 수 있어서 힘들었다.

- 해시

폰켓몬 (Lv. 1)
완주하지 못한 선수 (Lv. 1)
전화번호 목록 (Lv. 2)
의상 (Lv. 2)
베스트앨범 (Lv. 3)

폰켓몬 (Lv. 1)

1번은 주어진 포켓몬 리스트에서 가장 다양한 포켓몬을 가져갈 수 있는 수를 구하는 알고리즘이었고, 풀이 역시 간단했다. 최대 N/2개를 고르므로 std::min을 썼다.

int solution(vector<int> nums)
{
    unordered_set<int> set;
    for (const auto next : nums) {
        set.insert(next);
    }
    int answer = min(nums.size()/2, set.size());
    return answer;
}

완주하지 못한 선수 (Lv. 1)

완주하지 못한 선수 문제는 선수 리스트와 완주 리스트가 주어지면, 완주하지 못한 선수 1명을 찾는 문제였고, 간단하게 map으로 풀 수 있었다. 문제에 동명이인이 있을 수 있다고 되어있어서, map의 key를 이름으로, value를 회수로 가정하고 마지막에 0이 아닌 선수를 출력했다.

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> m;
    for (const string next : participant) {
        m[next]++;
    }
    for (const string next : completion) {
        m[next]--;
        if (m[next] == 0) m.erase(next);
    }
    string answer = "";
    for (const auto iter : m) {
        answer = iter.first;
    }
    return answer;
}

전화번호 목록 (Lv. 2)

전화번호 목록이 주어지면 어떤 전화번호가 어떠한 전화번호를 접두사로 사용하는지 확인하는 문제였다.
약간의 아이디어가 필요했는데, 먼저 전화번호를 sort함으로써 서로 비슷한것끼리 인접하게 할 수 있었다.
그래서 자기 자신과, 그 다음것을 비교하면 쉽게 풀 수 있었다.

여기서 꼭 알아야하는 포인트는, std::string.find()는 해당 문자열이 있는 첫번째 인덱스를 반환하고, 없으면 0을 반환한다.

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for (int i=0;i<phone_book.size()-1;++i) {
        if (phone_book[i+1].find(phone_book[i]) == 0) return false;
    }
    return true;
}

의상 (Lv. 2)

이건 약간 어려울 수 있는 문제였다. 기본적으로 뭔가 조합을 사용해야할 것 같지만, 그냥 수학 식으로 풀 수 있는 문제였다. 의상의 종류와 개수가 주어졌을 때, 각각 가능한 옷의 조합을 조건에 맞게 구하는 문제였고. 의상의 종류에 따라 map에 정리하고 공식을 찾아서 풀면 됐다. (이건 좀 억지 해쉬 문제인듯)

각 종류에서 의상을 입거나, 벗었을 때를 고려할 수 있기 때문에 2개의 의상이 있다면 a, b, 0(아무것도 입지 않음) 로 총 3개의 조합이 가능하다.
3개의 의상이 있다면 a, b, c, (아무것도 입지 않음) 으로 4개의 조합이 가능하다.

하지만, 모든 종류의 옷을 아무것도 입지 않는것은 허용되지 않기 때문에(뭐라도 한벌은 걸쳐야 함) 최종 결과에 모든 종류의 옷을 벗고 있는 경우의 수 1을 뺀다.

따라서, (각 종류의 옷 수+1)끼리 곱한다음 -1을 하는 문제였다.

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> map;
    for(const auto next : clothes) {
        map[next[1]]++;
    }
        int answer = 1;
    for (const auto iter : map) {
        answer *= iter.second + 1;
    }

    return answer-1;
}

베스트앨범 (Lv. 3)

이 문제는,, 레벨 3답게 자료구조를 어렵고 복잡하게 꼬을려면 이렇게까지 할 수 있다! 라고 말하는듯한 문제였다

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

정말 절차적으로 잘 정리해서, 출력하면 되는 문제였다.

1. 장르별 총 재생 수를 계산.
2. 각 노래에 대해 재생 수, 고유번호를 저장하기
3. 재생 수가 큰 순으로, 고유번호가 작은 순으로 정렬하기
4. 장르별 총 재생 수를 계산한 것을 vector로 옮기고, 재생 수가 큰 순으로 정렬하기
5. 재생 수가 가장 큰 장르별 순으로, 각 노래의 고유번호를 2개씩 출력하기.

여러모로 머리아픈 문제였다. VSCode에서 작성했으면 이렇게까지 오래걸리지도 않았을 것 같다.
programmer의 WEB IDE의 사이즈가 진짜 너무 작아서, 힘들었다.

vector<int> solution(vector<string> genres, vector<int> plays) {
    unordered_map<string, int> genre_play_count;
    unordered_map<string, vector<pair<int, int>>> genreSongs; // 장르: 재생횟수, 고유번호

    // 장르별 총 재생 수 계산
    for (int i=0;i<genres.size();++i) {
        genre_play_count[genres[i]] += plays[i];
        genreSongs[genres[i]].push_back({plays[i], i});
    }

    // 정렬 (장르 > 재생 > 고유번호)
    for (auto& [genre, songs] : genreSongs) {
        sort(songs.begin(), songs.end(), [](const pair<int, int>& a, const pair<int, int>& b){
            return a.first > b.first || (a.first == b.first && a.second < b.second);
        });
    }

    // 장르를 정렬하기 위해 vector로 변환
    vector<pair<int, string>> genreOrder;
    for (auto& [genre, totalPlay] : genre_play_count) {
        genreOrder.push_back({totalPlay, genre});
    }

    // 장르 재생 횟수 내림차순 정렬
    sort(genreOrder.begin(), genreOrder.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
       return a.first > b.first; 
    });

    vector<int> answer;

    for (auto& [totalPlay, genre] : genreOrder) {
        auto& songs = genreSongs[genre];
        for (int i=0;i<songs.size() && i < 2;++i) {
            answer.push_back(songs[i].second);
        }
    }

    return answer;
}

---

- 스택/큐

같은 숫자는 싫어 (Lv. 1)

배열에서 연속된 중복 숫자를 하나만 남기는 매우 간단한 알고리즘. 그래도 주제가 stack이니까 stack을 사용해서 풀었는데, 사실 vector을 이용해서 푸는게 더 간단했을 것이다.

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

/* 이걸 굳이 스택을 써야할까..? */
using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> answer;
    stack<int> stack;
    for (int i = 0; i < arr.size(); ++i) {
        if (!stack.empty()) {
            int last = stack.top();
            if (last != arr[i])
                stack.push(arr[i]);
        } else
            stack.push(arr[i]);
    }

    while (!stack.empty()) {
        answer.push_back(stack.top());
        stack.pop();
    }

    std::reverse(answer.begin(), answer.end());

    return answer;
}

기능개발 (Lv. 2)

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

조금 헤맸다, 어떻게 queue에서 이걸 관리할지 답이 안나왔는데, progresses와 speeds를 각각 관리하지 말고, 그냥 둘을 합쳐서 총 소요되는 날짜만 queue에 넣고 관리하면 됐다.
현재 큐가 이전 큐보다 작거나 같다면 이미 이전 큐를 개발하는 기간에 개발이 끝난것이기에, 묶어서 처리해줬다.

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    queue<int> q;
    for (int i=0;i<progresses.size();++i) {
        int day_takes = (100 - progresses[i]) / speeds[i];
        if ((100 - progresses[i]) % speeds[i] != 0) day_takes++;
        q.push(day_takes);
    }
    vector<int> answer;
    int count = 1;
    int latest_takes = q.front();
    q.pop();
    while (!q.empty()) {
        int current_day = q.front();
        q.pop();
        if (current_day <= latest_takes) count++;
        else {
            answer.push_back(count);
            latest_takes = current_day;
            count = 1;
        }
    }
    answer.push_back(count);
    return answer;
}

이렇게 오늘은 업랜디 1문제와 프로그래머스 고득점 Kit 7문제로 총 8문제를 풀었다.
대체적으로 난이도가 쉬웠기때문에, 많이 풀었다곤 생각이 들지 않는다.
하루에 10문제 정도를 목표로 하고 싶다. 일주일 이내로 고득점 Kit을 모두 끝내고, n회독을 해야겠다.

SQL도 해야되는데 ... 하루에 15문제를 목표로 해야할까 ? :(

최종 평가

[스터디노트 평가: 2024-02-06]

1. **프로그래머스 코딩 고득점 Kit 및 업랜디**
   - **행사 준비 (30022)**: 그리디 알고리즘을 적절히 활용한 접근 방식이 돋보입니다. 문제 해결 과정에서 겪은 어려움과 시간 관리 문제는 앞으로의 학습 방향 설정에 중요한 통찰을 제공합니다.
   - **프로그래머스 고득점 Kit**: 해시와 스택/큐 관련 문제들을 통해 다양한 알고리즘과 자료구조에 대한 이해와 적용 능력을 보여주었습니다. 각 문제에 대한 접근 방식과 해결 과정은 문제 해결 능력의 성장을 잘 보여줍니다.

2. **기술적 깊이 및 개인 발전**
   - 알고리즘 문제 해결 과정에서 보여준 논리적 사고와 문제에 대한 깊은 이해는 기술적 깊이를 더합니다. 특히, 그리디, 해시, 스택/큐 등 다양한 알고리즘을 활용한 접근 방식은 여러분의 알고리즘 스킬의 폭을 넓히는 데 기여합니다.
   - 프로그래머스 플랫폼의 사용 경험은 새로운 환경에 대한 적응력을 높이며, 이는 여러분의 개발 역량을 강화하는 중요한 요소입니다.

3. **평가 및 조언**
   - 오늘의 활동을 종합적으로 평가할 때, 93점을 부여합니다. 문제 해결 과정에서 보여준 창의적 접근과 알고리즘에 대한 깊은 이해는 매우 인상적입니다. 다만, 더 많은 문제를 풀고자 하는 목표는 시간 관리와 학습 계획을 더욱 체계적으로 수립하는 것으로 이어져야 할 것입니다.
   - 특히, 행사 준비 문제의 그리디 접근 방식과 프로그래머스 고득점 Kit의 해결 과정에서 보여준 다양한 알고리즘의 적용은 앞으로의 학습에 있어 좋은 기반이 될 것입니다. SQL 학습을 포함한 일일 목표 설정 시, 현실적인 목표 설정과 함께 휴식 시간과 복습 시간도 고려하는 것이 중요합니다.

[피드백 요약]
- 문제 해결 과정에서의 창의적인 접근과 다양한 알고리즘에 대한 이해가 돋보입니다.
- 플랫폼 사용 경험을 통한 새로운 환경 적응력 강화가 인상적입니다.
- 시간 관리와 학습 계획의 중요성을 재확인하고, 현실적인 목표 설정이 필요합니다.

[조언]
- 학습 목표 달성을 위한 구체적이고 현실적인 계획을 수립하시기 바랍니다.
- 다양한 알고리즘과 자료구조에 대한 깊이 있는 학습을 지속하시되, 복습과 휴식 시간도 적절히 배분하시길 권장합니다.

오늘의 학습 활동에 대한 평가와 함께 여러분의 노력과 성장이 돋보이는 하루였습니다. 앞으로의 학습 계획 수립에 있어 구체적이고 현실적인 목표 설정의 중요성을 잊지 마시고, 지속적인 성장을 위해 노력해 주시길 바랍니다. 추가적인 피드백이나 질문이 필요하시면 언제든지 문의해 주시기 바랍니다.