200913 라인 코딩 테스트 후기

코딩 테스트

• 3시간에 6문제. 앞 4문제는 쉬웠고, 뒤 2문제는 조금 어려웠다.
• 역시나 시뮬레이션 및 구현을 좋아한다. 여기에다가 dfs, bfs, dp 등을 섞는 것을 좋아한다.
• 프로그래머스 채점 결과에 성공/실패 여부가 뜨는 게 없어서 내 코드가 맞는 지 틀린 지 잘 모르겠다. 사실 그냥 제출했다.

총평

• 라인에 입사하기 위해 라인 기출을 잘 보자

카카오 코딩테스트 후기

코딩테스트 링크

coding test

• 300분에 서버 이상으로 인한 30분 추가. 무려 5시간 30분동안 7문제를 푸는 코테였다.
  • 알고리즘이 아니라 사실상 지구력 싸움.
• 과거의 카카오 코딩테스트 문제들은 모두 프로그래머스에서 만나볼 수 있는데, 이게 많이 도움이 되었다. 기업마다 코테 스타일이 다르므로 카카오에 입사하고 싶다면 프로그래머스에서 카카오 코테 문제들을 풀어보면 좋을 것 같다.
• 시뮬레이션을 상당히 좋아한다. 예전 카카오 코테도 그러했다.
• 인터넷 커뮤니티에서 4솔 이상이면 합격이라는데, 글쎄.

총평

• 카카오는 과거 기출을 꼭 풀어보자

프로그래머스 42889 - 실패율

문제 링크

생각 및 접근

• struct를 다루는 것이 관건이 된 문제다.
• 문제 해결의 구조
  • 우선, 아래 struct Stage를 N개 담고 있는 vector를 만든다. (v)
  • 문제에서 주어진 stages를 순회한다.
    • 만약 stages[i] > N (즉, 이 유저가 고인물이라면)
      • 이 유저는 1부터 N까지의 모든 스테이지를 통과한 것이 된다. 따라서, Stage의 idx 1 ~ N 까지의 성공 유저 수를 하나씩 늘린다.
    • 만약 stages[i] <= N (즉, 이 유저가 뉴비라면)
      • 이 유저는 1부터 stages[i] - 1까지 통과한 것이고, stages[i]를 실패한 상태
        • 따라서 Stage의 idx 1 ~ stages[i] - 1까지의 성공 유저 수를 하나씩 늘리고,
        • Stage의 idx stages[i]의 실패 유저 수를 하나씩 늘린다.
  • 순회가 끝나면, 실패율을 계산해서 실패율 내림차순 -> 스테이지 단계 오름차순 순으로 정렬한다.
  • 정렬이 끝난 v의 각 Stage의 단계 번호를 answer에 담아 반환한다.
• struct Stage
  • int idx : 각 단계의 번호를 의미
  • int s : success한 유저의 수
  • int f : fail한 유저의 수
  • float rate : 실패율
  • void setS() : s를 하나 늘려준다.
  • void setF() : f를 하나 늘려준다.
  • void calcRate() : 실패율을 계산해서 rate에 저장한다. 식은 rate = (float) f / (float) (s + f);인데, s + f가 0일 때 주의하자.
  • 나중에 정렬을 할건데, 제일 우선되는건 실패율 내림차순, 그 다음은 단계의 번호로 오름차순이 되겠다.

      bool operator < (const Stage & b) const {
          if(rate == b.rate){
              return idx < b.idx;
          }
          return rate > b.rate;
      }

코드

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

struct Stage{
    int idx;
    int s;
    int f;
    float rate;
    Stage(int i, int a, int b){
        idx = i; s = a; f = b; rate = 0;
    }
    void setS(){
        s++;
    }
    void setF(){
        f++;
    }
    void calcRate(){
        if(s + f == 0){
            rate = 0;
        }
        else{
            rate = (float) f / (float) (s + f);    
        }
    }
    bool operator < (const Stage & b) const {
        if(rate == b.rate){
            return idx < b.idx;
        }
        return rate > b.rate;
    }
};

