JArchive 프로그래밍 일기

문제

소수 찾기 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제다.

에라토스테네스의 체로 소수를 체크해야 하고. 주어진 숫자들로 순열을 만들면 된다.

핵심 코드

bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

1. 예를 들어 71까지의 소수를 구하려면 72 크기의 배열을 만든다.소수의 배수들은 소수가 아니기 때문이다.
   에라토스테네스 GIF를 참고하자
2. 소수를 만날 때 마다 (인덱스 값이 true 라면, ) 소수의 배수가 되는 인덱스들의 값을 전부 false로 만든다.
3. 구하려는 범위 만큼 bool 배열을 만들고, 배열의 인덱스를 전부 소수라고 생각하여 true로 초기화 한다.

순열 만들기오름차순으로 정렬되어 있다면, 예를 들어 대상 벡터가 [1, 2, 3] 이라면, [3, 2, 1] 이 될 때 까지 순열을 만들어서 리턴해준다.

2. 따라서 반드시 미리 오름차순 정렬이 되어 있어야 한다. [3, 2, 1] 인채로 넣으면 바로 종료된다.
3. #include <algorithm>
next_permutation(v.begin(), v.end())

코드

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


bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

int solution(string numbers) {

    sort(numbers.begin(), numbers.end(), greater<int>()); 
    // 내림차순 정렬 -> 숫자로 만들 수 있는 가장 큰 수 만들기.

    int maxnum = atoi(numbers.c_str()); // 문자열->숫자

    eratos(maxnum); // 소수 체크

    sort(numbers.begin(), numbers.end()); // 오름차순 정렬 (next_permutation 함수 활용을 위함.)

    set<int> answer_set; // 유효한 숫자를 중복없이 저장하기 위한 set

    do{
        // substr로 1자리 숫자 부터 확인 
        for(int i = 1; i <= numbers.size(); i++){
            int temp_num = stoi( numbers.substr(0, i) );
            if(prime[temp_num]){
                answer_set.insert(temp_num); // set에 넣어서 중복제거 
            }
        } 

    }while( next_permutation(numbers.begin(), numbers.end()) ); 

    return answer_set.size();
}

문제

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