알고리즘 문제풀이/프로그래머스

다시 풀어보는 2020 카카오 인턴십 코딩테스트 풀이

닷넷 지키미 백발백준 2021. 12. 20. 23:00

올해 카카오 블라인드 채용을 준비하면서 다시 풀었던 2020 카카오 인턴십 코딩테스트 풀이를 작성하고자 합니다.

당시 풀었던 풀이는 해당 글을 참고하시면 됩니다.

당시에도 5번은 풀지 않았고, 이번에도 풀지 않았으므로 제외합니다.

 

1번의 경우 전체적으로 구현이 더러웠던 것을 제거하였습니다.

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> key = {{3, 1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};

string solution(vector<int> numbers, string hand)
{
    string answer = "";
    pair<int, int> left = {3, 0}, right = {3, 2};
    for(int num : numbers)
    {
        //왼쪽 열 입력
        if(key[num].second == 0) answer.push_back('L'), left = key[num];
        //오른쪽 열 입력
        else if(key[num].second == 2) answer.push_back('R'), right = key[num];
        else //가운데 열 입력
        {
            //왼쪽, 오른쪽 거리 구하기
            int left_dir = abs(left.first - key[num].first) + abs(left.second - key[num].second);
            int right_dir = abs(right.first - key[num].first) + abs(right.second - key[num].second);
            
            //왼쪽의 거리가 더 짧은 경우
            if(left_dir < right_dir) answer.push_back('L'), left = key[num];
            //오른쪽의 거리가 더 짧은 경우 || 두 엄지손가락의 거리가 같으면서, 오른손잡이인 경우
            else if(left_dir > right_dir || hand == "right") answer.push_back('R'), right = key[num];
            //두 엄지손가락의 거리가 같으면서, 왼손잡이인 경우
            else answer.push_back('L'), left = key[num];
        }
    }
    return answer;
}

 

2번의 경우 Python으로 푼 것을 C++로 다시 풀었습니다.

#include <bits/stdc++.h>
using namespace std;

long long solution(string expression)
{
    long long answer = 0;
    vector<string> priors = {"+-*", "+*-", "-*+", "-+*", "*+-", "*-+"};
    
    for(string prior : priors)
    {
        string oper;
        vector<long long> number;
        int now = 0;
        for(char ch : expression)
        {
            if(isdigit(ch)) now = now * 10 + (ch - '0');
            else
            {
                oper.push_back(ch);
                number.push_back(now);
                now = 0;
            }
        }
		number.push_back(now);
		
        for(char ch : prior)
        {
            for(int i = 0;i < oper.length();)
            {
                if(oper[i] == ch)
                {
                    if(ch == '+') number[i] += number[i + 1];
                    else if(ch == '-') number[i] -= number[i + 1];
                    else number[i] *= number[i + 1];
                    number.erase(number.begin() + i + 1);
                    oper.erase(oper.begin() + i);
                }
                else i++;
            }
        }
        answer = max(answer, abs(number[0]));
    }
    return answer;
}

 

3번의 경우 unorder_map을 배제한 풀이로 변경하였습니다.

#include <bits/stdc++.h>

using namespace std;

bool check(vector<int>& vec)
{
    bool ret = true;
    for(int x : vec) ret = (ret && x);
    return ret;
}

vector<int> solution(vector<string> gems)
{
    map<string, int> jewels;
    vector<int> kinds;
    for(string gem : gems)
    {
        if(jewels.find(gem) == jewels.end())
        {
            jewels[gem] = kinds.size();
            kinds.push_back(0);
        }
    }
    
    int n = gems.size();
    int front = 0, back = 0;
    vector<int> answer = {1, n};
    while(front < n && back < n)
    {
        while(front < n && !check(kinds))
        {
            kinds[jewels[gems[front]]]++;
            front++;
        }
        while(back < n && check(kinds))
        {
            kinds[jewels[gems[back]]]--;
            back++;
        }
        
        if(answer[1] - answer[0] > front - back)
            answer[1] = front, answer[0] = back;
    }
    return answer;
}

 

4번의 경우 구조체를 사용하여 말끔하게 작성하도록 하였습니다.

#include <bits/stdc++.h>
using info = std::pair<std::pair<int, int>, std::pair<int, int>>;
using namespace std;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int n = board.size();
    
    vector<vector<int>> visit(n, vector<int>(n));
    priority_queue<info, vector<info>, greater<info>> pq;
    visit[0][0] = 10, pq.push({{0, -1}, {0, 0}});
    while(!pq.empty())
    {
        int cost = pq.top().first.first;
        int dir = pq.top().first.second;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        
        visit[x][y] = visit[x][y] | (1 << dir);
        if(x == n - 1 && y == n - 1)
        {
            answer = cost;
            break;
        }
        
        for(int i = 0;i < 4;i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(!(visit[nx][ny] & (1 << i)) && !board[nx][ny])
            {
                int ncost = (dir == i || dir == -1 ? 100 : 600);
                pq.push({{cost + ncost, i}, {nx, ny}});
            }
        }
    }
    return answer;
}