영원 웹 개발과 일상

프로그래머스 2019 kakao 무지의 먹방 라이브 문제 해설

29 Sep 2020

#[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설

문제 요약

특별한 먹방을 하려는 무지. 회전테이블에 각각의 음식을 놓아두고 자신 앞의 음식을 1초 동안 섭취 한 다음 회전판에 의해 다음 음식을 1초동안 섭취하는 특이한…

  • 회전하는데 걸리는 시간은 없다고 본다.
  • 빈 그릇이 아닐 때 까지 회전한다.
  • k초 후에 어떤 음식이 앞에 놓여있는지 도출해내는 문제
  • 무지는 엄청난 대식가이기 때문에 최대 20만개의 그릇에 한 그릇당 최대 1억 초 동안 먹을 수 있는 괴물이다. (효율성을 체크 해야한다는 뜻)
  • 또한 무지는 매우 지루한 나날을 보내고 있기 때문에 최대 2 x 10^13 초에 해당 하는 시간동안 음식을 섭취할 수 있는 초능력을 가지고 있다.(효율성을 체크 하라는 뜻)

    자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

문제 풀이

정확성만 생각한다면 1초 지날 때마다 검사하는 시뮬레이션을 통해 답을 도출해 내면 된다. 효율성을 생각한다면 남아있는 음식의 접시와 회전수를 조사하여 O(nlgn) 시간에 도출해야한다.

소스코드 및 소스해석

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

  • 정렬을 통해 남은 음식의 시간이 가장 작은 수에 해당하는 회전을 진행한다고 가정합니다.
  • 남은 접시의 수와 남은 지나간 k 초의 상관관계를 계산하며 k 가 0이하가 되기 바로 전 회전까지 계산합니다. (0번째 인덱스에 해당하는 접시로 다시 돌아오기 까지의 회전)
  • 이제 정렬된 숫자와 상관없이 1초마다 계산해서 답을 도출 해내시면 됩니다.
  • 회전 할 때 공식 : k = k - (음식이 남아 있는 접시 수) * (“체크하지 않은 접시 중 가장 낮은 남은 시간을 가진 접시의 남은 시간” - “이때 까지 회전한 수를 뺀 값”)
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> food_times, long long k);

int main() {
    vector<int> input = { 3, 1, 2 };
    vector<int> input2 = { 4,2,3,6,7,1,5,8 };
    int k = 5; // answer 1
    int k2 = 16; // answer 3
    int answer = solution(input, k);
}

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    vector<int> sortedTime = food_times;
    sort(sortedTime.begin(), sortedTime.end());
    sortedTime.push_back(0);

    long long foodNum = food_times.size();
    long long rotateNum = 0;

    for (int i = 0; i < sortedTime.size(); i++) {
        int ateFoodNum = 1;
        while (sortedTime[i] == sortedTime[i + 1]) {
            i++;
            ateFoodNum++;
        }
        if (k - (foodNum * (sortedTime[i] - rotateNum)) <= 0) {
            break;
        }
        k = k - (foodNum * (sortedTime[i] - rotateNum));
        foodNum -= ateFoodNum;
        rotateNum = sortedTime[i];
    }
    if (foodNum <= 0) return -1;
    while (k - foodNum > 0) {
        k = k - foodNum;
        rotateNum++;
    }

    for (size_t i = 0; i < food_times.size(); i++)
    {
        if (food_times[i] > rotateNum)
            k--;
        else
            continue;
        if (k == 0) {
            for (size_t j = 1; j <= food_times.size(); j++)
            {
                if ((i + j) % food_times.size() == 0) rotateNum++;
                if (food_times[(i + j) % food_times.size()] > rotateNum)
                    return (i + j) % food_times.size() + 1;
            }
        }
    }
    return -1;
}

문제 후기

문제 자체는 어렵지 않으나 구현 할 때 숫자 하나 차이로 풀리지 않을 수도 있기 때문에 주의를 요한다.

무지는 정말 대식가이다 지구에 있는 모든 음식을 다 먹을 수 있겠다.

프로그래머스 2019 kakao 길 찾기 게임 문제 해설

29 Sep 2020

#[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설

문제 요약