vector<int> answer;
vector<Stage> v;

vector<int> solution(int N, vector<int> stages) {
    for(int i = 1; i <= N; i++)
        v.push_back(Stage(i, 0, 0));

    for(int i = 0; i < stages.size(); i++){
        if(stages[i] > N){
            for(int j = 0; j <= N - 1; j++)
                v[j].setS();
        }
        else {
            for(int j = 0; j <= stages[i] - 2; j++)
                v[j].setS();
            v[stages[i] - 1].setF();
        }
    }

    for(int i = 0; i < N; i++)  v[i].calcRate();
    sort(v.begin(), v.end());

    for(int i = 0; i < N; i++)  answer.push_back(v[i].idx);
    return answer;
}

채점 결과

프로그래머스 42888 - 오픈채팅방

문제 링크

생각 및 접근

• vector<pair<string, string>> logs;

  • 유저들이 나가거나, 들어오거나를 기록하는 logs
  • 앞의 string은 uid를, 뒤의 string은 Enter, 혹은 Leave를 저장할 예정

• map<string, string> m;

  • 유저들의 이름을 저장할 map 선언
  • 앞의 string은 uid를, 뒤의 string은 유저들의 닉네임을 저장.

• 주어진 vector<string> record를 분석한다.

  • action[0]에는 행동을 담았다. (Leave, Enter, Change)
  • action[1]에는 uid를 담았다.
  • action[2]에는 유저들의 닉네임을 담았다.
  • 만약 행동이 떠나거나, 들어오는 것이었다면 logs에 저장해두어야 한다.

      if(action[ACT] == "Enter" || action[ACT] == "Leave"){
          logs.push_back(make_pair(action[ID], action[ACT]));
      }

  • 만약 행동이 들어오거나, 이름을 바꾸는 행위라면, 닉네임이 바뀌었을 수 있기 때문에, m을 바꿔준다.

      if(action[ACT] == "Enter" || action[ACT] == "Change"){
          m[action[ID]] = action[NAME];
      }

• 최종적으로 answer의 형태로 변환하기 위해, 아래 코드와 같은 과정을 거친다.

    lSize = logs.size();
    for(int i = 0; i < lSize; i++){
        string temp = m[logs[i].first];
        if(logs[i].second == "Enter")
            temp.append("님이 들어왔습니다.");
        else
            temp.append("님이 나갔습니다.");
        answer.push_back(temp);
    }
  
    return answer;

코드

#include <bits/stdc++.h>
#define ACT 0
#define ID 1
#define NAME 2
using namespace std;

vector<string> answer;
vector<pair<string, string>> logs;
map<string, string> m;

vector<string> solution(vector<string> record) {
    int rSize = record.size();
    int lSize;
    for(int i = 0; i < rSize; i++){
        int k = 0;
        string action[3];
        for(int j = 0; record[i][j] != '\0'; j++){
            if(record[i][j] == ' ') k++;
            else    action[k].push_back(record[i][j]);
        }

        if(action[ACT] == "Enter" || action[ACT] == "Leave"){
            logs.push_back(make_pair(action[ID], action[ACT]));
        }

        if(action[ACT] == "Enter" || action[ACT] == "Change"){
            m[action[ID]] = action[NAME];
        }
    }

    lSize = logs.size();
    for(int i = 0; i < lSize; i++){
        string temp = m[logs[i].first];
        if(logs[i].second == "Enter")
            temp.append("님이 들어왔습니다.");
        else
            temp.append("님이 나갔습니다.");
        answer.push_back(temp);
    }

    return answer;
}

채점 결과

백준 3190 - 뱀

문제 링크

생각 및 접근

• 어릴 적에 했었던 뱀 게임이다.

