작은시작

https://programmers.co.kr/learn/courses/30/lessons/42628

코드 설명

기존에는 문제처럼 priority_queue 두개를 할당해서 구현하다가 문제를 깨달았다. 큐를 두개 할당하고 문제를 풀때 최댓값을 지우고 최솟값을 지우는 과정에서 없어져야 할 숫자가 계속 남는 문제가 생긴다

(이를 해결하려면 cnt변수를 할당해서 넣고 빼는 횟수가 같다면 큐를 전부 비워주어야한다)

그래서 저는 아예 vector 하나에 할당하여 매번 sort시켜주고 앞,뒤에서 각각 빼주는 방식을 생각하였습니다. (시간복잡도는 더 늘어날듯..)

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
  vector<int> result;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    for(int i=0;i<operations.size();i++){
        bool I_flag=false;
        bool D_flag=false;
        string abc="";
        for(int j=0;j<operations[i].size();j++){
            
            if(operations[i][j]=='I'){
                I_flag=true;
                
            }
            else if(operations[i][j] == 'D'){
                D_flag=true;
                
            }
            else if(I_flag==true && operations[i][j]!=' '){
                abc+=operations[i][j];
            }
             else if(D_flag==true && operations[i][j]=='-'){ //최솟값삭제
                if(answer.size()>0)
                answer.erase(answer.begin());
                 break;
            }
            
            else if(D_flag==true && operations[i][j]=='1'){ //최댓값삭제
                if(answer.size()>0){
                    answer.erase(answer.begin()+answer.size()-1);
                }
            }
           
        }
        if(abc!=""){
            answer.push_back(stoi(abc));
 
        }
        sort(answer.begin(),answer.end());
    }
    
    if(answer.size()==0){
        result.push_back(0);
        result.push_back(0);
    }
    else{
    int N=answer.size();
  
    result.push_back(answer[N-1]);
    result.push_back(answer[0]);
    }
    return result;
}

https://programmers.co.kr/learn/courses/30/lessons/43163

코드 설명

cnt 변수를 이용하여 한 글자가 다른 걸 찾는다 -> 재귀

재귀를 돌면서 target과 일치한다면 그때까지의 level을 tmp 변수에 담아둬서 가장 빠른 과정으로 도착할 경우를 찾는다.

(이때 min을 쓸거면 초기 result값을 큰 값으로 지정해둬야 한다!!! 여기서 실수해서 디버깅함...)

또한 result가 변화없이 다시 main으로 돌아왔다면 target을 한 번도 만나지 않았다는 의미 이므로 0을 반환해준다.

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool visited[51];
int tmp;
int result=999;
int cnt;
void dfs(int level, string& begin, string& target, vector<string>& words) {
    if (begin == target) {
        tmp = level;
        result = min(tmp, result);

        return;
    }




    for (int i = 0; i < words.size(); i++) {
        if (!visited[i]) {
            cnt = 0;
            for (int j = 0; j < words[i].size(); j++) {
                if (words[i][j] != begin[j]) {
                    cnt++;
                }
            }
            if (cnt == 1) {
                visited[i] = true;
                cout << words[i] << " ";
                dfs(level + 1, words[i], target, words);
                visited[i] = false;
            }
        }

    }


}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;

    dfs(0, begin, target, words);



    if (result == 0) answer = 0;
    else {
        answer = result;
    }

    return answer;
}
int main() {

    solution("hit", "cog", { "hot", "dot", "dog", "lot", "log", "cog" });

    return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/43162

코드 설명

visited배열을 통해 네트워크가 형성될때마다 표시해줍니다. 재귀를 사용하였고 level로 넘어갈때 그전 i 를 이용하여 네트워크 형성하는지 체크후 재귀하게됩니다. 

기본 그래프 문제이므로 기억이 안난다면 백준 기본문제를 다시 풀어보면 좋을것 같습니다 !! 

(main문에서 항상 dfs는 0 으로 시작한다는 습관 없애자!)

코드 

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

bool visited[201];

void dfs(int level,int n,vector<vector<int>> &computers){
    visited[level]=true;
    
    for(int i=0;i<n;i++){
        if(!visited[i] && computers[level][i]==1){
            
            dfs(i,n,computers);
            
        }
    }
    
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

    for(int i=0;i<n;i++){
        if(!visited[i]) {
            answer++;
            dfs(i,n,computers);
        }
    }
    
    
    
    
    
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42626

코드설명

처음에는 K값이 이렇게 큰줄 모르고 단순 구현하였다... (scoville 벡터를 매번 sort하고 erase,push_back) 방식으로..

하지만 당연히 효율성에서 시간초과가 났고 아차싶었다

우선수위큐(minHeap)을 통해 O(N)으로 코드를 다시 짰다. 

그리고 pop()을 두번 하는과정이 있기때문에 중간에 큐가 빈건 아닌지 꼭 한번더 체크하자!!!!!!!!!!!!!!!!!!!!!!!

안하면 core dumped

코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;


priority_queue<int,vector<int>,greater<int>> pq;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    
    }
    int cnt=0;
    while(pq.top() < K && !pq.empty()){
        int temp=pq.top();
        pq.pop();
        temp=temp+pq.top()*2;
        if(pq.empty()) break;
        pq.pop();
        pq.push(temp);
        cnt++;
    }
    if(pq.empty()) answer=-1;
    else{
        answer=cnt;
    }
    
    
    return answer;
}