서리 개인 개발 블로그

풀이코드

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

using namespace std;

int GetAnswer(const vector<int>&, int);

int solution(vector<int> priorities, int location) {
    int answer = GetAnswer(priorities, location);
    return answer;
}

int GetAnswer(const vector<int>& priorities, int location)
{
    int result = 0;
    queue<pair<int, int>> iQueue;
    priority_queue<int> pQueue;
    for(int i = 0; i < priorities.size(); i++)
    {
        iQueue.push(make_pair(i, priorities[i]));
        pQueue.push(priorities[i]);
    }

    while(!iQueue.empty())
    {
        if(iQueue.front().second == pQueue.top())
        {
            pQueue.pop();
            result++;

            if(iQueue.front().first == location)
            {
                break;
            }
        }
        else
        {
            iQueue.push(iQueue.front());
        }
        iQueue.pop();
    }

    return result;
}

• vector의 값을 queue<pair<int, int>와 priority_queue<int>에 넣어준다.
• 그 뒤, 큐의 priority값과 우선순위 큐의 값을 비교해서 같으면 result를 증가시키고 다르면 큐의 첫번째 값을 맨 뒤로 옮겨준다.
• priority 값이 같을 때, location값을 비교하는데 location 값이 같으면 내가 요청한 문서를 찾은것이니 반복문을 나와 result 값을 반환한다.

기타

- 인수로 들어오는 vector 값으로 해결해보려고 했는데, 기본 케이스는 통과가 되나 제출 시의 테스트 케이스에서 불합격이 나는바람에 포기했다. (어떤 케이스에서 안되는지 알고싶은데 그걸 모르니 답답함...)

풀이 코드

#include <string>
#include <vector>

using namespace std;

#define COMPLETE 100

vector<int> GetAnswer(const vector<int>&, const vector<int>&);

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer = GetAnswer(progresses, speeds);
    return answer;
}

vector<int> GetAnswer(const vector<int>& progresses, const vector<int>& speeds)
{
    vector<int> result;
    for(int i = 0; i < progresses.size();)
    {
        int date = (COMPLETE - 1 - progresses[i]) / speeds[i] + 1;
        int releaseCount = 0;
        for(int j = i; j < progresses.size(); j++)
        {
            if(progresses[j] + speeds[j] * date >= COMPLETE)
            {
                releaseCount++;
            }
            else
            {
                break;
            }
        }

        result.push_back(releaseCount);
        i += releaseCount;
    }

    return result;
}

• 카테고리가 스택/큐로 분류되어있어서 큐를 사용할까 했는데, 이걸 굳이 큐까지 사용해야하나 싶어서 결국 결과 값을 카운팅해서 구했다.

기타

- 다른사람 풀이를 보니 반복문 하나만 사용해서 풀은 코드를 보게되었다.

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

- 처음에 이런식으로 작성하려고 생각했다가, answer에 값이 없을 때와 이미 들어간 값을 증감시키는 부분에 막혀서 카운팅을 따로 했었는데 vector.back()에 증감연산자 사용하는 방법이 있었다.

풀이 코드

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

using namespace std;

#define MAX 2

vector<pair<string, int>> GetSortedGenres(const vector<string>&, const vector<int>&);
unordered_map<string, vector<pair<int, int>>> GetSortedPlays
(const vector<pair<string, int>>&, const vector<string>&, const vector<int>&);

vector<int> solution(vector<string> genres, vector<int> plays) {
	
    //재생 수를 기준으로 내림차순으로 정렬 된 장르의 벡터를 가져온다.
    vector<pair<string, int>> genresVec = GetSortedGenres(genres, plays);
    //재생 수를 기준으로 내림차순으로 정렬 된 장르별 곡의 맵을 가져온다.
    unordered_map<string, vector<pair<int, int>>> playsMap = GetSortedPlays(genresVec, genres, plays);

    vector<int> answer;
    for(int i = 0; i < genresVec.size(); i++)
    {
        for(int j = 0; j < playsMap[genresVec[i].first].size() && j < MAX; j++)
        {
            //반환할 결과 값(벡터)에 장르별 곡의 길이(혹은 최대 2곡)까지 넣어준다.
            answer.push_back(playsMap[genresVec[i].first][j].first);
        }
    }

    return answer;
}

vector<pair<string, int>> GetSortedGenres(const vector<string>& genres, const vector<int>& plays)
{
    unordered_map<string, int> genresMap;
    for(int i = 0; i < genres.size() && i < plays.size(); i++)
    {
        genresMap[genres[i]] += plays[i];
    }

    //값(value)를 기준으로 내림차순 정렬을 해주기위해 map을 vector로 바꿔준다.
    vector<pair<string, int>> pVector;
    for(auto& it : genresMap)
    {
        pVector.push_back(it);
    }
	
    //내림차순 정렬(람다 사용)
    sort(pVector.begin(), pVector.end(), [](auto& p1, auto& p2)
    {
        return p1.second > p2.second;
    });

    return pVector;
}

