개발자 김수진

[문제]

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

[풀이]

스테이지의 실패율이 같을 경우, 스테이지 번호를 기준으로 오름차순 해야하므로  cmp 함수에서 second 값으로 비교해준다.

[코드]

#include <string>
#include <vector>
#include <algorithm>
#define MAX 501

using namespace std;

int people =0;
double score[MAX]={0,};
vector <pair<double,int>> v;

bool cmp(pair<double,int> a, pair<double,int> b){
    if(a.first > b.first)
        return true;
    else if(a.first == b.first) {
        if(a.second< b.second) {
            return true;
        } else
            return false;
    } 
    else
        return false;
}


vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    for(int i=1;i<=N;i++)   score[i] =0;
    people = stages.size();
    sort(stages.begin(), stages.end());
    int idx =0;
    int tmp_people = people;
    for(int i=0;i<people;i++){
        if(stages[i] > N)   continue;
        idx=i+1;
        int goal = 1;
        while(idx < people && stages[idx] == stages[i]){
            idx++;
            goal++;
        }
        double d =  (double)goal/tmp_people;
        score[stages[i]] =d;
        tmp_people -= goal;
        i = idx-1;
    }
    for(int i=1;i<=N;i++) 
        v.push_back({score[i],i});
    
    sort(v.begin(), v.end(),cmp);
    for(int i=0;i<N;i++)   answer.push_back(v[i].second);
    return answer;
}

문제

https://programmers.co.kr/learn/courses/30/lessons/82612?language=cpp 

풀이

단순 반복문 사용해서 최종 금액 구하는 문제

가지고 있던 금액의 범위가 1부터 1,000,000,00 까지 이므로 long long 사용

( int형 범위 -2,147,483,647 to 2,147,483,647 )

코드

using namespace std;

long long solution(int price, int money, int count)
{
    long long total =0;
    long long answer = -1;
    for(int i=1;i<=count;i++)
    {
        total+=price*i;
    }
    answer = total - money;
    if(answer <=0)  answer =0;
    return answer;
}

[문제]

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

[풀이]

특별한 알고리즘을 사용해서 해결해야되는 문제일줄 알았는데

내가 가장 많이 다루었던 DFS 알고리즘을 사용해 해결하는 문제라는게 놀라웠다.

한번 방문한 곳은 재방문 안해도 된다는 점에 있어서 이해가 안됐는데

모든 경로는 연결되어 있으므로 재방문을 고려하지 않아도 된다. 

[코드]

#include <string>
#include <vector>
#include <map>
#define MAX 200000

using namespace std;

vector<int> v[MAX];
int hang[MAX]={0,};
bool visited[MAX]={0,};
map <int,int> post;

void DFS(int idx)
{
    if(visited[idx])    return;
    if(post.find(idx) != post.end())
    {
        int pre = post.at(idx);
        if(!visited[pre])
        {
            hang[pre] = idx;
            return ;
        }
    }
    visited[idx]=true;
    DFS(hang[idx]);
    for(int i=0;i<v[idx].size();i++)    DFS(v[idx][i]);
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;

    for(auto tmp : path)
    {
        v[tmp[0]].push_back(tmp[1]);
        v[tmp[1]].push_back(tmp[0]);
    }
    
    for(auto tmp : order)    post.insert(make_pair(tmp[1], tmp[0]));
    
    if(post.find(0) != post.end() )   return false;
   
    visited[0]=true;
    for(int idx : v[0]) DFS(idx);
   
    for(int i=0;i<n;i++)    if(!visited[i]) answer= false;
    
    return answer;
}

[문제]

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

[풀이]

Union-Find 알고리즘을 사용해서 풀었다.

