프로그래머스 42579 - 베스트앨범

문제 링크

생각 및 접근

• 시간이 꽤 걸린 문제였고, 새롭게 알게 된 C++ 지식들이 많았다.
• 선언한 자료 구조
  • 음악 장르 별로 음악 재생 수의 합을 구해서 내림차순으로 정리하기 위한 map<string, int> sumGenre; vector<pair<string, int>> v;
  • 음악 장르 별로 음악을 저장하고, 음악의 index 번호와 재생 수를 저장하는 map<string, vector<Music>> groupByGenre;
  • 음악의 index 번호와 재생 수를 한꺼번에 저장하고, operator 함수를 선언하기 위해 선언한 객체 struct Music{};

새로 배운 내용은 볼드 처리 하였습니다.

• 기

  • struct Music

      struct Music{
          int index;
          int play;
          Music(int b, int c){
              index = b;
              play = c;
          }
          bool operator < (const Music & b) const {
              if(play == b.play){
                  return index < b.index;
              }
              return play > b.play;
          }
      };

  • sumGenre와 groupByGenre에 값을 채워넣는다.

      for(int i = 0; i < numMusic; i++){
          sumGenre[genres[i]] += plays[i];
          groupByGenre[genres[i]].push_back(Music(i, plays[i]));
      }

• 승

  • map을 vector로 변환하기
    • vector로 변환하고, sum이 큰 순서대로 sort한다.

      bool cmp(pair<string, int> a, pair<string , int> b){
        return a.second > b.second;
      }

      vector<pair<string, int>> v;
      for(auto & k : sumGenre){
        v.push_back(make_pair(k.first, k.second));
      }
      sort(v.begin(), v.end(), cmp);

• 전, 결

  • vector v를 순회하면서, groupByGenre의 value인 vector를 sort한다.

      for(int i = 0; i < v.size(); i++){
          string target = v[i].first;
          sort(groupByGenre[target].begin(), groupByGenre[target].end());

    • sort의 방식은 play 오름차순, play 수가 같다면 index 내림차순으로 정렬한다.

  • 정렬 이후, 장르의 음악 수에 따라서 2개를 넣을 지, 1개를 넣을 지 판단한다.

          for(int i = 0; i < min(2, (int) groupByGenre[target].size()); i++){
              answer.push_back(groupByGenre[target][i].index);
          }
      }
    
      return answer;
    

코드

#include <bits/stdc++.h>
using namespace std;

struct Music{
    int index;
    int play;
    Music(int b, int c){
        index = b;
        play = c;
    }
    bool operator < (const Music & b) const {
        if(play == b.play){
            return index < b.index;
        }
        return play > b.play;
    }
};

bool cmp(pair<string, int> a, pair<string , int> b){
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    int numMusic = genres.size();

    map<string, int> sumGenre;
    map<string, vector<Music>> groupByGenre;

    for(int i = 0; i < numMusic; i++){
        sumGenre[genres[i]] += plays[i];
        groupByGenre[genres[i]].push_back(Music(i, plays[i]));
    }

    vector<pair<string, int>> v;
    for(auto & k : sumGenre){
        v.push_back(make_pair(k.first, k.second));
    }
    sort(v.begin(), v.end(), cmp);

    for(int i = 0; i < v.size(); i++){
        string target = v[i].first;
        sort(groupByGenre[target].begin(), groupByGenre[target].end());

        for(int i = 0; i < min(2, (int) groupByGenre[target].size()); i++){
            answer.push_back(groupByGenre[target][i].index);
        }
    }

    return answer;
}

채점 결과

프로그래머스 42578 - 위장 (c++)

문제 링크

접근 및 생각

• 의상의 종류가 있기 때문에, 단순 vector로 다루기엔 어려워서 map이라는 자료구조를 활용했습니다.
  • C++ STL map에 대한 정보
  • 문제에서 활용된 map의 pair는 <string, int>로 하여, string에는 옷의 종류 이름이, int에는 옷의 종류에 해당하는 옷의 가짓수를 저장하였습니다.
