JArchive 프로그래밍 일기

문제

베스트앨범 프로그래머스 level3

리뷰

해시 카테고리의 문제다.

map을 잘 다루면 풀 수 있는 문제였다.

장르 별로 가장 많이 재생된 노래 2개 씩 모아 앨범을 출시한다.

1. 속한 노래가 많이 재생된 장르를 내림차순으로 정렬한다.

// 장르명, 재생횟수 
map<string, int> genre_cnt;

2. 장르 내에서 많이 재생된 노래를 내림차순으로 정렬한다.

// 장르명 string,   <재생횟수, 고유번호> pair로 vector를 저장한다. 
map<string, vector<pair<int,int>>> genre_playlist;  

3. 장르 내에서, 재생횟수가 같은 노래 중에는 고유번호가 낮은 노래를 수록한다.

// 장르명, 재생횟수를 저장한다. 
vector<pair<string, int>> genre_v;

코드

#include <string>
#include <vector>
#include <algorithm> 
#include <map>
using namespace std;

bool compare(pair<int,int> a, pair<int,int> b){
    return a.first > b.first; // 재생횟수 내림차순  
}

bool compare_song_cnt(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;

    map<string, int> genre_cnt; // 장르별 재생횟수 
    map<string, vector<pair<int,int>> > genre_playlist; // 장르별 노래의 재생횟수 및 고유번호
    vector<pair<string, int>> genre_v;  // 장르별 노래 개수 

    for(int i = 0; i < genres.size(); i++){
        genre_cnt[genres[i]] += plays[i]; // 장르별 재생횟수 누적
        genre_playlist[genres[i]].push_back({plays[i], i}); // 장르별 노래의 재생횟수 및 고유번호 
    } 

     // 재생횟수를 이용하여 내림차순 정렬 
    for( auto &song : genre_playlist){
        sort(song.second.begin(), song.second.end(), compare);    
    }    

     genre_v.assign(genre_cnt.begin(), genre_cnt.end()); // 장르별 노래 개수
    sort(genre_v.begin(), genre_v.end(), compare_song_cnt); // 내림차순  

    for(int i = 0; i <genre_v.size(); i++){ // 장르 종류만큼 반복

        string genre_name = genre_v[i].first; // 장르 이름  

        // genre_playlist 에서 최대 2곡까지 선택 가능 (j < 2)
        for(int j = 0; ( j <genre_playlist[genre_name].size() && j < 2 ); j++){ 
            answer.push_back(genre_playlist[genre_name][j].second);
        } 
    }

    return answer;
}

문제

위장 프로그래머스 level2

리뷰

해시 카테고리의 문제다. 조합의 개념이 필요하다.

예를 들어, 선글라스 2종류, 모자 1종류가 있다.

1개씩 착용한 경우는 3가지다. 2가지를 착용한 경우는 eyeware 2 X headgear 1 = 2가지다.

따라서 답은 5가지가 된다.

다른 방식으로 계산하면, 어떤 의상을 착용한다 / 안한다의 기준으로 각 종류에 +1을 해준다. 옷 종류만큼 곱한다.

(eyeware 2 +1 ) X (headgear 1 + 1) = 3 X 2 = 6 가지

여기서 전부 착용 안하는 1가지 경우를 빼줘서 5가지 라는 답을 얻을 수 있다.

코드

#include <string>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<string>> clothes) { 

    int answer = 1;
    map<string, int> m;

    for(auto c : clothes){ // 옷의 종류를 센다  
        m[c[1]]++;
    }

    // 옷 종류만큼 곱한다. 
    map<string, int>::iterator it;

    for(it = m.begin(); it != m.end(); it++){
        answer *=  (it->second + 1);
    }

    answer--;  // 마지막에 1개 빼준다(하나도 안 입은 경우를 제외해야 하므로.)

    return answer;
}

문제

기능개발 프로그래머스 level2

입출력 예시

스택/큐 카테고리의 문제다.

입출력 예시는 아래와 같다.

작업 [93, 30, 55] , 작업속도 [1, 30, 5]

93%진행된 작업은 하루에 1%씩 진행된다. (7일만 더 일하면 100이 된다 )

30%진행된 작업은 하루에 30%씩 진행된다. (3일만 더 일하면 100을 넘긴다)

55% 진행된 작업은 하루에 5%씩 진행된다. (9일이 더 필요하다)

