메모장

문제 풀이 :

모든 작업의 요청 시점 시간 에서부터 작업이 완료되는 시간들의 평균값을 구하는 문제다.

문제는 Heap(힙) 카테고리에 있지만 우선순위 큐를 사용하지 않아도 풀리는 문제다.

첫번째 중요한점 : 평균은 최소의 원소끼리 합했을때 최소의 평균값이 나온다.

즉, 인자값으로 준 vector를 [작업의 소요시간]을 기준으로 오름차순 정렬을 해서 각 평균을 구하면 된다.

두번째 중요한 점 : [ 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다 ]

이 문장을 잘 봐야된다.  작업이 완료된 시점의 시간에 작업이 없으면 남은 작업 중 요청 시점이 제일 빠른것 부터 다시 평균을 구해주면된다. 

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

using namespace std;

bool compare(vector<int> a , vector<int> b)
{
     return a[1] < b[1];  
}

int solution(vector<vector<int>> jobs) 
{
    int answer = 0;
    int cur_time =0;
    bool check = false;
    
    vector<vector<int>> results = jobs;

    while(!results.empty())
    {
        check = false;
        sort(results.begin(),results.end(),compare);
        for(int i = 0; i < results.size(); i++)
        {
            if(cur_time >= results[i][0])
            {
                check  = true;
                answer += (cur_time - results[i][0]) + results[i][1];
                cout << cur_time << " "<< results[i][0]<< " "<<results[i][1]<<endl;
                cur_time += results[i][1];
                results.erase(results.begin() + i);
                break;
            }
        }

        if(!check)
        {
            vector<vector<int>> tmp = results;
            sort(tmp.begin(),tmp.end());
            cur_time = tmp[0][0];
            answer += tmp[0][1];
            cout << cur_time << " "<< tmp[0][0]<< " "<<tmp[0][1]<<endl;
            cur_time += tmp[0][1];
            tmp.erase(tmp.begin());
            results = tmp;
        }
    }
    
  cout <<answer;
    
    return answer / jobs.size();
}

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

//알고리즘 헤더에 sort 함수에 비교자 변경해서 풀었음
//비교자에서 해당 수자를 문자열로 바꾸고 문자열 제일 앞 숫자가 같으면
//해당 숫자문자열을 합친뒤 크기를 비교하여 true인경우 정렬을 하는식으로

//비교자의 해당 숫자의 문자열 앞이 다른경우 대소비교하여 true인경우 정렬 

using namespace std;

bool compare(int a, int b)
{
     string str_lhs = to_string(a) ;
     string str_rhs = to_string(b) ;
    
    switch(str_lhs.front() == str_rhs.front() )
    {
        case true:
            if(str_lhs+str_rhs > str_rhs + str_lhs) { return true;}
            break;
        case false:
            if(to_string(a).front() > to_string(b).front())  {return true;} 
            break;
    }
  
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";
        
    sort(numbers.begin(),numbers.end(),compare);
   
    //정렬된 배열 제알 앞이 0인경우 숫자 완성이 안됬기에 0문자열 리턴 
    if(numbers.front() == 0 ) { return "0";}
    
    for(int num : numbers) {  answer += to_string(num);}

    return answer;
}

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


string solution(string s, string skip, int index) {
    string answer = "";
    
    
    //sort 정렬 : 시간복잡도 N , 우선순위 큐 : 시간복잡도 : log n
    //이기에 우선순위큐를 이용하여 minheap으로 정렬함
    priority_queue<char,vector<char>,greater<char>> pq_skip;
    for(char ch : skip) {  pq_skip.push(ch);}
    
    
    char pivot = 'a'; //알파벳 배열에 넣을 시작 문자
    vector<char> alpabet;
    while(pivot <= 'z') 
    {
        //해당 알파벳이 skip문자열에 있는경우 알파벳 배열에 넣지 않는다.
        if( pq_skip.top() != pivot) { alpabet.push_back(pivot); }
        else { pq_skip.pop(); }
        pivot++;
    }
        
    //문자열 s 길이만큼 순회하며 문자를 변환한다.
    int result;
    for(int i = 0; s.size() >i;i++)
    {
        //문자열 s의 단일문자가 알파벳배열의 어디에 위치하는지 찾는다.
        int alpabet_index = find(alpabet.begin(),alpabet.end(),s[i]) - alpabet.begin();
        
        //찾은 단일문자위치에 인자값index를 더하여 최종 위치를 찾는다.
        result = alpabet_index + index;
        //만약 알파벳 사이즈를 초과한 경우 , 알파벳 사이즈만큼 뺀다.
        while(result> alpabet.size()-1 )
        {
            result -= alpabet.size();
        }
        
        answer += alpabet[result];
    }
    
    
    return answer;
}