(Union-Find 알고리즘 : https://tnwlswkd.tistory.com/33 )

고객이 원하는 방이 아직 배정받지 않은 방이라면 해당 고객에게 배정해주고 map에 다음 칸의 방으로 초기화한다.

이미 배정받은 방이라면 Find 함수를 통해 해당 방을 기준으로 다음 방에서 비어있는 방을 찾아 배정해준다.

또한 배열이 아닌 맵을 사용한 이유는 k의 범위가 1 이상 10^12 이하이므로 배열을 사용하면  10^12 크기의 배열을 선언하여 메모리 부족이 발생하게 된다. 

항상 Union-Find 알고리즘 구현할 때, else 부분에서 초기화 해주는걸 깜박한다.

[코드]

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

using namespace std;

map <long long,long long > m;

long long Find(long long num)
{
    if(m[num]==0)
    {
        m[num]=num+1;
        return num;
    }
    else    return m[num]= Find(m[num]);
    
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for(int i=0;i<room_number.size();i++){
        long long room= room_number[i];
        if(m[room] == 0)
        {
            answer.push_back(room);
            m[room]=room+1;
        }
        else
        {
            long long res = Find(room);
            answer.push_back(res);
        }
    }
    return answer;
}

[문제]

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

[풀이]

반복문을 사용해 한 명씩 보내면서 구할 수 있다.

하지만 stones 배열의 길이가 200,000이므로 시간초과가 발생하여 효율성 부분에서 틀린다.

따라서 이분 탐색을 사용하여 찾아가는 방식으로 하였다.

(이분탐색 정리 : https://tnwlswkd.tistory.com/112 )

stones 배열에서 left는 1, 가장 큰 값으로 right를 초기화 한다.

중간 값을 구해가면서 left, right 값을 조절하여 건널 수 있는 학생수의 최댓값을 찾는다.

mid를 기준으로 mid 값보다 stones의 값이 작다면 mid만큼의 학생이 건너지 못하는 것이므로 cnt+=1을 해준다. 또한 이러한 경우가 연속으로 k번 이상이라면 mid 만큼의 학생이 건너지 못하므로 false를 return하여 mid 값을 조절한다.

이러한 방식으로 left>right일 때까지 반복하여 이분탐색을 통해 최댓값을 찾을 수 있다.

[코드]

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

using namespace std;
bool binary_search(vector<int> stones, int k, int mid)
{
    int cnt =0;
    for(int i=0;i<stones.size();i++)
    {
        if(stones[i] < mid )    cnt++;
        else    cnt=0;
        
        if(cnt >= k)    return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 1;
    int right = *max_element(stones.begin(),stones.end());
    
    while(left <= right){
        int mid = (left+right)/2;
        if(binary_search(stones,k,mid)){
            left = mid +1;
            if(answer < mid)    answer = mid;
        }
        else{
            right = mid -1;
        }     
    }
    return answer;
}

[문제]

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

[풀이]

앞쪽에 위치한 원소일수록 집합에 가장 많이 포함되어 있어

따라서 원소가 나온 내림차순 횟수를 정렬하여 

가장 많이 나타난 원소부터 answer에 insert

[코드]

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

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) {
	if (a.second > b.second) return true;
	return false;
}
vector<int> solution(string s) {
    vector<int> answer;
    map<int,int> m;
        
    string num = "";

    for(int i=1;i<s.size()-1;i++)
    {
        if(s[i] == ',' || s[i] == '}' || s[i]=='{')
        {
            if(num=="") continue;
            m[stoi(num)]++;
            num="";
        }
        else    num+=s[i];
    }
    vector<pair<int,int>> v( m.begin(), m.end() );
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++) answer.push_back(v[i].first);
    return answer;
}

[문제]

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

[풀이]

next_permutation 함수를 사용해 완전탐색으로 풀었다.

먼저 vector에 숫자와 연산자를 구분해서 담아줬다.

그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다.

우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식으로 풀었다.

 next_permutation 함수 : 순열을 구한다.

예를 들어 집합 { '+' , '-' , '*' }의 모든 순열을 구하면 아래와 같이 총 6가지가 나오게 된다.

{ '+' , '-' , '*'}

{ '+' , '*' , '-'}

{ '-', '+' , '*' }

{ '-' , '*' , '+'}

{ '*' ,'+' , '-' }

{ '*'  , '-' , '+'}

[코드]

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

using namespace std;

long long calc(long long a,long long b, char op)
{
    if(op == '-')   return a-b;
    else if(op == '+')  return a+b;
    else    return a*b;
}

long long solution(string expression) {
    long long answer = 0;
    vector <char> oper_list =  { '*', '+', '-' };
    vector <long long> number;
    vector <char> oper;
    string num = "";
    

    for(int i=0;i<expression.size();i++)
    {
        if(expression[i] == '+' || expression[i] =='*' || expression[i] == '-')
        {
            oper.push_back(expression[i]);
            number.push_back(atoi(num.c_str()));
            num="";
        }
        else    num+= expression[i];  
    }
    number.push_back(atoi(num.c_str()));
    long long _max =0;
    do{
        vector <char> tmp_oper = oper;
        vector <long long> tmp_num = number;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<tmp_oper.size();j++)
            {
                if(tmp_oper[j] == oper_list[i])
                {
                    tmp_num[j] = calc(tmp_num[j],tmp_num[j+1],oper_list[i]);
                    tmp_num.erase(tmp_num.begin()+j+1);
                    tmp_oper.erase(tmp_oper.begin()+j);
                    j--;
                }
            }
        } 
        if(_max < abs(tmp_num[0]))   _max = abs(tmp_num[0]);
    }while(next_permutation(oper_list.begin(),oper_list.end()));
    answer = _max;
    return answer;
}

[문제]

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

[풀이]

1,4,7을 누를경우 왼손

3,6,9를 누를 경우 오른손

나머지는 현재 왼손, 오른손의 위치를 기준으로 가까운 손으로 누르도록 구현

만약 거리가 같다면 왼손잡이,오른손잡이인지 확인하고 이에 맞게 누르도록

[코드]

#include <string>
#include <vector>

using namespace std;

struct pos{
    int x,y;
};

pos left = {3,0};
pos right = {3,2};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    for(int i=0;i<numbers.size();i++)
    {
        int num = numbers[i];
        
        if(num == 1 || num == 4 || num == 7)
        {
            answer += "L";
            left = {num/3,0};
        }
        else if(num == 3 || num == 6 || num == 9)
        {
            answer += "R";
            right = { num/3-1 , 2};
        }
        else
        {
            int x = num/3;
            int y = 1;
            if(num == 0)    x = 3;
            
            int ldis = abs(x-left.x) + abs(y-left.y);
            int rdis = abs(x-right.x) + abs(y-right.y);
            
            if(rdis < ldis)
            {
                answer += "R";
                right = {x,y};
            }
            else if(rdis > ldis )
            {
                answer += "L";
                left = {x,y};
            }    
            else
            {
                if(hand.compare("right") == 0)
                {
                    answer += "R";
                    right = {x,y};
                }
                else
                {
                    answer += "L";
                    left = {x,y};
                }
            }
        }
    }
    return answer;
}