따라서 7, 3, 9일 씩 필요한데, 첫 작업이 끝났을 때는 이미 두번째 작업이 (3일밖에 안걸림)끝나 있으므로 함께 배포된다. 셋째 작업은 9일이 필요하니까, 첫째 둘째 작업보다 2일이 더 필요하다.

따라서 정답은 [2, 1] 이 된다.

리뷰

작업량이 100이 되면 배포가 가능하니까, speeds 배열 값을 활용해 각 작업이 몇일이 걸리는지 세준다.

소요 시일을 큐에 넣는다. 100개 이하의 작업이니까 for문으로 처리한다

    for(int i = 0; i < progresses.size(); i++){ // 작업 마다 몇일 걸리는지 세준다  
        int day_cnt = 0;

        while(progresses[i] < 100){
            progresses[i] += speeds[i];
            day_cnt++;
        }
        q.push(day_cnt); 
    }

그 다음, 큐를 보고 함께 배포할 수 있는 작업 개수를 센다.

큐에서 front 값을 확인한다. 현재 front 값보다 작거나 같을 때 까지 큐에서 pop()한다.

현재 front 값보다 작다면, 현재 작업보다 먼저 끝나있다는 것이다.

현재 front 값보다 크다면, 현재 작업보다 오래걸려서 끝났다는 것이다.

    int cnt = 1; // 현재 
    int front_day = q.front();
    q.pop();

    while(!q.empty()){

        if(q.front() <= front_day){
            q.pop();
            cnt++;
        }else{
            answer.push_back(cnt);
            cnt = 1;
            front_day = q.front();
            q.pop();
        }
    }
    answer.push_back(cnt);

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;


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

    queue<int> q;

    for(int i = 0; i < progresses.size(); i++){ // 작업 마다 몇일 걸리는지 세준다  
        int day_cnt = 0;

        while(progresses[i] < 100){
            progresses[i] += speeds[i];
            day_cnt++;
        }
        q.push(day_cnt); 
    }

    int cnt = 1; // 현재 
    int front_day = q.front();
    q.pop();

    while(!q.empty()){

        if(q.front() <= front_day){
            q.pop();
            cnt++;
        }else{
            answer.push_back(cnt);
            cnt = 1;
            front_day = q.front();
            q.pop();
        }
    }
    answer.push_back(cnt);

    return answer;
}

문제

더 맵게 프로그래머스 level2

리뷰

힙 카테고리에 있는 문제다.

처음에는 내림차순으로 정렬 후, 뒤에서 첫번째, 두번째 숫자들을 pop_back, 새로 계산한 숫자를 push_back 해서 해결하려고 했었다.

하지만 자꾸 (비용이 큰 함수) sort()를 해야 해서 "실패" 떴다. 그리고 벡터 크기가 2 이상인지도 체크도 안해줬다...

실패한 코드

#include <functional> 

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int last = scoville.size()-1;

    while(scoville[last] >= K){

        sort(scoville.begin(), scoville.end(), greater<int>()); // 내림차순 
        last = scoville.size()-1;
        int new = scoville[last-1]*2 + scoville[last];
        scoville.pop_back();
        scoville.push_back(new);

        answer++;
    }

    return answer;
}

힙 을 사용해서 바꿨다.

priority_queue<int, vector<int>, less<int> > pq; // 오름차순
priority_queue<int, vector<int>, greater<int> > pq; // 내림차순

내림차순으로 정렬한 우선순위 큐를 선언하고, 벡터의 원소를 모두 넣는다.

맨 위에는 가장 작은 값이 오니까 2개 꺼내서 새 값을 계산해서 다시 푸시한다.

이 때, 2개를 꺼내야 하니까, 큐의 사이즈가 1인지 확인하여 예외처리를 해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int> > pq;
    int answer = 0;

    for(int i=0; i <scoville.size(); i++){ // 벡터 원소를 모두 큐에 넣는다 
        pq.push(scoville[i]);
    }

    while(pq.top() < K){

        if(pq.size() < 2){
            answer = -1; break;    
        } 

        int top = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        pq.push(second*2 + top);
        answer++;
    }

    return answer;
}

문제

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

리뷰

해시 카테고리에 있는 문제다.

입력이 [12,123,1235,567,88] 로 주어졌을 때, 12 가 123의 접두어가 된다. 그래서 답이 false가 나와야 한다.