• 주어지는 것은

  • n : 보드의 크기
  • k : 사과의 갯수
  • vector<pair<Loc, bool>> apple; : 사과의 좌표
  • l : 뱀의 회전 횟수
  • vector<pair<int, char>> Rotate; : 뱀의 회전 방향 및 시간
    이다.

• 수도 코드는 이렇다.

    int main() {
        // 문제의 입력을 받는다.
  
        while(-1){
            // 뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다.
            // 방향을 바꿔야 한다면, 방향을 바꿔준다
  
            // 다음 머리 위치에 벽이 있는지 확인한다.
            // 다음 머리 위치에 뱀의 몸통이 있는지 확인한다.
                // 위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;
  
            // 다음 머리 위치에 사과가 있는지 확인한다.
                // 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.
                // 사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.
  
            // 시간을 1 늘려준다.
        }
    }

• queue<pair<Loc, int>> snake;

  • 큐의 front는 뱀의 머리, 큐의 back은 뱀의 꼬리, 그 중간에 있는 요소들은 뱀의 몸통이라고 가정하였음.
  • Loc는 좌표를 구조체로 표현. (아래 코드 참조) in는 뱀 머리 방향을 표현.

문제의 입력을 받는다.

struct Loc{
    int x;
    int y;
    Loc(int a, int b) : x(a), y(b) {};
};

// Loc는 뱀의 머리/몸통/꼬리 위치, int는 뱀 머리 방향
queue<pair<Loc, int>> snake;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        cin >> x >> y;
        // 사과의 좌표 삽입. 두번째 bool은 이 사과를 먹었는 지 기억하는 변수다.
        apple.push_back(make_pair(Loc(y, x), false));
    }

    cin >> l;
    for(int i = 1; i <= l; i++){
        cin >> x >> c;
        // 방향을 바꿔야 할 때를 기억하는 벡터
        Rotate.push_back(make_pair(x, c));
    }

    snake.push(make_pair(Loc(1, 1), RIGHT));

뱀의 머리 위치와 방향을 토대로 다음 머리 위치를 찾는다. 방향을 바꿔야 한다면, 방향을 바꿔준다

const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;

int TURN(int dir, char to){
    if(to == 'L')       return (dir - 1 == -1) ? 3 : dir - 1;
    else if(to == 'D')  return (dir + 1 == 4) ? 0 : dir + 1;
}

x = snake.front().first.x;
y = snake.front().first.y;
dir = snake.front().second;
snake.pop();

// 다음 뱀의 머리 위치
int xx = x + dx[dir];
int yy = y + dy[dir];
int ddir = dir;

// 시간 때문에 뱀의 머리 방향을 바꿔야 한다면, 바꿔준다.
// Rotate는 시간 순서로 주어지기 때문에, idx를 선언하여 시간을 기억해 놓는다.
if(idx < l && Rotate[idx].first == t){
    ddir = TURN(dir, Rotate[idx].second);
    idx++;
}

다음 머리 위치에 벽이 있는지 확인한다.

if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;

다음 머리 위치에 뱀의 몸통이 있는지 확인한다.

• snake를 전부 순회해서 다음 머리 위치가 snake에 있는 Loc와 일치하는 지 확인한다.

  int tmp = snake.size();
  for(int i = 1; i <= tmp; i++){
    int tx = snake.front().first.x;
    int ty = snake.front().first.y;
    int tdir = snake.front().second;
    snake.pop();
  
    if(tx == xx && ty == yy){
        cout << t;
        exit(0);
    }
  
    snake.push(make_pair(Loc(tx, ty), tdir));
  }

위 두 가지 조건을 만족하면, 더이상 뱀이 앞으로 전진할 수 없다는 의미이므로 break;

다음 머리 위치에 사과가 있는지 확인한다. 사과가 있다면, 뱀을 다음 머리를 머리로 인정하고, 기존 머리를 몸통으로 인정한다.

• gotApple은 사과가 있는지 확인하는 변수. 뒤에 if문을 위해서 선언해 놓는다.

