서리 개인 개발 블로그

풀이 코드

#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()에 증감연산자 사용하는 방법이 있었다.

인덱서

- 인덱스를 이용해 객체 내의 데이터에 접근하게 해주는 프로퍼티.

- 객체를 배열처럼 사용할 수 있게 해준다.

- 인덱서는 해당 접근자가 매개변수를 사용한다는 점을 제외하면 프로퍼티와 유사하다.

- List나 ArrayList에서 인덱스를 통해 접근하는 방법을 생각하면 이해하기 쉽다.

- 선언 방법 : this[int index] { get; set; }

  ※ this 키워드는 인덱서를 정의하는데 사용된다.

사용 예

using System;

class Indexer
{
    private int[] iArr = new int[10];
    
    public int this[int i]
    {
        get { return iArr[i]; }
        set { iArr[i] = value; }
    }
}

class Program
{
   static void Main()
   {
      Indexer indexer = new Indexer();
      for(int i = 0; i < 10; i++)
      {
        indexer[i] = i;
      }
      
      //결과 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
   }
}

풀이 코드

#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 원소 문자열의 접두사가 된다.