unordered_map<string, vector<pair<int, int>>> GetSortedPlays
(const vector<pair<string, int>>& pairVec, const vector<string>& genres, const vector<int>& plays)
{
    unordered_map<string, vector<pair<int, int>>> map;
    for(int i = 0; i < genres.size() && i < plays.size(); i++)
    {
        map[genres[i]].push_back(make_pair(i, plays[i]));
    }

    for (auto& it : map)
    {
    	//map의 장르(Key)에 해당하는 곡(value(pair))들을 내림차순으로 정렬(람다 사용)
        sort(it.second.begin(), it.second.end(), [](auto& v1, auto& v2)
        {
            //곡의 플레이수가 같으면 고유번호를 기준으로 오름차순 정렬한다.
            if (v1.second == v2.second)
            {
                return v1.first < v2.first;
            }

            return v1.second > v2.second;
        });
    }

    return map;
}

• 각 곡 장르와 장르별 곡을 정렬해 반환하는 함수를 나눠 작성했지만, 반환 함으로써 값 복사가 일어나므로 solution에 다 작성하거나, 힙에 할당했으면 좀 더 좋았을 것 같다.

기타

- Lv3은 처음 풀어봤는데, Lv1, Lv2와 다르게 코드가 너무 길어져서 잘못하고 있는줄 알았다.

- C#이랑 람다 식을 작성하는 방법이 달랐다.

- 해당 문제를 풀면서 필요한 자료형을 찾다가 pair라는것을 알게 됨.

풀이코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

#define CLOTH_KIND 1

int GetAnswer(const vector<vector<string>>&);

int solution(vector<vector<string>> clothes) {
    int answer = GetAnswer(clothes);
    return answer;
}

int GetAnswer(const vector<vector<string>>& clothes)
{
    int returnValue = 1;
    unordered_map<string, int> map;
    for(int i = 0; i < clothes.size(); i++)
    {
        auto iter = map.find(clothes[i][CLOTH_KIND]);
        if(iter == map.end())
        {
            map.insert(make_pair(clothes[i][CLOTH_KIND], 1));
        }
        else
        {
            iter->second++;
        }
    }

    for(auto iter = map.begin(); iter != map.end(); iter++)
    {
        returnValue *= iter->second + 1;
    }

    return returnValue - 1;
}

• map을 만들어 옷 종류별로 나눈 뒤, 경우의 수를 계산하여 반환한다.

기타

- 처음에는 map<string, vector<string>>으로 선언해서 접근했으나, 하다보니 수학으로 해결해야 할 것 같아서 map<string, int>로 변경했다.

- 코드 자체는 작성하기 쉬웠으나 경우의 수에서 많이 헤맸다.

- 경우의 수와 같은 경우, 각 옷의 종류마다 입지 않는다는 경우를 하나더 추가해서 모든 경우의 수를 계산하게 되면 마지막의 경우는 모든 옷을 입지 않는다는 수가 나오게 되는데, 지문에서 무조건 1개 이상 입도록 되어있으니 해당 경우의 수를 제외해서 반환하면 된다.

- 다른 사람 풀이를 보니 굳이 find로 키를 찾을 필요없이 operator[]로 바로 접근해도 됐었다.

- operator[]의 경우, 맵 안에서 키를 탐색하고 저장된 값의 참조를 반환하며, 키가 없을 경우 기본 초기화를 사용하여 해당 키에 새 요소를 만든 뒤 참조를 반환한다.

풀이코드

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

using namespace std;

bool GetAnswer(const vector<string>&);

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());

    bool answer = GetAnswer(phone_book);
    return answer;
}

bool GetAnswer(const vector<string>& pb)
{
    for(int i = 0; i < pb.size() - 1; i++)
    {
        if(pb[i] == pb[i + 1].substr(0, pb[i].size()))
        {
            return false;
        }
    }
    return true;
}

• 문자열이라 정렬을 한 뒤 반복문으로 현재 원소와 다음 원소를 비교해서 bool값을 반환한다.

기타

- 풀긴 했는데 해시와는 거리가 먼 코드같아서 다른사람 풀이를 보다가 문제 의도대로 풀린 코드를 봤다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
    {
        hash_map[phone_book[i]] = 1;
    }

    for(int i = 0; i < phone_book.size(); i++) 
    {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) 
        {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
            {
                return false;
            }
        }
    }

    return true;
}

• map을 써서 해시 값을 확인하고 전화번호 문자열(phone_number)을 vector의 원소 문자열과 비교해서 다르면 맵의 해시가 vector 원소 문자열의 접두사가 된다.