따라서 12를 타겟으로 두고, 나머지 문자열을 검사한다.

나머지 문자열이 12를 가지고 있는 시작 인덱스가 0인지 확인하면 된다.

// 12 : first,  123 : second 문자열인 경우, 

int loc = second.find(first);
if(loc == 0 ) answer = false; break; 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    int pb_size = phone_book.size();

    sort(phone_book.begin(), phone_book.end());

    for(int i = 0; i < pb_size; i++){
        for(int j = i+1; j < pb_size; j++){

            string first = phone_book[i];
            string second = phone_book[j];

            int loc = second.find(first);
            if(loc == 0 ) answer = false; break;
        }    
    }

    return answer;
}

문제

주식가격 프로그래머스 level2

리뷰

이중 for문 으로 해도 풀린다.

자신보다 큰 수가 몇 개인지 개수를 세는 것이다.

코드 1

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    for(int i = 0; i < prices.size(); i++){

        int cnt = 0;
        for(int j = i+1; j <prices.size(); j++){
            if(prices[i] <= prices[j]) cnt++;
            else{
                cnt++;
                break;
            }
        }
        answer.push_back(cnt); 
    }

    return answer;
}

리뷰

스택/큐 카테고리에 들어가 있으니 스택을 이용한 풀이를 찾아봤다.
스택에 인덱스를 넣는 방법이다.

prices 가 [ 1, 2, 3, 2, 3 ] 으로 주어졌을 때,
값이 계속 오르는 1, 2, 3 구간은 스택에 0 1 2 로 저장된다. 이 순간 스택의 top 은 2 라는 인덱스가 저장되어 있는 것이다.

prices[4] 는 2라는 값을 가진다.
이 때, prices[st.top()] 과 2값을 비교하면, 3 > 2 가 된다.
가격이 전보다 떨어진 것이다.
이 때, st.top()과 현재 인덱스 i 와의 차이로 answer의 값을 정해준다. 그리고 스택에서 pop 해준다.

주식 가격이 전보다 떨어지는 경우 말고는 현재 인덱스가 스택에 푸시되었을 것이다.

인덱스가 0부터 시작 됨을 감안하여 스택이 빌 때까지 꺼낸다.

코드 2

#include <stack>
#include <vector>
using namespace std;

vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st; // 인덱스를 저장하는 스택 

    for(int i = 0; i < size; i++){ 

        // 스택이 비어있지 않고, 스택 top 인덱스의 값이 현재값보다 크다면, pop 
        while(!st.empty() && prices[st.top()] > prices[i]){
            // 가격이 이전보다 떨어졌을 떄 처리 
            answer[st.top()] = i-st.top();
            st.pop(); 
        }
        st.push(i); // 현재 인덱스를 푸시 
    }

    // 인덱스는 0으로 시작함을 감안하여 size-1 에서 st.top()을 빼준다
    while(!st.empty()){ 
        answer[st.top()] = size-st.top()-1;
        st.pop();
    }

    return answer;
}

문제

N과M(5) 백준 15654번

리뷰

1부터 N까지의 자연수가 아니라, 입력받은 N개의 수열을 이용한다.

중복을 허용하지 않고 2개 고르는 것이라서 중복체크를 위해 ch [10] 배열이 필요하다.

수열은 사전 순으로 증가하는 순으로 출력해야 하니까, 입력받자마자 sort() 했다.

코드

#include <iostream>
#include <algorithm> 
using namespace std;

// n과 m  (5)

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10]; // 입력받은 수열 저장.
int ch[10]; // 중복을 허용하지 않으니까, 체크 배열이 필요하다.
int answer[10];

void go(int index){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = 0; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0);

    return 0;
}

문제

N과M(6) 백준 15655번

리뷰

수열의 중복을 허용하지 않고, 사전 순으로 증가하는 순서로 출력해야 한다.

수열은 오름차순이어야 하므로 go 함수에 start 변수를 넣어서 이전 인덱스 보다 큰 인덱스부터 수열의 숫자를 고르도록 했다.

코드

#include <iostream>
#include <algorithm> 
using namespace std;

// n과 m  (6)
// 중복 허용 안 함. 오름차순 수열.

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10];
int ch[10];
int answer[10];

void go(int index, int start){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = start; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1, i+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0, 0);

    return 0;
}