JArchive 프로그래밍 일기

Mini-Max Sum

Algorithm Warmup

코드포스에서 유용한 벡터 함수 포스팅을 봐서 문제에 써먹었다.

배열에서 원소의 값을 처음부터 끝까지 누적해서 더할때 반복문 필요 없이 아래처럼 가능하다.

accumulate() 함수가 있다.

int sum = accumulate(all(), 0LL); 
// 여기서 0LL은 0과는 다르다. 

코드

void miniMaxSum(vector<int> arr) {

    sort(arr.begin(), arr.end());
    long long sum = accumulate(arr.begin(), arr.end(), 0LL);

    cout << sum-arr[arr.size()-1] << ' ' << sum - arr[0];
}

문제

스킬 트리 프로그래머스 level2

리뷰

스킬트리에서 스킬에 포함된 문자만 벡터에 넣는다.

스킬의 인덱스와 스킬트리에서 뽑아낸 인덱스가 일치하는지 확인한다.

예를 들어, 스킬 "CBD" , 스킬트리는 "BACDE" 일 때 아래의 과정을 거친다.

스킬 "CBD" 에서. 차례로 "B", "A", "C" ... 를 찾아본다.

for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 
    int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
    if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
}
// 반복문이 끝나면 벡터 v에 저장되는 원소들 {1, 0, 2}

왜냐하면 스킬에서 B를 찾으면 idx == 1

스킬에서 A를 찾으면, 없으니까 idx == -1 (push 안 한다)

스킬에서 C를 찾으면, idx == 0

스킬에서 D를 찾으면 idx == 2

스킬의 인덱스와 벡터에 들어간 인덱스가 일치하는지 확인한다.

for (int k = 0; k < v.size(); k++) { // 벡터 v의 크기 만큼 순회
    // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
    if (v[k] != k) {
        flag = false; break;
    }
} 

코드

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

int solution(string skill, vector<string> skill_trees) {

    int skill_len = skill.length(); // 스킬 문자열의 길이 
    int answer = 0;

    for (int i = 0; i < skill_trees.size(); i++) { // 스킬트리들의 개수 만큼 반복  
        string str = skill_trees[i]; // 스킬트리 하나. 
        vector<int> v;

        for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 

            int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
             if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
        }

        bool flag = true;

        for (int k = 0; k < v.size(); k++) { 
            // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
            if (v[k] != k) {
                flag = false; break;
            }
        }

        if (flag) answer++;
    }

    return answer;
}

참고할 만한 코드

'스킬'에 포함되지 않은 알파벳을 전부 지운다. erase() 이용.

/*
스킬이 "CBD" 라면,  
"BACDE"--> "AE" 
"AECB" --> "CB" 
"CBADF"--> "CBD"
*/

제거 후의 문자열의 길이 만큼 '스킬' 알파벳을 확인한다.

"CB"가 결과물인 경우, 스킬도 "CB"까지만 확인한다. 일치한다면 '가능한 스킬트리'다.

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

int solution(string skill, vector<string> skill_trees) {
    int skill_len = skill.length();
    int answer = 0;

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

        // 스킬 순서에 포함되지 않는 스킬들 제거.
        for (int j = 0; j < skill_trees[i].size(); j++) {

            if (skill.find(skill_trees[i][j]) == string::npos) {

                skill_trees[i].erase(j, 1); // j인덱스부터 1개 제거.
                // erase 함수가 실행되면 배열의 뒷 요소들이 자동으로 한칸씩 당겨짐.
                // j 인덱스 감소시켜야 모든 원소를 빠짐없이 확인 가능.
                j--;
            }    
        }
        // 스킬순서 문자열 에서 skill_trees[i] 문자열 길이만큼 잘라낸다 
        string temp = skill.substr(0, skill_trees[i].size()); 

        if (skill_trees[i] == temp) {
            answer++;
        }        
    }

    return answer;
}

문제

카펫 프로그래머스 level2

리뷰

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

카펫의 갈색 격자의 수, 노랑 격자의 수가 주어진다. 카펫의 가로 길이, 세로 길이를 맞춰야 한다.

brown + yellow 를 합치면 카펫의 면적을 알 수 있다.

가로 X 세로 == 면적 이 된다.

예를 들어, 면적이 12라면, 12의 제곱근(면적의 제곱근) 부터 3까지 탐색하면 세로의 길이를 얻을 수 있다.

세로가 3 이상이 되어야 brown이 yellow를 한 줄이라도 둘러쌀 수 있다.

세로가 2라면, yellow 격자는 생길 수 없기 때문이다.

long long sum = brown + yellow; // 면적 
long long hori = 3;  // 세로
long long ver = 1;   // 가로 
int limit =  sqrt(sum); // 면적의 제곱근 

for(hori = 3; hori <= limit; hori++){ // 세로 hori 구하기 

    if( sum % hori == 0){ // 면적과 나누어 떨어지는 세로 길이 발견.
        ver = sum/hori;  // 가로 길이가 정해짐.

    }
}

면적과 나누어 떨어지는 세로 길이를 구했을 때, 아래의 조건을 만족하는지 확인하여 격자의 개수까지 맞춰본다.

(ver-2)*(hori-2) == yellow  

가로 기준으로 봤을 때, brown이 둘러싼 맨 위 한 줄, 맨 아래 한 줄을 빼면 ( hori - 2 ) 가 된다.

세로 기준으로 봤을 때도 맨 왼쪽, 맨 오른쪽 세로줄을 2개 빼면, ( ver - 2 ) 가 된다.

이렇게 격자의 개수를 확인하는 이유는, 특정 면적을 만족시킬 수 있는 가로, 세로의 길이는 여러개가 나올 수 있기 때문이다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <functional>
#include <algorithm> 
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    long long sum = brown + yellow; // 면적 
    long long hori = 3;  // 세로
    long long ver = 1;   // 가로 
    int limit =  sqrt(sum); // 면적의 제곱근 

    for(hori = 3; hori <= limit; hori++){ // 세로 구하기 

        if( sum % hori == 0){
            ver = sum/hori; 

            if( (ver-2)*(hori-2) == yellow ){
                answer.push_back(ver); // 가로 
                answer.push_back(hori); // 세로 
                break;                
            }

        }
    }

    return answer;
}

문제

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