bool gotApple = false;
for(int i = 0; i < k; i++){
    // 사과를 먹지 않았고, 다음 머리에 사과가 존재한다면 => 사과를 먹은 것으로 처리해야함!
    if(!apple[i].second && apple[i].first.x == xx &&  apple[i].first.y == yy){
        // 이전 머리를 몸통으로 인정하기
        snake.push(make_pair(Loc(x, y), dir));
        int temp = snake.size();
        // 다음 머리를 머리로 인정하기
        // 여기서 뱀의 머리는 snake의 front와 일맥상통.
        snake.push(make_pair(Loc(xx, yy), ddir));
        if(temp != 0){
            for(int i = 1; i <= temp; i++){
                int tx = snake.front().first.x;
                int ty = snake.front().first.y;
                int tdir = snake.front().second;
                snake.pop();

                snake.push(make_pair(Loc(tx, ty), tdir));
            }
        }
        apple[i].second = true;
        gotApple = true;
        break;
    }
}

사과가 없다면, 뱀의 다음 머리를 머리로 인정하고, 맨 마지막 꼬리를 잘라낸다.

if(!gotApple){
    // 이전 머리를 몸통으로 인정하기
    snake.push(make_pair(Loc(x, y), dir));
    int temp = snake.size();
    // 다음 머리를 머리로 인정하기
    snake.push(make_pair(Loc(xx, yy), ddir));
    for(int i = 1; i <= temp; i++){
        int tx = snake.front().first.x;
        int ty = snake.front().first.y;
        int tdir = snake.front().second;
        snake.pop();

        // 꼬리 잘라내기
        if(i != 1)
            snake.push(make_pair(Loc(tx, ty), tdir));
    }
}

시간을 1 늘려준다.

t++;

코드

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

const int UP = 0;
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

struct Loc{
    int x;
    int y;
    Loc(int a, int b) : x(a), y(b) {};
};

char c;
int n, k, l, x, y, idx, t = 1, dir;
vector<pair<Loc, bool>> apple;
vector<pair<int, char>> Rotate;
queue<pair<Loc, int>> snake;

int TURN(int dir, char to){
    if(to == 'L')       return (dir - 1 == -1) ? 3 : dir - 1;
    else if(to == 'D')  return (dir + 1 == 4) ? 0 : dir + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        cin >> x >> y;
        apple.push_back(make_pair(Loc(y, x), false));
    }

    cin >> l;
    for(int i = 1; i <= l; i++){
        cin >> x >> c;
        Rotate.push_back(make_pair(x, c));
    }

    snake.push(make_pair(Loc(1, 1), RIGHT));
    while(-1){
        x = snake.front().first.x;
        y = snake.front().first.y;
        dir = snake.front().second;
        snake.pop();

        int xx = x + dx[dir];
        int yy = y + dy[dir];
        int ddir = dir;
        if(idx < l && Rotate[idx].first == t){
            ddir = TURN(dir, Rotate[idx].second);
            idx++;
        }

        if(!(xx >= 1 && xx <= n && yy >= 1 && yy <= n)) break;
        int tmp = snake.size();
        for(int i = 1; i <= tmp; i++){
            int tx = snake.front().first.x;
            int ty = snake.front().first.y;
            int tdir = snake.front().second;
            snake.pop();

            if(tx == xx && ty == yy){
                cout << t;
                exit(0);
            }

            snake.push(make_pair(Loc(tx, ty), tdir));
        }

        bool gotApple = false;
        for(int i = 0; i < k; i++){
            if(!apple[i].second && apple[i].first.x == xx &&  apple[i].first.y == yy){
                snake.push(make_pair(Loc(x, y), dir));
                int temp = snake.size();
                snake.push(make_pair(Loc(xx, yy), ddir));
                if(temp != 0){
                    for(int i = 1; i <= temp; i++){
                        int tx = snake.front().first.x;
                        int ty = snake.front().first.y;
                        int tdir = snake.front().second;
                        snake.pop();

                        snake.push(make_pair(Loc(tx, ty), tdir));
                    }
                }
                apple[i].second = true;
                gotApple = true;
                break;
            }
        }
        if(!gotApple){
            snake.push(make_pair(Loc(x, y), dir));
            int temp = snake.size();
            snake.push(make_pair(Loc(xx, yy), ddir));
            for(int i = 1; i <= temp; i++){
                int tx = snake.front().first.x;
                int ty = snake.front().first.y;
                int tdir = snake.front().second;
                snake.pop();

                if(i != 1)
                    snake.push(make_pair(Loc(tx, ty), tdir));
            }
        }
        t++;
    }

    cout << t;
}