“전무”로 승진한 라이언이 왕따인 이유를 알려주는 문제. “전무” 라이언이 x, y 좌표값을 주면 우리 친구들이 x, y 를 전부 순회를 마친 팀이 이기는 “라이언만” 재미있는 게임이다.

  • x, y 좌표는 사실상 트리의 구성요소라고 생각하면 된다.
  • 이진트리의 모양을 가졌으며 x 값이 node 의 data, y가 node 의 레벨 이라 생각한다.

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

문제 풀이

x, y 좌표를 가지고 트리를 만들어 순회시키면 끝나는 문제. 모든 요소들은 이진트리를 만족하기 위한 조건을 가지고 있으므로 맘 놓고 트리를 만들면 된다.

소스코드 및 소스해석

리스트로 짜도 되지만 귀찮기 때문에 vector를 이용하여 트리의 정보를 저장한다. x, y, left, right, 들어올 때 index 를 저장하는 Node 구조체를 생성하고, 트리를 잘 만들어 주면 된다. 트리를 만들기 힘들다고 느껴지면 노트장 펴고 펜으로 먼저 순서를 적어가며 하는 것을 추천함.

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

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

struct Node {
    int x, y;
    int left, right;
    int myindex;
};

vector<vector<int>> solution(vector<vector<int>> nodeinfo);
void myInsert(int nodeIndex, vector<int> insertNode);
void preorder(vector<int> &vec, Node node);
void postorder(vector<int>& vec, Node node);
bool comp(vector<int> a, vector<int> b) {
    if (a[1] == b[1]) return a[0] < b[0];
    return a[1] > b[1];
}
vector<Node> tree; // x,y,left,right 를 저장하는 노드를 가진 트리
vector<vector<int>> levelInfo;
int treeIndex;
int main() {
    vector<vector<int>> nodeinfo = { {5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2} };
    solution(nodeinfo);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    for (size_t i = 0; i < nodeinfo.size(); i++)
        nodeinfo[i].push_back(i + 1);
    sort(nodeinfo.begin(), nodeinfo.end(), comp);
    tree.push_back(Node{nodeinfo[0][0], nodeinfo[0][1], -1, -1, nodeinfo[0][2]});

    for (size_t i = 1; i < nodeinfo.size(); i++)
        myInsert(0, nodeinfo[i]);


    //순회
    vector<int> preVec,postVec;
    preorder(preVec, tree[0]);
    postorder(postVec, tree[0]);
    answer.push_back(preVec);
    answer.push_back(postVec);

    return answer;
}
void myInsert(int nodeIndex, vector<int> insertNode){

    //x 값을 기준으로 왼쪽 오른쪽 체크한다
    if (tree[nodeIndex].x > insertNode[0]) {
        if (tree[nodeIndex].left == -1) {
            tree.push_back(Node{insertNode[0], insertNode[1], -1, -1, insertNode[2] });
            tree[nodeIndex].left = tree.size() - 1;
        }
        else {
            myInsert(tree[nodeIndex].left, insertNode);
        }
    }
    else {
        if (tree[nodeIndex].right == -1) {
            tree.push_back(Node{insertNode[0], insertNode[1], -1, -1,insertNode[2] });
            tree[nodeIndex].right = tree.size() - 1;
        }
        else {
            myInsert(tree[nodeIndex].right, insertNode);
        }
    }
}
void preorder(vector<int> &vec, Node node) {
    vec.push_back(node.myindex);
    if(node.left != -1)
        preorder(vec,tree[node.left]);
    if (node.right != -1)
        preorder(vec, tree[node.right]);
}
void postorder(vector<int>& vec, Node node) {
    if (node.left != -1)
        postorder(vec, tree[node.left]);
    if (node.right != -1)
        postorder(vec, tree[node.right]);
    vec.push_back(node.myindex);
}

문제 후기

문제의 난이도에 비해 정답률이 낮은 것이 좀 의아하다.

내 친구가 라이언 같은 놈이라면 절교한다.

프로그래머스 2019 kakao 블록게임 해설

29 Sep 2020

#[프로그래머스][2019 kakao] 블록게임 해설

문제 요약

피지컬을 극복하려는 프로도의 피빠진 노력

