코딩생존기

코딩 문제는 머리로는 어떻게 풀 지 생각이 되는데 그걸 언어로 구현을 생각하기 어렵다. 천천히 풀어 보았다. 

일단 중요한 것은 스테이지 별로 클리어 하지 못한 사용자 수를 저장해야하고

스테이지를 깨고 다음 스테이지에 간 사람도 알고 있어야한다. 

생각을 해보니 

일단 첫번째에 실패한 사람은 다음 스테이지는 당연히 실패하는 것이여서

전체 수를 체크해두고 뺴주는 식으로 가면 된다.

그리고 실패율과 스테이지는 vector 안에 pair 자료형을 통하여 저장하고 정렬은 정렬함수를 만들어서 정렬을 할 수 있게 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<double,int> &a,pair<double,int> &b){
    if(a.first==b.first) return a.second < b.second;            //실패율 같다면 숫자 큰 순으로
    else return a.first > b.first;
}

int cnt[501];            //스테이지별 클리어하지 못한 사용자 수
vector<pair<double,int>> failure;           //스테이별 실패율 저장할 벡터
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    int st= stages.size();
    for(int i=0;i<st;i++){
        cnt[stages[i]]++;           //스테이지별 클리어하지 못한 사용자 수 저장
    }
    int tmp=st;
    for(int i=1;i<=N;i++){
        
        if(cnt[i]==0) failure.push_back({0,i});     //실패한 사람이 없다면 실패율은 0
        else{
            double t=(double)cnt[i]/tmp;             //실패율 계산
            
            failure.push_back({t,i});
        }
        
        tmp-=cnt[i];         //해당단계에서 실패했다면 다음단계도 실패 총 인원 줄이기
    }
    sort(failure.begin(),failure.end(),compare);
    
    int fsize=failure.size();
    
    for(int i=0;i<fsize;i++){
        auto p =failure[i];
        answer.push_back(p.second);
    }
    
    return answer;
}

숫자 n 까지의 소수를 찾는 문제이다. 처음에는 n까지 for 문을 돌면서 소수를 판별하는 함수로 개수를 세려고 했는데 이렇게 해보니

 효율성 테스트에서 시간초과가 떴다. 왜 그런지 생각해보니 for문을 돌면서 계속 검사를 하면 O(N^2)로 시간복잡도가 계산되기 때문에 실패하는 것이였다. 

방법을 찾아보니 에라토스테네스의 체 라는 방법을 사용하면 시간을 많이 줄일 수 있다고 해서 이 방법을 익히고 사용해 보기로 하였다. 

에라토스테네스의 체

에라토스테네스의 체를 설명한 그림이다. 

소수 인것을 찾고 소수의 배수를 찾아 체크하는 과정을 반복하면 체크하지 않은 것이 소수이여서 이런 방식으로 소수를 찾을 수 있다.

전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<bool> v(n+1,true);
    
    for(int i=2;i<=n;i++){              //전체 순회
        if(v[i]){               //소수라면
            for(int j=2;j*i<=n;j++){            //배수 찾기
                v[i*j]=false;               //배수는 소수가 아니다.
            }
            answer++;
        }
    }
    return answer;
}

숫자의 조합을 만들어서 소수인지 판별하면 되는 문제이다.

조합은 3중 for문을 사용해서 구현하였으며 소수 판별은 시간복잡도를 줄이기 위해 sqrt(num) 값까지만 계산하게 해두었다.

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num){
    if(num<=2) return false;
    for(int i=2;i<=sqrt(num);i++){          //시간복잡도 줄이기
        if(num%i==0) return false;
    }
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;

    for(int i=0;i<nums.size();i++){
        for(int j=i+1;j<nums.size();j++){
            for(int h=j+1;h<nums.size();h++){
                int n= nums[i]+nums[j]+nums[h];     //조합고려
                if(isPrime(n)){
                    answer++;
                }
            }
        }
    }
    return answer;
}

