2020 카카오 인턴십 문제 ①

 

 

2020 카카오 인턴십 문제

 

 

 

 

#1 키패드 누르기

조건을 헷갈리지 않고 구현하면 됨

각 숫자의 위치를 저장해두고 문자열을 구했다.

 

/* 1 2 3  1,4,7 => L  n=0일 때 주의
   4 5 6  3,6,9 => R
   7 8 9  else => rdist,ldist 계산, hand 고려 
   * 0 # */
string solution(vector<int> numbers, string hand) {
    string answer = "";
    int pos[12][2];
    pos[0][0]=3, pos[0][1]=1;
    pos[10][0]=3, pos[10][1]=0;
    pos[11][0]=3, pos[11][1]=2;
    int num=1;
    for(int r=0;r<3;++r){
        for(int c=0;c<3;++c,++num) pos[num][0]=r, pos[num][1]=c;
    }
    
    int rdx=11, ldx=10;
    //printf("   l=%2d  r=%2d \n",ldx,rdx);
    for(int n:numbers){
        if(n%3==1) answer+='L', ldx=n;
        else if(n && !(n%3)) answer+='R', rdx=n;
        else{
            int rdist=abs(pos[rdx][0]-pos[n][0])+abs(pos[rdx][1]-pos[n][1]);
            int ldist=abs(pos[ldx][0]-pos[n][0])+abs(pos[ldx][1]-pos[n][1]);
            if(rdist<ldist) answer+='R', rdx=n;
            else if(rdist>ldist) answer+='L', ldx=n;
            else{
                if(hand=="right") answer+='R', rdx=n;
                else answer+='L', ldx=n;
            }
        }
    }
    
    return answer;
}

 

 

 

 

#2 수식 최대화

연산자별 우선순위 정해서 스택으로 계산 잘 하면 된다

헷갈리지 않고 잘 하는 게 중요한 듯. 백준 괄호추가하기 문제들보다 좀 더 상위 버전인 듯

디버깅 안 되는 환경에서 풀기 너무 어렵다,,,,, ㅜㅜㅜㅜㅜㅜ오열

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

struct node {
    int op;
    long long num;
};
stack<node> S;
vector<node> v; // 0+ 1- 2*
int ord[6][4]={{1,2,3,4},{1,3,2,4},{2,1,3,4},{2,3,1,4},{3,1,2,4},{3,2,1,4}};

long long solution(string expression) {
    long long answer = 0;
    
    long long n=0;
    v.push_back({3,0});
    for(char e:expression){
        if('0'<=e && e<='9') n*=10, n+=(e-'0');
        else {
            v.back().num=n, n=0;
            if(e=='+') v.push_back({0,0});
            else if(e=='-') v.push_back({1,0});
            else v.push_back({2,0});
        }
    }
    v.back().num=n;
    v.push_back({3,0});
    
    for (int o = 0; o < 6; ++o) {
        //ord[o]={현재 +,-,* 우선순위}  1>2>3

        //printf("+:%d -:%d *:%d\n", ord[o][0], ord[o][1], ord[o][2]);
        for (int i = 0; i < v.size() - 1; ++i) {
            S.push(v[i]);

            while (ord[o][S.top().op] <= ord[o][v[i + 1].op]) {
                if (S.top().op == 3 && v[i + 1].op == 3) break;

                node cur = S.top(); S.pop();
                //printf("top:%d,%lld   cur:%d,%lld => ", S.top().op, S.top().num, cur.op, cur.num);
                if (cur.op == 0) S.top().num += cur.num;
                else if (cur.op == 1) S.top().num -= cur.num;
                else S.top().num *= cur.num;
                //printf("top:%d,%lld\n", S.top().op, S.top().num);
            }
        }
        long long tmp = S.top().num; S.pop();

        if (tmp < 0) answer = (answer > -tmp) ? answer : -tmp;
        else answer = (answer > tmp) ? answer : tmp;
    }
    
    return answer;
}

 

 

 

 

#3 경주로 건설

처음엔 단순 dp로 생각해서 어떤 순서로 dp배열을 채워야 하나 고민함

보드, 좌표 범위, cost, 방향 모두 고려하는 전형적인 다익스트라였다. PQ+DP 사용

 

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

struct node{
    int r, c, dir, cost;
};
struct pqsort{
    bool operator()(node A, node B) {
        return A.cost>B.cost;
    }
};
priority_queue<node,vector<node>,pqsort> pq;

int dp[25][25][4];      // [r][c][dir] 
int dy[4]={1,0,-1,0};   // 0↓ 1→ 2↑ 3←
int dx[4]={0,1,0,-1};
int build[3][2]={{0,1},{1,6},{-1,6}};

int solution(vector<vector<int>> board) {
    int answer = 0;
    int N=board.size();
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            for(int k=0;k<4;++k) dp[i][j][k]=987654321;
        }
    }
    
    dp[0][0][0]=dp[0][0][1]=0;
    if(!board[0][1]) pq.push({0,1,1,1}), dp[0][1][1]=1;
    if(!board[1][0]) pq.push({1,0,0,1}), dp[1][0][0]=1;
    while(!pq.empty()){
        int r=pq.top().r, d=pq.top().dir;
        int c=pq.top().c, cost=pq.top().cost; pq.pop();
        if(cost<dp[r][c][d]) continue;
        
        //printf("[%d][%d][%d]=%d -> ",r,c,d,cost);
        for(int b=0;b<3;++b){
            int nd=d+build[b][0];
            if(nd<0) nd+=4;
            else if(nd>3) nd-=4;
            
            int nr=r+dy[nd], nc=c+dx[nd];
            if(nr<0 || nr==N || nc<0 || nc==N) continue;
            if(board[nr][nc]) continue;
            
            int ncost=cost+build[b][1];
            if(dp[nr][nc][nd]>ncost){
                //printf("[%d][%d][%d]=%d ",nr,nc,nd,ncost);
                dp[nr][nc][nd]=ncost;
                if(nr==N-1 && nc==N-1) continue;
                pq.push({nr,nc,nd,ncost});    
            }
        }
        printf("\n");
    }
    answer=987654321;
    for(int k=0;k<4;++k) if(answer>dp[N-1][N-1][k]) answer=dp[N-1][N-1][k];
    answer*=100;
    return answer;
}