C++ Level1 - 나머지 문제들(?) 2

1. 소수 만들기(Summers/Winter Coding(~2018)

• 알고리즘  서술

1. 배열 중 3개의 합 구하기

2. 합의 소수 판별하기 -> 소수 구별 함수 생성하기

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

bool chkprime(int sum){
    if(sum==0||sum==1) //소수는 2부터
        return false;
    for(int i=2;i<sum/2;i++){ 
        // 에라토스테네스 : 굳이 sum 까지 돌릴 필요 없음 그래서 sum/2
        if(sum%i==0) // 소수 아님
            return false;
    }
    return true; // 소수!
}

// nums_len은 배열 nums의 길이입니다.
int solution(vector<int> nums) {
    int cnt = 0;
    sort(nums.begin(),nums.end());
    for(int i=0;i<nums.size();i++){
        for(int j=i+1;j<nums.size();j++){
            for(int k=j+1;k<nums.size();k++){
                int sum=nums[i]+nums[j]+nums[k];
                if(chkprime(sum)==true){
                    cnt++;
                }
            }
        }
    }
    return cnt;
}

---

2. 체육복(탐욕법 : Greedy)

Greedy :: 현재 시점에서의 최적의 선택을 하는 알고리즘. 당장 그 시점에서의 최선의 답을 찾는 방식

 

• 알고리즘 서술

1. 모든 학생들에게 체육복 1개 set

2. 도난 학생들 체육복 --

3. 여분 학생들 체육복 ++

4. for문으로 체육복 여부 확인 진행

4.1) 체육복이 있는 경우 1. 앞사람 확인 , 2. 뒷사람 확인

5. 출력

#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {//lost : 도난, reverse : 여벌
    int answer = 0;
    vector<int>cnt(n,1);//n개 1로 초기화
    //체육복 갯수 조정
    for(auto l:lost){ //for(int i=0;i<lost.size();i++)
        cnt[l-1]--; //체육복 도난
    }
    for(auto r:reserve){
        cnt[r-1]++;// 체육복 여벌
    }
    
    
    for(int i=0;i<cnt.size();i++){
        if(cnt[i]==0){//1. 체육복이 없는 경우
            if(cnt[i-1]==2){ 
                // 앞사람 여분이 있는지 확인하고 빌리기
                cnt[i]++;
                cnt[i-1]--; // 한개 빌려줌
            }else if(cnt[i+1]==2){ //뒷사람 여분 확인하고 빌리기
                cnt[i]++;
                cnt[i+1]--; // 빌려줌
            }
        }
    }
    
    for(auto c:cnt){
        if(c!=0)
            answer++;
    }
    
    
    return answer;
}

 

• 개선점

for문에서 int i 이런식으로 계속 돌렸는데 for(auto i:vec)문을 사용하여 좀더 간결하게 작성하게 됨

---

3. 완주하지 못한 선수 (Hash)

1) 해시 사용 X - 정답 아님!

• 알고리즘 순서

1. par, comp 정렬

2. par과 비교

2.1) 같으면 pass

2.2) 다르면 출력하기

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

using namespace std;

string solution(vector<string> par, vector<string> comp) {
    string ans = "";
    sort(par.begin(), par.end());
    sort(comp.begin(), comp.end());
    vector<string>vc;
    for(int i=0;i<par.size();i++){
        for(int j=0;j<comp.size();j++)
            if(par[i]!=comp[j]){
                //vc.push_back(par[i]);
                ans=par[i];
            }
    }
    return ans;
    
}

test 3에서 error

2) 해시 사용 - Hash Map 

Hash :: key-value 쌍으로 데이터를 저장하는 자료구조

 

풀이)

https://coding-grandpa.tistory.com/89

[프로그래머스] 완주하지 못한 선수 (해시 Lv. 1) - C++

1. hash map인 map 생성

2. par의 선수이름과 value를 map에 넣어줌

2.1) map에 par 가 있으면 ++ => 동명이인 때문

3. map에서 comp선수 빼기

4. 전체 map 돌면서 value가 0이 아닌것 찾기

 

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
string solution(vector<string> par, vector<string> comp) {
    string ans = "";
    unordered_map<string,int>map;
    for(int i=0;i<par.size();i++){ // par를 돌면서 
        if(map.end()==map.find(par[i])){ //map에 이 선수가 없다면
            // par에 있는 사람 map에 추가
            map.insert(make_pair(par[i],1)); 
        }
        else{ //map 에 이 선수가 있다면
            map[par[i]]++; //map의 par[i]값이 1로 증가 -> 동명이인때문
        }
    }
    
    
    // 완주 선수 빼기
    for(int i=0;i<comp.size();i++){
        map[comp[i]]--; //comp[i] 선수의 value 값을 뺀다
    }
    
    
    for(int i=0;i<par.size();i++){
        if(map[par[i]]>0){ // map에서 value가 0이 아닌 참가자 찾기
            ans=par[i];
            break;
        }
    }
    return ans;
}