[Programmers C++] Winter Coding(재시도)

윈터 코딩

 프로그래머스에서 주최하는 겨울 인턴 프로그램 코딩 테스트에 참가한 적이 있다. 알고리즘을 막 배우기 시작했던 단계였으며, C++은 아직 하지도 못했던 터라 Javascript로 참가했었다. 결과가 너무 처참해서 아직도 기억이 난다. 두 시간동안 세 문제를 풀어야 하는데, 두 번째와 세 번째 문제는 봐도 아무것도 모르겠어서 첫 번째 문제라도 풀어야겠다 싶어서 두 시간동안 그것만 풀었는데 그것마저 못 풀었다. 

 그 이후로 '이래서는 안되겠다' 싶어서 BOJ도 열심히 풀고, C++ 공부도 하고, 알고리즘과는 관련없지만 정보처리기사 준비를 위해 운영 체계 공부도 하며 겨울 방학을 알차게 보냈다. 방학이 끝나가는 지금 겨울 방학 동안 한 것의 성과를 확인하기 위해 겨울 인턴 프로그래밍 코딩 테스트 문제를 다시 풀어봤다. 만약 공부를 해서 조금이라도 나아졌으면 몇 개는 맞출 것이고, 그렇지 않고 허송세월 한 것이라면 그대로일 것이라는 생각이 들어서다. 테스트를 시작하기 전 목표는 세 문제 중 두 문제를 맞추는 것이었는데, 그 목표치에는 아쉽게도 도달하지 못했다.

첫 번째 문제 : 스킬 트리 ( 30분 소요)

예전에 풀 때는 정규식으로 풀려고 했던 것으로 기억한다. 왜 그랬었는지 모르겠다. 

알파벳의 길이만한 chk라는 배열을 만들어 어떤 스킬이 어떤 스킬을 선행하는지 표시할 수 있게끔 했다. 만약 skill이 "CBD"라면 [0, 2, 1, 3, 0, 0, 0, 0, ...]과 같이 된다. 이 때 0을 제외한 숫자들은 값이 작을수록 선행해야 하는 스킬이 된다. 그러므로 C는 B 스킬의 선행 스킬이며, B는 D의 선행 스킬이다.

다음은 skill tree를 본다. 만약 "BACDE"라면 chk 배열에서 값을 가져오면 [2, 1, 3, 0, 0]이 된다. 0이 아닌 값들은 1, 2, 3의 순서로 등장해야 스킬트리를 올바르게 따른 것이 되며, 그렇지 않으면 선행 스킬을 무시한 것이 된다.

올바르게 순서를 맞춘 것을 세면 답이 나온다.

#include <string>
#include <vector>
using namespace std;
int chk[26];
int solution(string skill, vector<string> skill_trees) {
    int answer = 0, cnt = 1;
    for (int i = 0; i < skill.size(); i++) {
        chk[skill[i] - 'A'] = cnt++;
    }
    for (int i = 0; i < skill_trees.size(); i++) {
        cnt = 1;
        bool rightSkillTree = true;
        for (int j = 0; j < skill_trees[i].size(); j++) {
            int tmp = chk[skill_trees[i][j] - 'A'];
            if (tmp) {
                if (tmp != cnt) {
                    rightSkillTree = false;
                    break;
                } else {
                    cnt++;
                }
            }
        }
        if (rightSkillTree) answer++;
    }
    return answer;
}

두 번째 문제 : 방문 길이( 0분 소요)

첫 번째 문제를 풀고 이 문제를 봤을 때 풀이법이 바로 떠오르지 않아서 세 번째 문제를 먼저 시도했지만, 결국 두 번째 문제로 돌아오지 못했다. 아래는 테스트가 끝나고 따로 시간을 내서 푼 것이다. 

(0, 0)부터 시작해서 U, R, D, L이 주어졌을 때 방문했던 길을 중복없이 세는 문제다. 좌표 평면 상에 나타난 길을 중복없이 센다는 것이 떠오르지 않아 넘어갔었다. 나중에 떠오른 방법은 다음과 같다.

arr[11][11][4]를 bool 타입으로 선언한다. 첫 번째 11은 가능한 y좌표, 두 번째 11은 가능한 x좌표다. 마지막에 4는 y, x 좌표로부터 위, 오른쪽, 아래, 왼쪽을 간 적이 있는지 표시하는 것이다. 만약 시작점인 (5, 5)에서 U가 나왔다면 arr[5][5][0] = true;가 된다. 또한 이 길은 (6, 5)에서 D 방향으로 가는 길이기도 하므로 arr[6][5][2] = true;도 해준다. 이런 식으로 한 번 움직일 때 마다 두 개의 값을 수정해주고, 결과값을 반환할 때 2로 나누는 것이 필요하다. 이런 식으로 두 개의 값을 한번에 체크해주지 않으면 나중에 답보다 더 큰 값을 반환하게 될 수 있다.

#include <string>
#include <iostream>
using namespace std;
bool arr[11][11][4];
bool canGo(int y, int x) {
    return y <= 10 && x <= 10 && y >= 0 && x >= 0;
}
int solution(string dirs)
{
    int answer = 0, size = int(dirs.size()), x = 5, y = 5;
    for (int i = 0; i < size; i++) {
        if (dirs[i] == 'U') {
            if (canGo(y + 1, x)) {
                arr[y][x][0] = true;
                arr[++y][x][2] = true;
            }
        } else if (dirs[i] == 'R') {
            if (canGo(y, x + 1)) {
                arr[y][x][1] = true;
                arr[y][++x][3] = true;
            }
        } else if (dirs[i] == 'D') {
            if (canGo(y - 1, x)) {
                arr[y][x][2] = true;
                arr[--y][x][0] = true;
            }
        } else {
            if (canGo(y, x - 1)) {
                arr[y][x][3] = true;
                arr[y][--x][1] = true;
            }
        }
    }
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            for (int k = 0; k < 4; k++) {
                if (arr[i][j][k]) answer++;
            }
        }
    }
    return answer / 2;
}

세 번째 문제 : 쿠키 구입 ( 1시간 30분 소요 )

이렇게 오래 걸릴 줄 몰랐다... 정신없이 풀다 보니 1시간 30분이 지나 알람이 울렸다. 푸는 방법을 잘 몰랐던 문제였는데 그냥 패스하고 두 번째 문제를 푸는 것이 좋았을 뻔 했다.

인접하며 합이 동일한 두 부분합을 구하는 것이다. 부분합을 이루는 요소들도 서로 인접해야 한다. 완전 탐색으로 시도했으며 답은 맞았지만 효율성 테스트 부분에서 점수가 낮았는지 오답처리 됐다. 그도 그럴만한게 합이 동일한 두 분합을 구하는 부분의 시간 복잡도가 $O(N^3)$이었다. 다음에 부분합을 구하는 방법을 공부하고 다시 풀어봐야겠다.