#include <string>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

//체육복 빌려주는 조건 : 자기 앞,뒷 1번호 만큼 가능
//체육수업을 들을수있는 학생의 최댓값 return 
//여벌 체육복을 가져온 학생도 도난 가능,체육복을 빌려줄수 없음 하지만 자기것는 있음

bool reserve_check(int index, map<int,int>& students)
{
    //iter = 자신의 앞 또는 뒤 학생의 iter
    map<int,int>::iterator iter_before = students.find(index);
    
    //해당 학생이 없을수도 있기에(제일 앞학생 또는 제일 뒷학생 고려)
    //여벌 체육복이 있으면 해당 학생의 체육복을 -1 시킴
    if(iter_before  != students.end() && iter_before->second == 2)
    {
        iter_before->second--;
        return true;
    }  
    
    return false;
}


int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    map<int,int> students; //학생번호,체육복 수
    
    //여벌 체육복이 있는 학생을 맵에 추가
    for(int num : reserve) {  students.insert({num,2}); }
    
    //체육복을 잃어버린 학생을 맵에 추가
    for(int num : lost)
    {
        //해당 맵에 여벌 체육복을 갖고 있지만 잃어버린 학생이 있을수 있기에 find 실행
         map<int,int>::iterator iter = students.find(num);
        //find결과가 없으면 해당 체육복이 없는 학생으로 추가
        if(iter  == students.end()) {  students.insert({num,0}); }
        //find 결과가 있으면 해당 학생의 체육복 수를 1감소
        else {  iter->second--;}
    }
    
    for(int i=1; i <= n ; i++)
    {
        map<int,int>::iterator iter = students.find(i);
        
        //해당 학생이 map에 없으면 수업을 들을 수 있기에 answer후 순회
        if(iter == students.end()) {  answer++;  continue;}
        
        //해당 학생이 체육복이 없는경우
        if(iter->second == 0)
        {
            //자기 앞,뒷 번호의 여벌 체육복을 체크후 true인경우 해당 학생의 체육복을 1증가
           if(reserve_check(i-1,students) || reserve_check(i+1,students))  iter->second++; 
        }
        
        //해당 학생이 체육복이 1개 이상인경우 answer증가 
        if(iter->second >=1) {  answer++; } 
        
    }

    
    
    return answer;
}

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