채점 결과

백준 12100 - 2048 Easy

문제 링크

생각 및 접근

• 평소에 해본 2048 게임. 상하좌우 방향으로 최대 5번 까지만 시행한다고 한다. 5번까지 상하좌우를 고르는 과정을 DFS로 구현하였다.
• 우선 main 함수에서 2048 초기값을 받고, 그 배열을 기준으로 dfs 수행

DFS

• int depth : 상하좌우로 숫자를 몇 번 넘겼는지 확인하는 변수
  • depth == 5는 5번을 다 수행했다는 의미. 즉, dfs의 종료 조건이 된다.
  • 종료 조건에서 v를 탐색하여 가장 큰 값을 변수 answer에 기억해둔다.
• vector<vector<int>> v 와 solve(v, i)
  • solve(v, i)는 아래 solve 챕터에서 설명되어 있음
  • 간단하게, i는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 i 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 i 방향으로 이동을 마친 배열이다.

void dfs(vector<vector<int>> v, int depth){
    if(depth == 5){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                answer = max(answer, v[i][j]);
        return;
    }
    else {
        for(int i = 0; i < 4; i++)
            dfs(solve(v, i), depth + 1);
    }
}

vector<vector<int>> solve(vector<vector<int>> v, int dir)

• dir
  • 따로 상하좌우를 나타내는 상수를 선언하여, dir에 들어온 값에 따라 상/하/좌/우를 구분하여 solve를 수행한다.
    • 상하좌우 상수

        const int RIGHT = 0;
        const int LEFT = 1;
        const int UP = 2;
        const int DOWN = 3;

• solve
  • dir는 상하좌우 중 한 곳의 방향을 가리키고, v는 아직 dir 방향으로 수행하기 이전의 배열을 넣는다. solve의 반환 값은 dir 방향으로 이동을 마친 배열이다.
  • dir == LEFT일 경우만 설명하겠다. 나머지의 경우는 다 비슷하고, 인덱스만 조금 바뀐다.
• dir == LEFT일 경우
  • 왼쪽으로 모든 숫자를 미는 것을 고려한다.
  • i
    • 한 줄 씩 왼쪽으로 미니까, 가장 큰 for문인 i를 한 줄 씩 왼쪽으로 미는 용도 로 사용한다.
  • j
    • v[i][j]에 들어갈 수 있는 값을 찾는다. 즉, j의 자리에 들어올 숫자를 찾는다.
    • j는 자리를 위한 인덱스다.
  • k
    • v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
    • 말이 조금 어려운데, v[i][j]의 값과 v[i][k]의 값에 따라서 v[i][j]에 들어갈 값이 달라지기 때문이다. 일단 코드의 주석을 보면서 이해해보자.

