프로그래머스 42586 - 기능개발

문제 링크

생각과 접근

• 먼저 각 작업의 끝나는데 걸리는 날 ( vector<int> endDay(progresses_size, 0) ) 을 구한 다음, 그 값을 토대로 answer를 찾으려 했습니다.
• endDay 를 순회하면서 endDay 의 최댓값을 기록하는 변수 temp 와 answer에 push_back할 변수 cnt를 선언했습니다. temp가 갱신되는 순간, answer에 cnt 를 push_back합니다. 최댓값으로 기록된 변수 temp 가 변경되는 시점은 그간 앞의 작업이 끝나길 기다리는 작업들이 temp 일 만큼 걸리는 작업이 끝났으므로 배포가 가능하게 되는 시점입니다.

코드

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    int progresses_size = progresses.size();
    vector<int> answer;
    vector<int> endDay(progresses_size, 0);

    // 각 작업의 끝나는데 걸리는 날을 구하기
    int day = 0, endJob = 0;
    while(endJob < progresses_size){
        day++;
        for(int i = 0; i < progresses_size; i++){
            if(progresses[i] >= 100)    continue;
            progresses[i] += speeds[i];
            if(progresses[i] >= 100){
                endDay[i] = day;
                endJob++;
            }
        }
    }

    int temp = endDay[0], cnt = 1;
    for(int i = 1; i < progresses_size; i++){
        if(temp < endDay[i]){
            temp = endDay[i];
            answer.push_back(cnt);
            cnt = 0;
        }
        cnt++;
    }
    answer.push_back(cnt);
    return answer;
}

채점 결과

프로그래머스 42584 - 주식가격

문제 링크

생각과 접근

• 문제가 스택/큐 분야에 있어서 스택과 큐를 활용해서 문제를 풀어보려다 실패해서 그냥 맨 처음에 생각했던 이중 for문 방식으로 풀었습니다.
• i for문에서 0부터 price_size - 2만큼 돕니다. prices의 마지막 원소를 탐색하지 않는 이유는 맨 마지막 주식 가격은 가격이 떨어질 수 없고, 이에 따라 answer 값이 0으로 고정되기 때문에 나중에 0 하나만 push_back하기로 했습니다.
• j for문에서 i + 1부터 price_size - 1만큼 돕니다. prices[i]보다 prices[j]이 작다면, answer에 j - i를 push_back하고 j for문을 종료합니다. 만약 j for문을 break없이 끝냈다면, answer에 j - i - 1를 push_back합니다.
  • 왜 j - i와 j - i - 1로 나눠서 구분을 하는가?
    • answer는 주식가격이 떨어지지 않는 시간 을 기록합니다. 아래 입출력 예로 설명하겠습니다.

      • 

      • 쉽게 말해서, 주식가격이 떨어지지 않는 시간을 세는 방식은 prices 배열의 ,수를 세는 것 입니다.
      • prices[2]는 prices[3]에서 j for문이 멈추게 됩니다. ,가 하나 있고, j - 1의 값은 3 - 2 = 1로 동일합니다.
      • prices[0]는 prices[4]와 비교를 끝내고 j = 5인채로 j for문이 끝나게 됩니다. ,는 4개 있고, j - i - 1의 값은 5 - 0 - 1로 동일합니다. - 1이 있는 이유는 j for문에서 빠져나올 때 j++되어 그것을 하나 빼주는 것입니다.

코드

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

vector<int> solution(vector<int> prices) {
    int i, j, price_size = prices.size();
    vector<int> answer;

    for(i = 0; i < price_size - 1; i++){
        for(j = i + 1; j < price_size; j++){
            if(prices[i] > prices[j]){
                answer.push_back(j - i);
                break;
            }
        }
        if(answer.size() != i + 1){
            answer.push_back(j - i - 1);
        }
    }
    answer.push_back(0);

    return answer;
}

채점 결과

프로그래머스 42585 - 쇠막대기

문제 링크

생각과 접근

• 쇠막대기 문제는 문제의 길이는 짧지만 고민을 정말 많이 해야하는 문제였습니다.
  
  

  

• 위와 같은 경우를 깊게 고민해보았습니다.
• 괄호를 열 경우는 딱히 나뉘는 케이스가 떠오르지 않았습니다.
• 괄호를 닫을 경우 두가지 케이스로 나뉩니다.
  • 첫 번째 : 레이저인 경우
    • 레이저일 경우, 열려있던 괄호만큼 answer를 더해주면 됩니다. (잘린 쇠 파이프 갯수!)
  • 두 번째 : 쇠막대기가 끝나는 경우
    • 쇠막대기가 끝나는 경우, 새로운 쇠막대기가 단 하나 생깁니다.
      
      

      

• 빨간 원이 레이저일 때 더해주는 경우, 파란 원이 쇠막대기가 끝나는 경우입니다.

코드

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

int solution(string arrangement) {
    int answer = 0;
    stack<int> s;

    for(int i = 0; arrangement[i] != '\0'; i++){
        if(arrangement[i] == '(')   s.push(1);
        else if(arrangement[i] == ')'){
            s.pop();
            if(arrangement[i - 1] == '(')       answer += s.size();
            else if(arrangement[i - 1] == ')')  answer++;
        }
    }
    return answer;
}

채점 결과

프로그래머스 42588 - 탑

문제 링크

생각과 접근

• 문제의 분야는 스택/큐에 있었지만, 굳이 사용하지 않고 for문 두 개를 쓰면 간단히 풀 수 있는 문제였습니다.
• 신호는 오른쪽에서 왼쪽으로 흐르니 heights를 탐색할 때 거꾸로 탐색합니다. (i-for문)
• 두 번째 j-for문에서 i보다 제일 가깝고 heights[i]보다 큰 값을 찾습니다.
  • 큰 값이 있다면, 그 타워의 인덱스를 push_back
  • 큰 값이 없다면, 0을 push_back
• 탐색은 거꾸로 하여 값 또한 거꾸로 push_back되어 있으므로, vector answer에 다시 거꾸로 넣어줍니다.

코드

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

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    vector<int> temp;

    for(int i = heights.size() - 1; i >= 0; i--) {
        for(int j = i - 1; j >= 0; j--) {
            if(heights[j] > heights[i]){
                temp.push_back(j + 1);
                break;
            }
            if(j == 0) temp.push_back(0);
        }
        if(i == 0) temp.push_back(0);
    }

    for(int i = temp.size() - 1; i >= 0; i--){
        answer.push_back(temp[i]);
    }
    return answer;
}

채점 결과

프로그래머스 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;
}

채점 결과