https://programmers.co.kr/learn/courses/30/lessons/60062

 

코딩테스트 연습 - 외벽 점검

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하

programmers.co.kr

 

풀이

    처음 문제를 O(N)만에 풀 수 있는 방법을 생각해보았지만 뜻대로 되지 않고 자꾸 DFS를 이용하는 방법이 떠올라 DFS를 이용하지 않고 풀어보려했지만 결국 DFS를 사용하게 되었다. 이 문제가 까다로운 부분은 원형으로 연결되어 있다는 것이다. 1차원 배열의 맨 끝에서 오른쪽으로 한 번 더 이동하면 첫 번째 원소에 와야하는 것과 같은 예외처리를 해야한다. 문제는 다음과 같이 풀었다.

  1. DFS를 이용하여 임의의 취약지점에서 출발한다.
  2. 점검할 수 있는 취약지점까지 점검한다.
  3. 다음 취약지점부터 아직 점검하지 않은 친구가 점검할 수 있는 거리만큼 점검한다.
  4. 만약 점검한 취약지점 수와 전체 취약지점 수가 같은 경우 결과값을 최소값으로 갱신한다.

 

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int answer = 1e9; //정답 최대값으로 설정
int N;

vector<bool> dvisit; //점검을 완료한 친구 표시

void dfs(int ans, int now, int len, int total, vector<int> &weak, vector<int> &dist) {
    int start = weak[now]; //시작 취약지점
    int limit = weak[now] + dist[len]; //점검할 수 있는 거리의 마지노선
    int cnt = 0; //점검한 취약지점 수
    if(limit >= N) { //만약 범위를 벗어나 다시 0부터 시작하는 경우
        while(true) {
            if((weak[now] >= start) || (weak[now] <= (limit % N))) { //다음 탐색할 취약지점이 점검할 수 있는  범위에 있는 경우
                now++; //다음 취약지점으로 이동
                now %= weak.size(); //범위 벗어나지 않게 처리
                cnt++; //점검한 취약지점 수 증가
                if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
                    answer = min(answer,ans); //최소값 갱신
                    return; //리턴
                }
            }
            else { //범위를 벗어난 경우 점검 종료
                break;
            }
        }
    }
    else { //만약 범위를 벗어나지 않는 경우
        while(true) {
            if((weak[now] >= start) && (weak[now] <= limit)) { //다음 탐색할 취약지점이 점검할 수 있는 범위에 있는 경우
                now++; //다음 취약지점으로 이동
                now %= weak.size(); //범위 벗어나지 않게 처리
                cnt++; //점검한 취약지점 수 증가
                if(cnt + total == weak.size()) { //취약지점 모두 점검한 경우
                    answer = min(answer,ans); //최소값 갱신
                    return; //리턴
                }
            }
            else { //범위를 벗어난 경우 점검 종료
                break;
            }
        }
    }
    for(int d = 0; d < dist.size(); d++) { //점검할 다음 친구 선택
        if(dvisit[d]) continue; //이미 점검한 친구는 패스
        dvisit[d] = true; //방문표시
        dfs(ans+1 , now, d, total + cnt, weak, dist); //DFS를 이용하여 now부터 취약지점 점검
        dvisit[d] = false; //방문표시 취서
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {
    N = n; //외벽길이 전역변수로 저장
    dvisit.resize(dist.size()); //방문배열 크기 설정
    
    sort(dist.begin(), dist.end(), greater<int>()); //큰 것부터 정렬
    
    for(int w = 0; w < weak.size(); w++) { //점검을 시작할 취약지점 위치
        for(int d = 0; d < dist.size(); d++) { //점검할 친구 선택
            dvisit[d] = true;
            dfs(1, w, d, 0, weak, dist);
            dvisit[d] = false;
        }
    }
    if(answer == 1e9) return -1; //모두 탐색하지 못한 경우 -1 리턴
    else return answer; //그렇지 않은 경우 최소값 리턴
}

최대한 반복되는 비교를 하지 않도록 방문함수를 설정하고 점검한 취약지점을 다시 점검하도록 하지 않도록 다음 취약지점으로 이동하며 점검하도록 프로그램을 짜보았다. DFS함수의 인자가 많은 것이 아쉬운 부분이지만 다른 방법으로는 떠오르지 않아 함수의 인자 밖에 선택할 수 없었다. weak와 dist를 모두 전역변수로 하면 메모리 낭비와 복사하는 시간이 걸리므로 call by reference를 이용하여 그런 시간을 줄여보았다.

 

채점 결과

https://programmers.co.kr/learn/courses/30/lessons/60063

 

코딩테스트 연습 - 블록 이동하기

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7

programmers.co.kr

 

 

풀이

    이 문제는 DFS, BFS 모두 풀이가 가능한 문제이다. 글쓴이는 평소 DFS를 많이 이용했기 때문에 이번에는 BFS를 이용하여 풀어보았다. 로봇이 한 칸을 차지하는 것이 아닌 두 칸을 차지하므로 예외처리를 많이 해야하기 때문에 캐치하지 못한 부분이 있어 일부 테스트 케이스를 통과하지 못할 수도 있다. 나도 이 문제를 풀며 내가 생각하지 못한 부분을 예외처리하지 못하여 약간의 시간이 더 걸렸다. 로봇의 현재 위치에서 생각해야할 부분은 네 가지가 있다.

  1. 다음 위치가 보드를 벗어나는지
  2. 로봇이 차지하는 두 칸 중 하나도 1이 아닌지
  3. 이미 현재 위치를 거쳐갔는지
  4. 회전하는 경우 회전할 때 지나가는 칸이 1이 아닌지

위 네 가지만 예외처리하면 쉽게 풀 수 있는 문제이다. 예외처리만 하면 되는 문제이기 때문에 if, continue 등이 많이 쓰였다.

 

    문제를 풀 때 로봇이 상하좌우로 이동하는 경우, 회전하는 경우를 나누어서 풀었다. 상하좌우로 이동하는 경우는 일반 BFS처럼 풀면 되기 때문에 예외처리가 따로 할 부분이 없었다. 문제는 회전하는 경우였다. 회전하는 경우를 차지하는 두 칸 중에 한 칸이 대각선으로 이동하는 방식으로 생각했다. 그림으로 나타내면 다음과 같다.

위와 같이 이동한다고 할 때 실제로는 2, 4번으로 이동할 수 있지만 1, 3번으로는 이동하지 못한다. 이 부분을 예외처리하기 위해 두 칸의 x좌표나 y좌표 중 하나가 같은 경우에만 올바르게 회전했다고 판단했다. 이 과정을 다른 쪽 칸도 똑같이 진행하였다. 이렇게 회전하는 경우에 갈 수 있는 좌표의 위치를 계산할 수 있다.

 

소스 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct pos{ //x, y좌표를 가지는 구조체
    int x, y;
};

struct element { //큐에 넣을 구조체
    pair<pos,pos> position;
    int depth;
};

bool visit[101][101][101][101]; //방문배열

int dx[4] = {1, 0, 0, -1}; //dx, dy는 상하좌우로 이동
int dy[4] = {0, 1, -1, 0};
int rx[4] = {1, 1, -1, -1}; //rx, ry는 회전
int ry[4] = {1, -1, 1, -1};

int solution(vector<vector<int>> board) {
    int N = board.size();
    pair<pos,pos> robot = {{0, 0}, {0, 1}}; ///로봇의 현재 위치
    queue<element> q; //BFS에 사용될 큐
    
    q.push({robot, 0}); //현재 위치를 큐에 넣음
    visit[robot.first.x][robot.first.y][robot.second.x][robot.second.y] = true; //현재 위치 방문 표시
    visit[robot.second.x][robot.second.y][robot.first.x][robot.first.y] = true; //두 칸을 반대로 했을 때도 방문 표시
    
    while(!q.empty()) { //큐가 빌 때까지
        element e = q.front(); q.pop();
        pair<pos,pos> now = e.position; //현재 위치
        for(int d = 0; d < 4; d++) { //상하좌우 방향으로
            pair<pos,pos> nxt = {{now.first.x + dx[d], now.first.y + dy[d]}, {now.second.x + dx[d], now.second.y + dy[d]}}; //다음 좌표 위치
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //만약 두 칸 중에 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우도 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue; //로봇 왼쪽 오른쪽이 반대로 됐을 경우도 같음
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //도착한 경우 방문 횟수 리턴
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
        
        
        for(int r = 0; r < 4; r++) { //회전하는 경우
            pair<pos,pos> nxt = {{now.first.x + rx[r], now.first.y + ry[r]}, {now.second.x, now.second.y}}; //한 쪽 날개 회전 
            if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //만약 한쪽을 대각선으로 회전했을 때 로봇이 차지하는 두 칸이 나란히 있지 않은 경우 건너뛰기
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[now.first.x][now.first.y + ry[r]] || board[now.first.x + rx[r]][now.first.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
            
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴 
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
            
        for(int r = 0; r < 4; r++) { //다른 한 쪽이 회전하는 경우
            pair<pos,pos> nxt = {{now.first.x, now.first.y}, {now.second.x + rx[r], now.second.y + ry[r]}}; //다른 한 쪽 날개 회전
            if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //로봇이 차지하는 두 칸이 나란히 있지 않은 경우 리턴
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 리턴
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[now.second.x][now.second.y + ry[r]] || board[now.second.x + rx[r]][now.second.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue;//이미 방문한 경우 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
            
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
    }
}

같은 코드가 반복되어 비효율적인 부분이 있긴 하지만 프로그램 자체가 길지 않으므로 하나의 함수에 작성하였다.시간의 효율성을 생각해보면 큐 안의 반복문이 4번 반복하는 for문이 3개 있으므로 배열의 크기를 N이라고 할 때 약 N * N * 12번의 반복이 발생하지만 12번의 반복은 10^8이 약 1초 걸린다고 생각할 때 무시해도 될 정도의 아주 작은 시간이므로 그다지 효율성을 떨어뜨리지 않는다고 할 수 있다.

 

채점 결과

https://programmers.co.kr/learn/courses/30/lessons/72412

 

코딩테스트 연습 - 순위 검색

["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt

programmers.co.kr

이 문제는 스스로 시간초과 문제를 해결하지 못하여 풀이를 보고 해결할 수 있었다.

문제

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

  • 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
  • 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
  • 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
  • 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

  • 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
  • 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
  • backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
  • 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
  • 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
  • query의 각 문자열은 "[조건] X" 형식입니다.
    • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
    • 언어는 cpp, java, python, - 중 하나입니다.
    • 직군은 backend, frontend, - 중 하나입니다.
    • 경력은 junior, senior, - 중 하나입니다.
    • 소울푸드는 chicken, pizza, - 중 하나입니다.
    • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
    • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
    • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
    • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

조건이 주어지는 query를 만족하는 인원이 몇명인지를 vector에 담아 리턴하는 문제이다.

 

예시

위 그림과 같이 info로 각 사람들의 지원 조건이 주어지면 query를 만족하는 인원이 각각 몇명인지를 구하는 문제이다.

 

이 문제는 각각 인원을 모두 구하고 겹치는 인원들을 찾아내어 인원을 세면 시간초과가 걸린다. 따라서 각 조건을 만족하는 사람을 전부 가지고 유지하고 있어야한다. 따라서 info에 주어지는 언어, 직군, 경력, 음식을 하나로 생각해서 그 조건을 만족하는 사람들의 점수를 가지고 있어야한다. 글쓴이는 언어, 직군, 경력,음식을 각가 1차원으로 생각하여 4차원 배열을 만들었다. 코드는 다음과 같다.

 

소스코드

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

vector<int> database[3][2][2][2]; //데이터베이스 구축
//cpp = 0, java = 1, python = 2;
//backend = 0, frontend = 1;
//junior = 0, senior = 1;
//chicken = 0, pizza = 1;


vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    for(int i =0; i < info.size(); i++) {
        int lan, end, career, food;
        int now = 0;
        string s = info[i]; //문자열을 나눔
        if(s[0] == 'c') {
            lan = 0;
            now = 4;
        }
        else if(s[0] == 'j') {
            lan = 1;
            now = 5;
        }
        else{
            lan = 2;
            now = 7;
        }
        
        if(s[now] == 'b') {
            end = 0;
            now += 8;
        }
        else {
            end = 1;
            now += 9;
        }
        
        if(s[now] == 'j') {
            career = 0;
        }
        else {
            career = 1;
        }
        now += 7;
        
        if(s[now] == 'c') {
            food = 0;
            now += 8;
        }
        else {
            food = 1;
            now += 6;
        }
        
        int num = stoi(s.substr(now));
        database[lan][end][career][food].push_back(num); //해당하는 데이터베이스에 점수 추가
    }
    
  for(int i=0; i<3; i++)
    for(int j=0; j<2; j++)
      for(int k=0; k<2; k++)
        for(int l=0; l<2; l++)
          sort(database[i][j][k][l].begin(),database[i][j][k][l].end());
    
    for(string q : query) {
        int now = 0;
        int s1, s2, s3, s4, e1, e2, e3, e4;
        int lan = -1, end = -1, career = -1, food = -1;
        if(q[now] == 'c') { //언어 분류
            lan = 0;
            now += 8;
        }
        else if(q[now] == 'j') {
            lan = 1;
            now += 9;
        }
        else if(q[now] == 'p') {
            lan = 2;
            now += 11;
        }
        else {
            now += 6;
        }
        
        if(q[now] == 'b') {
            end = 0;
            now += 12;
        }
        else if(q[now] == 'f') {
            end = 1;
            now += 13;
        }
        else {
            now += 6;
        }
        
        if(q[now] == 'j') {
            career = 0;
            now += 11;
        }
        else if(q[now] == 's') {
            career = 1;
            now += 11;
        }
        else {
            now += 6;
        }
        
        if(q[now] == 'p') {
            food = 1;
            now += 6;
        }
        else if(q[now] == 'c') {
            food = 0;
            now += 8;
        }
        else {
            now += 2;
        }
        
        int num = stoi(q.substr(now));
        
        int people = 0;
        for(int i = 0; i <= 2; i++) {
            if(lan != i && lan != -1) continue;
            for(int j = 0; j <= 1; j++) {
                if(end != j && end != -1) continue;
                for(int k = 0; k <= 1; k++) {
                    if(career != -1 && career != k) continue;
                    for(int l = 0; l <= 1; l++) {
                        if(food != -1 && food != l) continue;
                        if(database[i][j][k][l].size()) {
                            auto lo = lower_bound(database[i][j][k][l].begin(), database[i][j][k][l].end(), num);
                            people += database[i][j][k][l].end() - lo;
                        }
                    }
                }
            }
        }
        answer.push_back(people);
    }
    
    return answer;
}

문자열을 분류하는 코드 때문에 상당히 복잡해보이지만 그 부분을 제외하면 간단한 코드이다. 각 조건에 따라서 언어, 직군, 경력, 음식에 해당하는 인덱스가 결정된다. 그 조건을 만족하는 벡터에 점수를 push한다. 그렇다면 같은 조건을 가진 사람들의 점수가 유지될 것이다. 그리고 조건이 되는 점수를 이분탐색하기 위하여 모두 정렬한다. 4중 for문이지만 3 * 2 * 2 * 2 = 24로 24번밖에 반복하지 않는다. 그 다음 query에서 주어지는 조건에 따라 탐색하고자 하는 인덱스를 결정한다. 모든 초기값을 -1로 주어 만약 -1인 경우 해당 조건의 모든 점수를 탐색할 수 있게 하였다. 위 코드를 보았을 때 

 if(lan != i && lan != -1) continue;

이 부분은 언어가 i번째 인덱스도 아니고 -1도 아닐 경우 건너 뛴다는 의미이다. 즉 -1인 경우 모든 인덱스를 탐색하고 그렇지 않은 경우 원하는 조건인 lan에 해당하는 인덱스만 탐색한다는 뜻이다. 그렇게 4가지 조건을 모두 탐색하여 lower_bound라는 이분탐색 알고리즘을 이용하여 조건을 만족하는 점수의 이터레이터를 얻는다. 그리고 end와의 차이를 이용해 조건으로 주어진 값보다 크거나 같은 값의 수를 구할 수 있다. 그렇게 구한 인원을 각 query마다 answer에 push_back하여 원하는 값을 구할 수 있다.

 

채점 결과

 

https://programmers.co.kr/learn/courses/30/lessons/42892

 

코딩테스트 연습 - 길 찾기 게임

[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

programmers.co.kr

문제 설명

이 문제는 좌표로 주어지는 노드들을 트리로 이진 트리로 만들어 전위 순회, 후위 순회 결과를 리턴하는 문제이다. 예시는 다음과 같다.

문제 예시

첫 번째 그림과 같이 주어진 좌표를 아래의 그림처럼 이진 트리 구조로 만드는 것이다. 트리를 구성하는 노드들의 규칙은 다음과 같다.

  1. 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
  2. 모든 노드는 서로 다른 x값을 가진다.
  3. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
  4. 자식 노드의 y 값은 항상 부모 노드보다 작다.
  5. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
  6. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

위 예시의 전위 순회와 후위 순회의 결과는 다음과 같이 나온다.

  • 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
  • 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

 

풀이

이 문제를 풀기 위해서 우선 트리를 구현해야한다. 연결리스트를 이용하여 구현하면 복잡해진다고 판단하여 배열을 이용하였다.

 

1. 트리의 표현

    pair<int,int>로 구성된 배열을 이용하여 first에는 왼쪽 자식, second에는 오른쪽 자식의 번호를 저장하였다. 트리를 사용하기 위해서는 트리를 초기화해야한다. 자식을 가리키는 인덱스 번호가 자기 자신과 같다면 리프노드로 판단하도록 초기화하였다.

 

2. 노드 순서

    입력으로 주어진 노드 정보들을 루트 노드부터 순서대로 정렬해야한다. 이때 주어진 배열의 (인덱스 번호 + 1)이 노드의 번호이기 때문에 주어진 배열 자체를 정렬시키면 안되고 인덱스 번호와 좌표를 유지해야한다. 따라서 각 노드의 번호를 통해 좌표를 쉽게 찾기 위해 map을 사용하였고 전위 순회 방식으로 노드를 정렬하기 위해 정렬을 위한 node라는 배열을 따로 선언하였다.

 

3. 트리 구현

    그 다음에는 정렬된 노드를 순서대로 트리에 붙여나가야한다. 트리를 만드는 find함수를 따로 구현하였다. find 함수는 다음과 같이 동작한다.

  1. 현재 노드의 x좌표보다  추가하는 노드의 x좌표가 작은 경우(왼쪽 자식인 경우)
    • 만약 왼쪽 자식이 자기 자신일 때(리프노드일 때) 왼쪽 자식에 붙인다.
    • 그렇지 않으면 재귀적으로 왼쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.
  2. 현재 노드의 x좌표보다 추가하는 노드의 x좌표가 큰 경우(오른쪽 자식인 경우)
    • 만약 오른쪽 자식이 자기 자신일 때(리프노드일 때) 오른쪽 자식에 붙인다.
    • 그렇지 않으면 재귀적으로 오른쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.

4. 전위 순회와 후위 순회

    전위 순회는 왼쪽 오른쪽 자식을 탐색하기 전에 자기 자신을 경로에 넣으면 된다. 반대로 후위 순회는 왼쪽 오른쪽 자식을 탐색하고 난 이후에 자기 자신을 경로에 넣으면 된다.

 

소스코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

pair<int,int> tree[10001];
map<int,pair<int,int>> m;

vector<int> frontpath; //전위순회 경로
vector<int> endpath; //후위순회 경로

struct edge { //정렬을 위한 구조체
    int idx, x, y;
};

bool cmp(edge a, edge b) { //루트노드부터 순서대로 정렬하는 비교함수
    if(a.y == b.y) {
        return a.x < b.x;
    }
    else
        return a.y > b.y;
}

void find(int now, edge e) { //적절한 위치 찾기
    pair<int,int> nowpos = m[now];
    if(nowpos.first > e.x) { //왼쪽자식인 경우
        if(tree[now].first == now) { //왼쪽 자식 끝인 경우
            tree[now].first = e.idx; //왼쪽 자식에 붙이기
            return;
        }
        else { //끝이 아닌 경우
            find(tree[now].first, e); //재귀적으로 탐색
        }
    }
    else { //오른쪽 자식인 경우
        if(tree[now].second == now) { //오른쪽 자식 끝인 경우
            tree[now].second = e.idx;
            return;
        }
        else {
            find(tree[now].second, e);
        }
    }
    return;
}

void front(int now) { //전위순회
    frontpath.push_back(now); //경로 먼저 추가
    if(tree[now].first != now) { //리프노드가 아니라면
        front(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) {//리프노드가 아니라면
        front(tree[now].second); //오른쪽 자식 탐색
    }
}

void end(int now) { //후위순회
    if(tree[now].first != now) { //리프노드가 아니라면
        end(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) { //리프노드가 아니라면
        end(tree[now].second); //오른쪽 자식 탐색
    }
    endpath.push_back(now); //경로 나중에 추가
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<edge> node; //정렬을 위한 배열
    
    for(int i = 1; i <= nodeinfo.size(); i++) { //트리 초기화
        tree[i].first = i; //왼쪽 자식을 자기 자신으로
        tree[i].second = i; //오른쪽 자식을 자기 자신으로
    }
    
    for(int i = 0;i < nodeinfo.size(); i++) { 
        node.push_back({i+1, nodeinfo[i][0], nodeinfo[i][1]}); //정렬을 위한 배열
        m[i+1] = {nodeinfo[i][0], nodeinfo[i][1]}; //각 노드 번호별 x, y좌표 map에 저장
    }
    sort(node.begin(), node.end(), cmp); //y좌표가 큰순, x좌표가 작은순으로 정렬
    
    int root = node[0].idx; //루트 인덱스 번호
    
    for(int i = 1; i < node.size(); i++) {
        edge now = node[i]; //현재 노드
        find(root, now); //자식으로 붙이기
    }
    
    front(root); //전위순회
    end(root); //후위순회
    
    
    answer.push_back(frontpath);
    answer.push_back(endpath);
    
    return answer;
}

 

결과

 

https://programmers.co.kr/learn/courses/30/lessons/72413

 

코딩테스트 연습 - 합승 택시 요금

6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

programmers.co.kr

이 문제는 딱 보자마자 플로이드-와샬 알고리즘으로 쉽게 풀 수 있는 문제임을 직감했다. 모든 정점에서 다른 모든 정점으로의 최단 경로를 구한 다음 시작정점으로부터 한 지점을 거쳐서 각각 A, B의 집을 가는 경로의 최솟값을 구하면 된다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MN = 201;
const int INF = 1e9; //무한대

int floyd[MN][MN]; //최단 경로를 저장할 배열

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    fill(&floyd[0][0], &floyd[n][n+1], INF); //최단 경로 무한대로 초기화
    for(int i = 1; i <= n; i++)
        floyd[i][i] = 0; //자기 자신은 0으로 초기화
    
    for(vector<int> e : fares) { //u->v와 v->u 모두 가능하므로 양방향으로 초기화
        floyd[e[0]][e[1]] = e[2];
        floyd[e[1]][e[0]] = e[2];
    }
    for(int k = 1; k <= n; k++) { //플로이드-와샬 알고리즘 수행 k정점을 통해 갔을 경우를 각각 계산
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
            }
        }
    }
    
    for(int k = 1; k <= n; k++) { //1번 정점부터 n번 정점까지 출발점부터 k를 지나 a, b로 각각 가는 합 계산
        int tmp = floyd[s][k] + floyd[k][a] + floyd[k][b];
        if(tmp < 0) continue; //오버플로우 방지
        answer = min(answer, tmp); //최솟값 갱신
    }
    
    return answer;
}

    초기화를 1e9인 10억으로 했기 때문에 만약 s->k, k->a, k->b 경로가 모두 없는 경우 30억으로 약 21억인 정수형 범위를 넘어가게 된다. 그렇기 때문에 오버플로우 방지로 계산한 결과 값이 0보다 큰 경우에만 최소값을 갱신해야한다. 그렇지 않으면 엄청나게 작은 수가 최소값으로 갱신될 것이다.

 

    플로이드-와샬 알고리즘을 수행하는 부분은 가운데에 있는 3중 반복문이다. k정점을 지나는 경우를 계속 최단 경로로 갱신하여 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 수 있다. 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 다익스트라나 벨만-포드 알고리즘은 O(n^2)의 알고리즘이 가능하지만 모든 정점에서의 최단 경로를 모두 구하는 플로이드-와샬 알고리즘은 O(n^3)의 알고리즘이 최선이다. 문제의 조건에 따라 다익스트라를 사용할지 플로이드-와샬 알고리즘을 사용할지 잘 판단해야한다.

+ Recent posts