if(dir == LEFT){
    // i : 모든 행을 검사해야 한다. (LEFT이기 때문에 행이지, UP이나 DOWN이라면 열을 검사해야 할 것이다.
    for(int i = 1; i <= n; i++){
        // j : v[i][j]에 들어갈 수 있는 값을 찾는다.
        for(int j = 1; j <= n; j++){
            // k : v[i][j]에 들어갈 수 있는 값의 후보를 찾는다.
            for(int k = j + 1; k <= n; k++){
                // 뒤의 값이 비어있는 경우에는 값의 후보가 될 수 없다.
                // 왜냐하면, 값이 있어야 v[i][j]에 합쳐지거나, 그 뒤에 놓아지거나 할 것이다.
                // 따라서 비어있는 경우에는 continue;
                if(v[i][k] == 0) continue;
                else {
                    // 값을 찾으려는 자리와 값의 후보의 값이 같다 == 하나의 숫자로 합쳐질 수 있다.
                    // 예를 들어, 2 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
                    if(v[i][k] == v[i][j]){
                        v[i][j] *= 2;
                        // 값의 후보는 v[i][j]에 합쳐졌으므로, 0으로 초기화
                        v[i][k] = 0;
                    }
                    // 값을 찾으려는 자리와 값의 후보의 값이 다르다 == 하나의 숫자로 합쳐질 수 없다. 얹어져야 한다.
                    else {
                        // 근데 v[i][j]가 비었다? == 값의 후보는 v[i][j]로 들어와야 한다.
                        // 예를 들어, 0 0 0 2 와 같은 경우, j == 0, k == 3 이 된 경우라고 생각하자.
                        if(v[i][j] == 0){
                            v[i][j] = v[i][k];
                            v[i][k] = 0;
                            // j를 빼는 이유
                            // 0 2 0 2 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
                            // 위의 코드 두 문장을 거친 이후, 2 0 0 2가 될 것이고, j-for 문이 끝나면서 j가 1이 되면, 앞의 2와 뒤의 2는 합쳐지지 못한다.
                            // j == 1, k == 3 이 되어서 그냥 2 2 0 0 이 될 것이다.
                            // 따라서, j를 한 번 빼줌으로써 이를 방지한다.
                            j--;
                        }   
                        // 근데 v[i][j]가 비어있지 않다? == 값의 후보는 v[i][j + 1]로 들어와야 한다.
                        else{
                            // v[i][j]와 v[i][k]가 바로 붙어있지 않다면?
                            // 그냥 뒤에 두고, v[i][k]를 비워준다.
                            if(j + 1 != k){
                                v[i][j + 1] = v[i][k];
                                v[i][k] = 0;
                            }
                            // v[i][j]와 v[i][k]가 바로 붙어있다면?
                            // 예를 들어, 2 4 0 0 와 같은 경우, j == 0, k == 1 이 된 경우라고 생각하자.
                            // 위 if문 코드를 수행하면 2 0 0 0 이 되어버린다.
                            // 이를 방지해주고자 위와 같은 if 문을 작성했다.
                        }
                    }
                    // 값을 처리했다면, break
                    break;
                }
            }
        }
    }
}

// RIGHT, UP, DOWN 생략

return v;

• dir == LEFT를 dir == RIGHT / UP / DOWN으로 전환할 때의 주의점
  • 왼쪽으로 모는 것과 오른쪽으로 모는 것은 for 문을 돌릴 때 숫자의 증가/감소의 차이가 존재한다.
  • 왼쪽으로 모는 것과 위쪽으로 모는 것은 for 문을 돌릴 때 행/열의 인덱스를 주의해야하는 차이가 존재한다.

코드

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

const int RIGHT = 0;
const int LEFT = 1;
const int UP = 2;
const int DOWN = 3;
int n, answer = -1;