일주일은 7일이고 1월1일부터 날짜를 세서 7로 나눈 나머지를 요일로 선택하게 하는 방법으로 하기로 했다.

이때 1월1일이 금요일이라서 요일 배열의 1번째 값을 금요일로 해두었다.

#include <string>
#include <vector>

using namespace std;

string solution(int a, int b) {
    string answer = "";
    int month[]={31,29,31,30,31,30,31,31,30,31,30,31};
    string day[]= {"THU","FRI","SAT","SUN","MON","TUE","WED"};
    int sum=b;
    for(int i=0;i<a-1;i++){
        sum+=month[i];
    }
    
    answer=day[sum%7];
    return answer;
}

처음에는 둘다 2진수로 바꾸고 비교를 해보면 되겠다고 생각을 했는데 비트연산자를 사용해서 미리 연산을 해두고 2진수 변환을 하면 더 좋다는 걸 알게되어서 그렇게 구현해 보았다

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

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    int a,b;
    for(int i=0;i<n;i++){
        string tmp="";
        arr1[i]=arr1[i] | arr2[i];      //비트 OR연산해서 하나라도 1이면 1 
        
        while(tmp.size()!=n){       //2진수변환과 동시에 지도 만들기
            if(arr1[i]%2==0){
                tmp.push_back(' ');
            }else{
                tmp.push_back('#');
            }
            arr1[i]/=2;
        }
        reverse(tmp.begin(),tmp.end());
        answer.push_back(tmp);
    }
   
    return answer;
}

유클리드 호제법을 통해 최대공약수를 구할 수 있다 

유클리드 호제법

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

#include <string>
#include <vector>

using namespace std;

int gcd(int a,int b)            //유클리드 호제법
{
    if(b==0) return a;
    else return gcd(b,a%b);     
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int gcd_num = gcd(max(n,m),min(n,m));
    
    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);                //최소공배수 = 기존 두 수의 곱 / 최대공약수
    return answer;
}

다리가 견딜 수 있는 무게만큼을 검사하고 순서대로 트럭을 보내면 된다. 

만약 그 다음 트럭이 견딜 수 있는 무게 이상이 된다면 0인 트럭을 추가해서 그 전 트럭을 계속 이동시켜주면 된다.

#include <string>
#include <vector>
#include <queue>
//1.초를 어떻게 셀것인가 -> 무게가 0인을 자동차를 추가하자 및 초 추가
//2.자동차무게의 합이 다리가 견딜 수 있는 무게보다 크다면? -> 0추가
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    queue<int> que;

    int weightSum = 0;        //자동차 무게합 
    int i = 0;                //인덱스
    while (1) {
        int curWeight = truck_weights[i];
        if (i == truck_weights.size()) {            //마지막 값만 남았을경우 
            time += bridge_length;                //다리길이 만큼 걸림
            break;
        }

        if (que.size() == bridge_length) {          //다리길이 만큼 이동했다면
            weightSum -= que.front();             //다리끝에 있는 자동차의 무게를 빼준다.
            que.pop();
        }
        if (weightSum + curWeight <= weight) {
            weightSum += curWeight;
            que.push(curWeight);
            i++;
        }
        else que.push(0);

        time++;
    }
    return time;
}

#include <string>
#include <vector>

using namespace std;
//4개의 블록을 파악 -> 제거 -> 밑으로 이동-> 다시 파악-> 반복
void fillEmpty(int m,int n,vector<string>& board){  //빈공간을 내려주는 함수
    for(int j=0;j<n;j++){
        string tmp="";
        for(int i=m-1;i>=0;i--) if(board[i][j]!= ' ') tmp+=board[i][j];     //채워져있는 칸이라면 tmp에 모두 추가
        int i=m-1;          //젤 끝에서부터
        for(auto c: tmp) board[i--][j]=c;       //tmp에서 하나씩 꺼내서 젤밑에서부터 추가
        for(;i>=0;i--) board[i][j]= ' ';         //나머지는 빈칸으로
    }
    
}