게임의 규칙은 간단하다.

  • 위에서 검은색 블록을 떨어뜨린다.
  • 검은블록을 포함하여 특정 블록이 직사각형의 형태가 되면 그 블록을 지울 수 있다.
  • 특정 블록은 무조건 한 개체여야하며 다른 개체와 섞여서는 안된다.

자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기

문제 풀이

테스트 케이스가 많지는 않기 때문에 검은블록을 0, 0 에서부터 n, n까지 다 떨어뜨려 본다.

소스코드 및 소스해석

프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.

  • 풀이방법은 12가지의 블록 유형중 삭제될 수 있는지 판단하는 것과 일단 떨어뜨려 보는 것이 있다. (그 외에도 있을 듯) 나는 후자를 택했다.
  • 블록을 감싼 직사각형의 Left Top 좌표와 Right Bottom 좌표를 획득하여 해당 하는 좌표 내에서 검은블록이 떨어지면 삭제될 수 있는지 판단한다.
  • 위에서부터 차곡차곡 검사한다.
#include <string>
#include <vector>
using namespace std;

struct Point {
    int x, y;
};
struct BlockInfo {
    Point lt, rb;
    vector<Point> pt; // x,y 반복체?
};

vector<int> getLTRB(BlockInfo block);
bool check(BlockInfo block, vector<vector<int>>& board);
int solution(vector<vector<int>> board);
void myRemove(BlockInfo block, vector<vector<int>>& board);

vector<BlockInfo> myblock(250);

int main() {
    vector<vector<int>> board = { {0,0,0,0,0,0,0,0,0,0} ,{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,4,0,0,0},{0,0,0,0,0,4,4,0,0,0},{0,0,0,0,3,0,4,0,0,0},{0,0,0,2,3,0,0,0,5,5},{1,2,2,2,3,3,0,0,0,5},{1,1,1,0,0,0,0,0,0,5} };
    int answer = solution(board);
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board.size(); j++) {
            if (board[i][j] == 0) continue;
            myblock[board[i][j]].pt.push_back(Point{ j, i });
            if (myblock[board[i][j]].pt.size() == 4) {
                vector<int> LTRB = getLTRB(myblock[board[i][j]]);
                myblock[board[i][j]].lt = { LTRB[0], LTRB[1] };
                myblock[board[i][j]].rb = { LTRB[2], LTRB[3] };
            }
        }
    }
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board.size(); j++) {
            if (board[i][j] != 0) {
                bool isPossible = check(myblock[board[i][j]], board);
                if (isPossible == true) {
                    answer++;
                    myRemove(myblock[board[i][j]], board);
                }
            }
        }
    }
    return answer;
}

vector<int> getLTRB(BlockInfo block) {
    vector<int> LTRB = { 2147483647, 2147483647, -1,-1 };
    for (int i = 0; i < block.pt.size(); i++)
    {
        if (block.pt[i].x < LTRB[0]) LTRB[0] = block.pt[i].x;
        if (block.pt[i].x > LTRB[2]) LTRB[2] = block.pt[i].x;
        if (block.pt[i].y < LTRB[1]) LTRB[1] = block.pt[i].y;
        if (block.pt[i].y > LTRB[3]) LTRB[3] = block.pt[i].y;
    }
    return LTRB;
}
bool check(BlockInfo block, vector<vector<int>> &board) {
    for (int i = block.lt.y; i <= block.rb.y; i++)
    {
        for (int j = block.lt.x; j <= block.rb.x; j++)
        {
            if (board[i][j] == 0) {
                for (int k = 0; k <= i; k++)
                {
                    if (board[k][j] != 0)
                        return false;
                }
            }
            else if (board[i][j] != board[block.pt[0].y][block.pt[0].x]) {
                return false;
            }
        }
    }
    return true;
}
void myRemove(BlockInfo block, vector<vector<int>>& board) {
    for (int i = block.lt.y; i <= block.rb.y; i++)
        for (int j = block.lt.x; j <= block.rb.x; j++)
            board[i][j] = 0;
}

문제 후기

직사각형이라고 하길래

0 0 0 2
0 1 2 2 1 1 1 2

이런식으로 나오면 두개 다 삭제해야하는 줄 알고 처음에 코드를 짯다가 낭패 맞았다. 문제가 애매하면 답이나 질문들을 먼저 참고하자.