vector<vector<int>> solve(vector<vector<int>> v, int dir){
    if(dir == RIGHT){
        for(int i = 1; i <= n; i++){
            for(int j = n; j >= 1; j--){
                for(int k = j - 1; k >= 1; k--){
                    if(v[i][k] == 0) continue;
                    else {
                        if(v[i][k] == v[i][j]){
                            v[i][j] *= 2;
                            v[i][k] = 0;
                        }
                        else {
                            if(v[i][j] == 0){
                                v[i][j] = v[i][k];
                                v[i][k] = 0;
                                j++;
                            }   
                            else{
                                if(j - 1 != k){
                                    v[i][j - 1] = v[i][k];
                                    v[i][k] = 0;
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }
    }
    if(dir == LEFT){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = j + 1; k <= n; k++){
                    if(v[i][k] == 0) continue;
                    else {
                        if(v[i][k] == v[i][j]){
                            v[i][j] *= 2;
                            v[i][k] = 0;
                        }
                        else {
                            if(v[i][j] == 0){
                                v[i][j] = v[i][k];
                                v[i][k] = 0;
                                j--;
                            }   
                            else{
                                if(j + 1 != k){
                                    v[i][j + 1] = v[i][k];
                                    v[i][k] = 0;
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }
    }
    if(dir == UP){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = j + 1; k <= n; k++){
                    if(v[k][i] == 0) continue;
                    else {
                        if(v[k][i] == v[j][i]){
                            v[j][i] *= 2;
                            v[k][i] = 0;
                        }
                        else {
                            if(v[j][i] == 0){
                                v[j][i] = v[k][i];
                                v[k][i] = 0;
                                j--;
                            }   
                            else{
                                if(j + 1 != k){
                                    v[j + 1][i] = v[k][i];
                                    v[k][i] = 0;
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }

    }
    if(dir == DOWN){
        for(int i = 1; i <= n; i++){
            for(int j = n; j >= 1; j--){
                for(int k = j - 1; k >= 1; k--){
                    if(v[k][i] == 0) continue;
                    else {
                        if(v[k][i] == v[j][i]){
                            v[j][i] *= 2;
                            v[k][i] = 0;
                        }
                        else {
                            if(v[j][i] == 0){
                                v[j][i] = v[k][i];
                                v[k][i] = 0;
                                j++;
                            }   
                            else{
                                if(j - 1 != k){
                                    v[j - 1][i] = v[k][i];
                                    v[k][i] = 0;
                                }
                            }
                        }
                        break;
                    }
                }
            }
        }
    }

    return v;
}

void dfs(vector<vector<int>> v, int depth){
    if(depth == 5){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                answer = max(answer, v[i][j]);
        return;
    }
    else {
        for(int i = 0; i < 4; i++)
            dfs(solve(v, i), depth + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n;
    vector< vector<int> > MAP(n + 1, vector<int>(n + 1, 0));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> MAP[i][j];

    dfs(MAP, 0);
    cout << answer;
}

채점 결과

백준 2573 - 빙산

문제 링크

생각 및 접근

• 문제를 요약하자면,

  • 1의 시간이 지날 때, 상하좌우 바다의 갯수만큼 얼음이 녹는다.
  • 빙하가 여러 개로 갈라지면, 그 때의 시간을 출력한다.
  • 빙하가 다 녹을 때까지 여러 개로 갈라지지 않으면, 0을 출력한다.

• 빙하가 녹는 과정을 bfs로, 빙하가 여러 개로 갈라졌는지 확인하는 과정은 dfs로 체크한다.

• 바다의 정보를 저장하는 sea[302][302], 높이 h, 너비 w

  • sea를 받을 때, 1 이상이면 빙하라는 이야기므로, queue< pair<int, int> > ice;에 좌표 정보를 넣어준다,

      for (int i = 1; i <= h; i++) {
          for (int j = 1; j <= w; j++) {
              cin >> sea[i][j];
              if (sea[i][j] >= 1)  ice.push(make_pair(j, i));
              }
      }

• bfs와 dfs를 수행한다.

   while (!ice.empty()) {
       int iceNum = ice.size();
       // 큐에 들어있는 빙하만큼만 큐 탐색
       while (iceNum--) {
           int cnt = 0;
           int x = ice.front().first;
           int y = ice.front().second;
           ice.pop();
  
           // 1의 시간이 지날 때 동시다발적으로 녹는다.
           // 만약 1의 시간이 지나면서, 바로 왼쪽 빙하가 다 녹아서 0이 되었다고 하면, 0이 되었다고 왼쪽 빙하때문에 내 빙하가 1이 더 줄어드는 것을 방지한다. 따라서 visit 배열을 선언해주어야 한다.
           visit[y][x] = 1;
  
           // 상하좌우 탐색해서 sea에서 0인 것만 cnt를 늘려준다.
           // cnt는 빙하가 녹을 양을 의미한다.
           for (int i = 0; i < 4; i++) {
               int xx = x + dx[i];
               int yy = y + dy[i];
  
               if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
                   cnt++;
               }
           }
  
           sea[y][x] = max(0, sea[y][x] - cnt);
  
           // 빙하가 아직 다 녹지 않았다면 push
           if (sea[y][x] > 0) {
               ice.push(make_pair(x, y));
           }
       }
       // 빙하가 몇 조각으로 나뉘었는지 찾기
       memset(visit, 0, sizeof(visit));
       int cnt = 0;
       for (int i = 1; i <= h; i++) {
           for (int j = 1; j <= w; j++) {
               if (visit[i][j] == 0 && sea[i][j] != 0) {
                   dfs(j, i);
                   cnt++;
               }
           }
       }
  
       // 조각으로 나뉘지 않고 다 녹았다.
       if (cnt == 0) {
           cout << 0;
           exit(0);
       }
       // 2조각 이상이다.
       else if (cnt != 1) {
           cout << answer;
           exit(0);
       }
  
       answer++;
       memset(visit, 0, sizeof(visit));
   }

   void dfs(int a, int b) {
       visit[b][a] = 1;
       for (int i = 0; i < 4; i++) {
           int aa = a + dx[i];
           int bb = b + dy[i];
           if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
               dfs(aa, bb);
           }
       }
   }

코드

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

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
int sea[302][302], visit[302][302], h, w, answer = 1;
queue< pair<int, int> > ice;

void dfs(int a, int b) {
    visit[b][a] = 1;
    for (int i = 0; i < 4; i++) {
        int aa = a + dx[i];
        int bb = b + dy[i];
        if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
            dfs(aa, bb);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> sea[i][j];
            if (sea[i][j] >= 1)  ice.push(make_pair(j, i));
        }
    }

    while (!ice.empty()) {
        int iceNum = ice.size();
        while (iceNum--) {
            int cnt = 0;
            int x = ice.front().first;
            int y = ice.front().second;
            ice.pop();

            visit[y][x] = 1;

            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];

                if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
                    cnt++;
                }
            }
            sea[y][x] = max(0, sea[y][x] - cnt);
            if (sea[y][x] > 0) {
                ice.push(make_pair(x, y));
            }
        }

        memset(visit, 0, sizeof(visit));
        int cnt = 0;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (visit[i][j] == 0 && sea[i][j] != 0) {
                    dfs(j, i);
                    cnt++;
                }
            }
        }

        if (cnt == 0) {
            cout << 0;
            exit(0);
        }
        else if (cnt != 1) {
            cout << answer;
            exit(0);
        }

        answer++;
        memset(visit, 0, sizeof(visit));
    }
}

채점 결과

200829 이베이코리아 코딩 테스트 후기

coding test

• 필자는 C++로 풀었다.
• 문제들이 대개 어려웠다. 백준 기준 골드 하위에서 상위 티어들 문제인 것 같다.
• 2시간에 1.5솔 / 5 했다.
• 시간 복잡도 때문에 여러 알고리즘 기법을 적용하느라 삽질 좀 했다. 문제를 보고 무작정 달라드는 것이 아니라, 어떻게 해야할 지 고민하는 시간이 필요할 것 같다.

총평

• 대기업은 괜히 대기업이 아니다. 기업의 이름에 걸맞는 벽을 넘어야 합격할 수 있다.
• 쉬운 문제만 풀면서 "나는 합격할거야" 라는 안일한 생각을 버리고 어려운 문제에 도전하겠다.