//1.메인벨트와  적재 박스 비교
//2.같은경우 벨트와 적재박스 큐에서 제외 후 ,answer증가
//3.다른경우 서브벨트 top과 비교해서 같은경우 stack과queue에서 제외후 answer증가
//3.둘다 다른경우 서브벨트에 적재

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

    queue<int> q_order; // 기사님이 원하는 택배 순서
    queue<int> main_belt;// 메인 컨테이너벨트
    stack<int> sub_belt; // 서브 컨테이너벨트
    
    //택배차의 원하는 택배순서를 queue로 저장
    for (int i = 0; i < order.size(); i++)
    {
        main_belt.push(i + 1); 
        q_order.push(order[i]); 
    }

    while (!q_order.empty())
    {
        //메인 벨트의 택배와 택배차의 order list와 비교
        if (!main_belt.empty() && q_order.front() == main_belt.front())
        {
            answer++;
            q_order.pop();
            main_belt.pop();
        }
        //서브 벨트의 택배와 택배차의 order list와 비교
        else if (!sub_belt.empty() && q_order.front() == sub_belt.top())
        {
            answer++;
            q_order.pop();
            sub_belt.pop();
        }
        //메인 벨트의 서브 벨트 둘다 택배가 없는경우
        else
        {
            //메인 벨트에 택배가 있으면 서브벨트에 해당 택배를 보관 후 다시 순회
            if (!main_belt.empty())
            {
                sub_belt.push(main_belt.front());
                main_belt.pop();
            }
            //메인 벨트에 택배가 없으면 더이상 할 수 없으므로 탈출후 반환
            else { return answer; }
        }

    }

    return answer;
}

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

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    //A라는 사람의 topping map
    map<int,int>  map_A;
    //A의 빵에 모든 토핑을 올려놓기
    for (int elements : topping)
    {
        map<int, int> ::iterator iter = map_A.find(elements);

        if (iter != map_A.end()) iter->second++;
        else  map_A.insert({ elements,1 });
    }
    
     //A라는 사람의 topping map
    map<int, int> map_B;
    
     //토핑의 갯수만큼 순회를 하며 A의 토핑을 B한테 하나씩 주며 체크하기
    for (int i = 0; i < topping.size(); i++)
    {
        int pivot = topping[i];
 
        //map_A의 원소 제거 (B한테 하나 주기)
        map<int, int> ::iterator iter = map_A.find(pivot);
        if (iter != map_A.end())
        {
            iter->second--;
            if (iter->second <= 0) map_A.erase(iter);
        }

        //map_B의 원소 추가 (A한테서 받은 토핑 추가하기)
        iter = map_B.find(pivot);
        if (iter != map_B.end()) iter->second++;
        else  map_B.insert({ pivot,1 });

        //각 토핑의 map갯수가 같은지 체크 
        if (map_A.size() == map_B.size()) answer++;
    }

    return answer;
}

[재귀함수 장점] -> 가독성 Up

1.변수의 사용을 줄일 수 있다.

2.알고리즘 자체가 재귀함수에 어울리는 경우 ex)Tree 

[재귀함수 단점] -> 시간증가 , 스택오버플로우 발생 

1.함수를 호출이 반복적으로 일어나기에 시간이 반복문보다 더 걸릴 수 있다.

2.함수 호출시마다 스택영역에 메모리가 쌓여서 결국 스택 오버 플로우 발생이 된다.

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

int solution(int x, int y, int n) 
{
    int answer = 0;

    vector<int> dp;
    for (int i = 0; i < y + 1; i++) { dp.push_back(-1); }//dp 배열 data값을 전부 -1 초기화

    dp[x] = 0; // 초기 시작값 설정
   
    for (int i = x; i < y + 1; i++)
    {
        //해당 dp[i]에는 접근하지 않았기에 넘어감
        if (dp[i] == -1) continue;

        if (i * 2 <= y)
        {
            //계산한 값이 -1이면 접근하지 않았기에 바로 dp에 계산값을 초기화
            if (dp[i * 2] == -1) { dp[i * 2] = dp[i] + 1; }//해당 dp자리에 연산 횟수data가 있는경우 최소값을 골라서 초기화
            else { dp[i * 2] = min(dp[i] + 1, dp[i * 2]); }
        }

        if (i * 3 <= y)
        {
            if (dp[i * 3] == -1) { dp[i * 3] = dp[i] + 1; }
            else { dp[i * 3] = min(dp[i] + 1, dp[i * 3]); }
        }

        if (i + n <= y)
        {
            if (dp[i + n] == -1) { dp[i + n] = dp[i] + 1; }
            else { dp[i + n] = min(dp[i] + 1, dp[i + n]); }

        }
    }
    //dp배열 길이만큼 순회 후 dp[y]에 도달한 연산 횟수 값을 반환 
    return dp[y];
}

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

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(long long i =0; i < numbers.size() ; i++)
    {
        long long number = numbers[i];
        long long index_0 = 0; //처음보는 0의 index
        
        //number를 이진법으로 변환하며 처음 만나는 0 찾기
        while(number > 0)
        {
            if(number % 2 == 0) { break; } // 해당 이진법의 자리가 0인경우 탈출
            index_0++; //0이 아닌경우 index가 증가함
            number *= 0.5;
        }

        //0뒤의 숫자1의 index를 알아야하기 때문에 -1을 계산
        if(index_0 > 0) { index_0 -= 1;} 

        //number에 더해줄 2^count 를 구함
        long long sum = 1;
        for(long long i =0; i< index_0; i++) {  sum *= 2;}
        
        answer.push_back(numbers[i] + sum);
    }
    return answer;
}