bool is_erase(int i,int j,vector<string>& board,vector<vector<bool>>& vis){
    if(board[i][j]!=board[i+1][j]||
      board[i][j]!=board[i][j+1]||
      board[i][j]!=board[i+1][j+1]) return false;
    vis[i][j]=true;
    vis[i+1][j]=true;
    vis[i][j+1]=true;
    vis[i+1][j+1]=true;
    return true;
}
int solution(int m, int n, vector<string> board) {
    int answer = 0;
    vector<vector<bool>> vis(m,vector<bool>(n,false)); //2차원 bool벡터 선언 및 초기화
    
    while(1){
        bool done=true;
        fill(vis.begin(),vis.end(),vector<bool>(n,false)); //2차원 bool 벡터 초기화
        for(int i=0;i<m-1;i++){         //비교를 위해 m-1,n-1까지
            for(int j=0;j<n-1;j++){
                if(board[i][j]!= ' ' && is_erase(i,j,board,vis)) done = false;
                //공백이 아니고 지울 수 있다면 방문체크 및 계속진행
            }
        }
        if(done) break;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(vis[i][j]) board[i][j] = ' '; //방문처리한=> 즉 지울 수 있는 칸은 지운다.
            }
        }
        fillEmpty(m,n,board); //빈공간 내리기
    }
    for(auto s:board){
        for(auto c: s) if(c== ' ') answer++; //빈칸인 경우 지워진블록으로 추가
    }
    
    return answer;
}

초기 아이디어

각 행에서 최대값을 구하고 그 최대값의 다음행의 값을 0으로 바꿔주면서 최댓값들을 저장하는 방식

=> 코드 구현이 너무 길어진다.

=>DP로 구현하는게 좋다는 힌트를 보고 고민을 해보다가 DP 공부를 할겸 코드분석을 해서 풀어보았다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//DP=>초기값 설정해주고 2,3번째를 어떻게 구할지 생각해보면 된다.
//DP=>모든 경우의 수를 만들어서 사용하는 것
int solution(vector<vector<int> > land)
{
    int answer = 0;
    vector<vector<int>> dp(land.size(), vector<int>(4));     //땅의 사이즈만큼 미리 초기화해주기

    for (int i = 0; i < 4; i++) {
        dp[0][i] = land[0][i];            //초기값은 그대로 => DP 초기값설정
    }

    for (int i = 1; i < land.size(); i++) {
        for (int j = 0; j < 4; j++) {               //2차원 땅배열 순회
            int max = 0;
            for (int k = 0; k < 4; k++) {
                if (k == j) continue;
                if (max < dp[i - 1][k])
                    max = dp[i - 1][k];
            }
            dp[i][j] = land[i][j] + max;        //땅배열과 같은크기의 DP배열을 하나하나 값을 완성시키기
        }
    }

    answer = *max_element(dp.back().begin(), dp.back().end());     //마지막행에 제일큰게 정답
    return answer;
}

힙구조를 사용하여 모든 음식의 스코빌 지수를 K 이상으로 만드는 것

힙구조는 priority_queue 를 사용하여 구현

※priority_queue에서 정렬를 부여해두려면 priority_queue<자료형, 구현체, 비교연산자> 로 우선순위 큐를 선언하면 된다. 

지금은 오름차순으로 정렬해야하니 priority_queue<int,vector<int>,greater<int>> pq 로 선언해 두었다.

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;          //정렬 조건 오름차순으로
    
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    }
    
    while(pq.size()>=2&&pq.top()<K){
        int first=pq.top();
        pq.pop();
        
       int second=pq.top();
        pq.pop();
        
        answer++;
        pq.push(first+second*2);
    }
    
    if(!pq.empty()&&pq.top()<K) return -1;
    
    return answer;
}