• 전부 다 벗은 경우를 제외해야 하고, 최소한 하나의 옷을 입어야 합니다. 옷의 종류가 아래와 같다면,

    a : 3, b : 2, c : 1, d : 7

  (3 + 1) * (2 + 1) * (1 + 1) * (7 + 1) - 1이 문제의 답이 됩니다.
  괄호 안의 + 1 은 그 옷의 종류를 입지 않은 경우를 넣은 것이고, 괄호 밖의 - 1 은 전부 다 벗은 경우를 제외한 것입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> m;

    // 옷의 종류에 해당하는 map value를 하나씩 늘려줍니다.
    for(int i = 0; i < clothes.size(); i++){
        m[clothes[i][1]]++;
    }

    // map을 순회하면서 (k.second + 1)를 곱해줍니다.
    for(auto & k : m){
        answer *= (k.second + 1);
    }

    // 전부 다 벗은 경우를 빼주고 반환해줍니다.
    return answer - 1;
}

채점 결과

프로그래머스 42577 - 전화번호 목록

문제 링크

접근 및 생각

• 우선, vector string을 sort했을 때 어떤 식으로 나열되는지 알아야 문제를 쉽게 풀 수 있었습니다. phone_book의 vector type이 int인 경우와 vector type이 string인 경우의 sort 결과가 다릅니다.

• 입출력 예제에서 준 vector string sort의 결과는 아래와 같습니다.

  

• string은 int와 달리 문자로 취급되므로 사전순으로 나열 됩니다. 사전을 펼쳐서 가 다음에 가나 가 나오듯이, phone_book을 sort하면 119 다음엔 1195524421 이 나옵니다. sort한 vector를 앞 원소와 바로 뒤 원소를 비교하여 접두어가 있는지 없는지를 판단하면 되겠습니다.

• 접두어가 있는지 어떻게 판단하느냐. 저는 string의 substr() 함수를 사용했습니다. substr()은 문자열의 일부분을 문자열로 반환하는 함수로, 파라미터를 1개, 2개를 넣을 수 있습니다.

  • 1개일 경우 : ( 시작위치 ) : 시작위치부터 끝까지의 문자들을 문자열로 반환합니다.

  • 2개일 경우 : ( 시작위치, 개수 ) : 시작위치부터 개수만큼의 문자를 문자열로 반환합니다.

    string s = "ABCDEF";
    string s2 = s.substr(4);      // s2 = "EF"    ( index 4부터 끝까지의 문자열을 반환한다. )
    string s3 = s.substr(1,3);    // s3 = "BCD"   ( index 1부터 3까지의 문자열을 반환한다. )

  • 출처 C++ 라이브러리 - String 클래스 함수 정리|작성자 김랜턴

• 이 점을 활용해서 앞의 원소의 string length만큼 뒤의 원소를 substr한 값을 앞의 원소와 비교합니다. 같다면 return false, 다르다면 다음 원소를 비교합니다. phone_book을 모두 비교해도 return false되지 않았다면, 접두어가 없는 phone_book이므로 return true해주시면 되겠습니다.

코드

#include <bits/stdc++.h>
using namespace std;

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

    // 출력을 위한 코드
    // for(auto k : phone_book){
    //     cout << k << endl;
    // }

    for(int i = 1; i < phone_book.size(); i++){
        string temp = phone_book[i].substr(0, phone_book[i - 1].length());
        if(temp == phone_book[i - 1])
            return false;
    }
    return true;
}

채점 결과

프로그래머스 42576 - 완주하지 못한 선수

문제 사이트

접근 및 생각

• 문제의 조건 중 "단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다."와 "마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때"를 보고, participant와 completion을 sort하여 앞에서부터 비교해나가야겠다 는 생각을 했습니다.

코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    // participant와 completion을 sort
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    // 앞에서부터 비교
    for(int i = 0; i < completion.size(); i++){

        // 비교해서 같으면 무시
        if(participant[i] == completion[i]) continue;

        // 비교해서 다르면, participant[i]는 완주하지 못한 선수
        else{
            answer = participant[i];
            break;
        }

    }

    // answer에 무언가가 지정되어 있지 않다면, participant의 맨 마지막 선수가 완주하지 못한 선수
    if(answer == ""){
        answer = *(participant.end() - 1);
    }

    return answer;
}

채점 결과