2020 KAKAO BLIND RECRUITMENT 풀이 모음

1번

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

코딩테스트 연습 - 문자열 압축

---

접근방법

1. 문자열을 탐색하면서 문자열에서 같은  문자가 나오는 지점의 숫자가 몇 번 나오는지 계산하면서 탐색을 진행합니다.

2. 같은 문자가 나오는 경우가 멈출 경우 숫자와 문자를 문자열에 더하고 정답에 값을 넣어줍니다.

3. 이때 사이즈가 1인 경우는 문제의 조건의 따라 예외처리를 진행해줍니다.

---

실수

1. 문자열 탐색을 진행한 뒤 다음 문자열을 검색해줘야 할 때 i = 0으로 cnt = 1로 초기화해야 했는데 해주지 못해서 디버깅을 진행했습니다. 좀 더 정확한 구현 능력이 필요해 보입니다.

---

정답 코드

#include<bits/stdc++.h>
using namespace std;
int solution(string s) {
    int answer = 987654321;
    int maxLength = s.size();
    int sLen = s.size();
    int inValue = 1; //몇 칸으로 나눌지를 결정하는 변수
    for(int i = 0; i < (sLen / 2) + 1; i++){ //문자열의 중첩되는 최대 경우는 절반이므로 절반만 탐색을 진행한다.
        vector<string> sArr;
        for(int j = 0; j < sLen; j += inValue){ //나눠준 문자열을 sArr에 넣어준다.
            sArr.push_back(s.substr(j, inValue));
        }
        int cnt = 1;
        string makeS;
        for(int i = 1; i < sArr.size(); i++){ //문자열이 같다면 갯수를 증가시켜주고 아니라면 갱신과정을 진행한다.
            if(sArr[0] == sArr[i]){
                cnt++;
            }
            else{
                //문제의 조건에 따른 예외처리
                if(cnt == 1)
                    makeS += sArr[0];
                else
                    makeS += to_string(cnt) + sArr[0];
                //탐색이 진행된 부분은 sArr에서 삭제를 진행한다.
                sArr.erase(sArr.begin(), sArr.begin() + i);
                i = 0, cnt = 1;
            }
        }
        if(cnt == 1)
            makeS += sArr[0];
        else
            makeS += to_string(cnt) + sArr[0];
        //문자열의 길이를 갱신해준다.
        answer = min(answer, (int)makeS.size());
        inValue++;
    }
    return answer;
}

//20220213 심심해서 다시 푼 문제
//아니 과거의 나가 더 잘풀었네;;

#include <bits/stdc++.h>

using namespace std;

int solution(string s) {
    int minSize = INT_MAX;

    if(s.size() == 1)
        return 1;
    
    int sSize = s.size();
    int searchSize = s.size() / 2;
    for (int i = 1; i <= searchSize; i++) {
        string jStr = "";
        int curCnt = 1;
        for(int j = 0; j < sSize; j+= i){ //시작부터 전체 탐색 위치
            if(j + i > s.size()) {
                jStr += s.substr(j);
                break;
            }
            string curStr = s.substr(j, i);
            string nextStr = s.substr(j + i , i);
            if(curStr == nextStr){
                curCnt++;
            }
            else{
                if(curCnt == 1){
                    jStr += curStr;
                }
                else{
                    jStr += to_string(curCnt) + curStr;
                    curCnt = 1;
                }
            }
        }
        if(minSize > jStr.size())
            minSize = jStr.size();
    }
    return minSize;
}

int main() {
    string tCase1 = "aabbaccc";
    string tCase2 = "ababcdcdababcdcd";
    string tCase3 = "abcabcdede";
    string tCase4 = "abcabcabcabcdededededede";
    string tCase5 = "xababcdcdababcdcd";

    cout << solution(tCase1) <<"\n";
    cout << solution(tCase2) << "\n";
    cout << solution(tCase3) <<"\n";
    cout << solution(tCase4) <<"\n";
    cout << solution(tCase5) <<"\n";

    return 0;
}

---

2번

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

코딩테스트 연습 - 괄호 변환

---

접근방법

문제의 조건을 그대로 따라 하면 되는 함수였습니다.

1. 주어진 문자열을 균일한 문자열 u, v로 나눕니다.

2. 올바른 문자열인지 아닌지 판단합니다.

 2-1. 올바른 문자열이 아닌 경우 v에 대한 재귀 함수를 진행하고 기존 u의 뒤에 더해줍니다.

 2-2. 올바른 문자열이라면 괄호를 붙여준 뒤 v에 대한 재귀 함수를 더해주고 u를 더해줍니다.

---

실수

1. u 뒤에 v를 붙여주는 경우와 v 뒤에 u를 붙쳐주는 경우를 헷갈려서 삽질 좀 했습니다..

---

정답 코드

#include<bits/stdc++.h>

#define sz(v) (int)(v).size()
using namespace std;

//올바른 문자열인지 검사하는 함수
bool isValid(string s) {
    stack<char> a, b;

    for (auto c : s) {
        a.push(c);
    }
    for (int i = 0; i < sz(a); i++) {
        if (a.top() == ')') {
            b.push(a.top());
        }
        else{
            if (b.empty())
                return false;
            //같은 경우
            else if (b.top() == ')'){
                b.pop();
            }
            //같지 않은 경우
            else
                return false;
        }
        a.pop();
    }
    return true;
}

string divide(string p) {
    //기저사례: 빈 문자열일 경우 재귀 종료
    if (p.empty())
        return "";

    string ret;
    int leftParen = 0, rightParen = 0;
    string str1, str2;
    //괄호의 종류에 맞게 개수를 측정한 뒤 두 종류의 개수를 측정하는 변수가 같으면 균일한 문자열 완성을 의미하고 반복문 종료
    for (int i = 0; i < p.size(); i++) {
        if (p[i] == '(')
            leftParen++;
        else
            rightParen++;
        str1 += p[i];
        if (leftParen == rightParen) {
            str2 = p.substr(i + 1);
            break;
        }
    }
    //올바른 문자열이라면 str2(문제에서 v)를 재귀한뒤 결과를 뒤에 붙쳐준다.
    if (isValid(str1)){
        ret += str1 + divide(str2);
    //올바른 문자열이 아니라면 맨 앞과 맨 뒤의 문자를 지워주고 괄호를 붙쳐준뒤 v에 대한 재귀와 u를 결합해준다.
    }else{
        str1.erase(str1.begin() + 0), str1.erase(str1.begin() + str1.size() - 1);

        for(auto &c : str1){
            if(c == ')')
                c = '(';
            else
                c = ')';
        }
        ret += '(' + divide(str2) + ')' + str1;
    }
    return ret;
};

string solution(string p) {
    string answer = "";
    answer = divide(p);
    return answer;
}

int main() {
    string p = "(()())()";
    cout << solution(p) <<"\n";

    string p1 = ")(";
    cout << solution(p1) <<"\n";

    string p2 = "()))((()";
    cout << solution(p2) <<"\n";
}

---

3번

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

코딩테스트 연습 - 자물쇠와 열쇠

---

접근방법

이런 구현량이 방대한 문제에서는 구조체 또는 클래스를 선언하고 함수 별로 큰 로직을 분리하면서 문제를 푸는 것이 확실히 더 쉬운 거 같습니다.

1. board의 중간에 자물쇠의 값을 넣어준다.

2. 시작 지점에서 열쇠를 돌리는 4가지의 모든 경우를 탐색합니다..(열쇠 값을 board에 더해서 확인)

그림으로 표현하면 이런 느낌입니다. 빨간색 영역이 열쇠이고 검은색 영역이 자물쇠 부분입니다. 이러한 탐색을 진행해주기 위해 배열을 최대 영역인 [21 * (2 + 1)[21 * (2 + 1)]로 선언해주었습니다.

아 트랙패트로 그리려니까 너무 힘드네요.. 

---

실수

1. 문제를 잘 읽어보면 자물쇠의 크기와 열쇠의 크기가 다르게 설정되어 있습니다. 하지만 부족한 국어능력으로 또다시 실수를 했습니다..

---

정답 코드

#include<bits/stdc++.h>

using namespace std;
const int MAX = 21 * (2 + 1);

using vi = vector<int>;
using vvi = vector<vi>;

struct play{
    int board[MAX][MAX];
    vvi key, lock;
    play(vvi key, vvi lock) : key(key), lock(lock), board{} {}

    //열쇠를 회전하는 함수
    void rotate(){
        vvi tmp = key;
        int N = key.size();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                key[i][j] = tmp[N - j - 1][i];
            }
        }
    }

    //자물쇠의 상태가 열쇠와 맞는지 확인하는 함수. 자물쇠의 모든값이 1이라면 그것은 자물쇠와 키가 맞는다는 의미
    bool check(){
        int lockSize = lock.size();
        int lockN = lock.size() - 1;
        for(int i = lockN; i < lockSize + lockN; i++){
            for(int j = lockN; j < lockSize + lockN; j++){
                if(board[i][j] != 1)
                    return false;
            }
        }
        return true;
    }

    bool simulation(){
        int N = lock.size();
        int NK = key.size();
        //board 배열의 중간에 자물쇠의 값들을 넣어준다.
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                board[i + N - 1][j + N - 1] = lock[i][j];
            }
        }
        // printBoard();

        //원본값 복사. 테스트 이후 마다 다시 원 상태로 만들어야 탐색이 가능하다.
        int oriBoard[MAX][MAX];
        memcpy(oriBoard, board, sizeof oriBoard);
        int totalN = lock.size() * 2 + 1;
        //열쇠를 회전하는 4가지의 모든 경우 중에
        for(int r = 0; r < 4; r++){
            rotate();
            
            //i, j에서 시작하는 상태
            for(int i = 0; i < totalN; i++){
                for(int j = 0; j < totalN; j++){
                    int keyY = 0;
                    //열쇠의 범위만큼 더해준다.
                    for(int l = i; l < i + NK; l++){
                        int keyX = 0;
                        for(int k = j; k < j + NK; k++){
                            board[l][k] += key[keyY][keyX];
                            keyX++;
                        }
                        keyY++;
                    }
                    if(check()){
                        return true;
                    }
                    //printBoard();
                    memcpy(board, oriBoard, sizeof(board));
                }
            }
        }
        return false;
    }
    void printBoard(){
        int totalN = lock.size() * 2 + 1;
        for(int i = 0; i < totalN ; i++){
            for(int j = 0; j < totalN; j++)
                cout << board[i][j]  << " ";
            cout << "\n";
        }
        cout <<"==============board===========" << "\n";
    }
};

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    play op(key, lock);
    answer = op.simulation();
    return answer;
}

int main(){
    vvi key = {{0,0,0}, {1,0,0}, {0,1,1}};
    vvi lock = {{1,1,1}, {1,1,0}, {1,0,1}};
    cout << solution(key, lock) <<"\n";
}

---

4번

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

코딩테스트 연습 - 기둥과 보 설치

---

접근방법

1. 기둥을 설치하는 경우와 보를 설치하는 경우의 분기점을 코드로 구현합니다.

2. 기둥과 보를 설치하거나 철거할 경우 문제의 기둥과 보의 규칙을 준수하는지 확인합니다.

---

실수

---

정답 코드

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
#define isExist(q) (building.find(test[q])) != building.end()

bool isValid(set<vector<int>> &building) {
    for (auto build : building) {
        int x = build[0], y = build[1], a = build[2];
        if (a == 0) {
            //현재 위치 밑에 기둥이 있는 경우, 현재 위치에 보가 있는 경우, 현재 위치의 x - 1좌표에 보가 있는 경우중 하나라도 만족하면 설치 조건에 만족한다.
            vvi test = {{x,     y - 1, 0},
                        {x,     y,     1},
                        {x - 1, y,     1}};
            if (y == 0 || isExist(0) || isExist(1) || isExist(2))
                continue;
            return false;
        } else {
            //현재 위치의 y좌표 밑에 기둥이 있는 경우, 현재 위치의 x좌표 + 1에 기둥이 있는 경우, 현재 위치의 x - 1 좌표에 보가 있는 경우, 현재 위치의 x + 1 위치에 보가 있는 경우 보의 조건을 만족한다.
            vvi test = {{x,     y - 1, 0},
                        {x + 1, y - 1, 0},
                        {x - 1, y,     1},
                        {x + 1, y,     1}};
            if (isExist(0) || isExist(1) || (isExist(2) && isExist(3)))
                continue;
            return false;
        }
    }
    return true;
}

struct play {
    int n;
    vvi buildFrame;
    set<vi> building;

    play(int n, vvi buildFrame) : n(n), buildFrame(buildFrame) {}

    vvi simulation() {
        vvi ret;
        for (auto list : buildFrame) {
            vi v = {list[0], list[1], list[2]};
            //삭제하는 경우
            if (list[3] == 0) {
                building.erase(v);
                if (!isValid(building))
                    building.insert(v);
            }
            //설치하는 경우
            else {
                building.insert(v);
                if (!isValid(building))
                    building.erase(v);
            }
        }

        for (auto v: building) {
            ret.push_back(v);
        }
        return ret;
    }
};

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    vector<vector<int>> answer;
    play op(n, build_frame);
    answer = op.simulation();
    return answer;
}

int main() {
    int n = 5;
    vvi build_frame = {{1, 0, 0, 1},
                       {1, 1, 1, 1},
                       {2, 1, 0, 1},
                       {2, 2, 1, 1},
                       {5, 0, 0, 1},
                       {5, 1, 0, 1},
                       {4, 2, 1, 1},
                       {3, 2, 1, 1}};
    vvi ret = solution(n, build_frame);

    for (auto v : ret) {
        for (auto i : v) {
            cout << i << " ";
        }
        cout << "\n";
    }
}

---

5번

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

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

---

 

접근방법

1. 순열을 통해 dist를 배치하는 모든 경우를 탐색한다.

2. 거리만큼 이동 후 종료지점의 값을 넘으면 다음 탐색을 진행한다.

---

실수

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = INT_MAX;

    //종료지점 설정으 위해 weak[i] + n 값을 더해준다. 이런 과정을 통해 탐색의 범위를 지정해줄수 있다.
    int wSize= weak.size();
    for(int i = 0; i < wSize; i++){
        weak.push_back(weak[i] + n);
    }
    //next_permutaion을 통한 순열을 사용하기 위한 정렬
    sort(dist.begin(), dist.end());

    do{
        for(int i = 0; i < wSize; i++){
            int start = weak[i];
            int end = weak[i + wSize - 1];
            for(int j = 0; j < dist.size(); j++){
                start += dist[j];
                //다음 지점이 종료지점을 넘었으면 갱신후 다음탐색 진행
                if(start >= end){
                    answer = min(answer, j + 1);
                    break;
                }
                //외벽을 넘는 가장 큰 지점을 탐색
                int next = upper_bound(weak.begin(), weak.end(), start) - weak.begin();
                start = weak[next];
            }
        }
    }while(next_permutation(dist.begin(), dist.end()));

    if(answer == INT_MAX)
        return -1;
    return answer;
}

int main(){
    int n = 12;
    vector<int> weak = {1, 5, 6, 10};
    vector<int> dist  {1, 2, 3, 4};
    cout << solution(n, weak, dist) <<"\n";
}

---

6번

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

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

---

접근방법

1. 로봇에 대한 구조체를 선언한다.(BFS 탐색 시 코드와 구현의 간결화를 위해)

2. 이동방향으로 가는 경우와 회전하는 경우를 구해준다.

3. 회전하는 경우는 해당 방향으로 이동이 가능하면 회전이 가능하다는 조건을 이용하여 구현해준다.

4. 탐색을 진행하다가 로봇이 n -1 위치에 도달을 하면 거리의 값을 반환하고 탐색을 종료한다.

---

실수

---

정답 코드

//블록이동하기 실패 코드
//#include<bits/stdc++.h>
//
//using namespace std;
//const int MAX = 101;
//int N;
//struct plane {
//    int x1, y1, x2, y2;
//};
//
//int moveX[] = {-1, 0, 1, 0};
//int moveY[] = {0, 1, 0, -1};
//
//
//bool visited[MAX][MAX][MAX][MAX];
//
//bool isValid(int x, int y) {
//    return (x >= 0 && x < N && y >= 0 && y < N);
//}
//
//void Rotate(vector<vector<int>> &board, int x1, int y1, int x2, int y2, queue<plane> &q) {
//    int taildir;
//    if (y1 == y2 && x1 > x2) {
//        taildir = 0;
//    } else if (y1 == y2 && x1 < x2) {
//        taildir = 2;
//    } else if (x1 == x2 && y1 > y2) {
//        taildir = 3;
//    } else if (x1 == x2 && y1 < y2) {
//        taildir = 1;
//    }
//
//
//    if (taildir == 0) {
//        //북쪽을 바라볼 때
//        if (isValid(x1, y1 + 1)) {
//            //북쪽에서 동쪽으로
//            if (!visited[x1][y1][x1][y1 + 1] && board[x1 - 1][y1 + 1] != 1) {
//                q.push({x1, y1, x1, y1 + 1});
//                visited[x1][y1][x1][y1 + 1] = true;
//            }
//        }
//
//        if(isValid(x1 , y1 - 1)){
//            //북쪽에서 서쪽으로
//            if (!visited[x1][y1][x1][y1 - 1] && board[x1 - 1][y1 - 1] != 1) {
//                q.push({x1, y1, x1, y1 - 1});
//                visited[x1][y1][x1][y1 - 1] = true;
//            }
//        }
//    } else if (taildir == 1) {
//        //동쪽을 바라볼 때
//        if (isValid(x1 - 1, y1)) {
//            //동쪽에서 북쪽으로
//            if (!visited[x1][y1][x1 - 1][y1] && board[x1 - 1][y1 + 1] != 1) {
//                q.push({x1, y1, x1 - 1, y1});
//                visited[x1][y1][x1 - 1][y1] = true;
//            }
//        }
//        if(isValid(x1 + 1, y1)){
//            //동쪽에서 남쪽으로
//            if (!visited[x1][y1][x1 + 1][y1] && board[x1 + 1][y1 + 1] != 1) {
//                q.push({x1, y1, x1 + 1, y1});
//                visited[x1][y1][x1 + 1][y1] = true;
//            }
//        }
//    } else if (taildir == 2) {
//        //남쪽을 바라볼 때
//        if (isValid(x1, y1 - 1)) {
//            //남쪽에서 서쪽으로
//            if (!visited[x1][y1][x1][y1 - 1] && board[x1 + 1][y1 - 1] != 1) {
//                q.push({x1, y1, x1, y1 - 1});
//                visited[x1][y1][x1][y1 - 1] = true;
//            }
//        }
//        if(isValid(x1, y1 + 1)){
//            //남쪽에서 동쪽으로
//            if (!visited[x1][y1][x1][y1 + 1] && board[x1 + 1][y1 + 1] != 1) {
//                q.push({x1, y1, x1, y1 + 1});
//                visited[x1][y1][x1][y1 + 1] = true;
//            }
//        }
//    } else if (taildir == 3) {
//        //서쪽을 바라볼 때
//        if (isValid(x1 - 1, y1)) {
//            //서쪽에서 북쪽으로
//            if (!visited[x1][y1][x1 - 1][y1] && board[x1 - 1][y1 - 1] != 1) {
//                q.push({x1, y1, x1 - 1, y1});
//                visited[x1][y1][x1 - 1][y1] = true;
//            }
//        }
//        if (isValid(x1 + 1, y1)){
//            //서쪽에서 남쪽으로
//            if (!visited[x1][y1][x1 + 1][y1] && board[x1 + 1][y1 - 1] != 1) {
//                q.push({x1, y1, x1 + 1, y1});
//                visited[x1][y1][x1 + 1][y1] = true;
//            }
//        }
//    }
//}
//
//
//int solution(vector<vector<int>> board) {
//    N = board.size();
//    int answer = 0;
//    queue<plane> q;
//    q.push({0, 0, 0, 1});
//    visited[0][0][0][1] = true;
//    int cnt = 0;
//    while (!q.empty()) {
//        int qSize = q.size();
//        for (int c = 0; c < qSize; c++) {
//            auto[x1, y1, x2, y2] = q.front();
//            q.pop();
//
//            if ((x1 == N - 1 && y1 == N - 1) || (x2 == N - 1 && y2 == N - 1)) {
//                answer = cnt;
//                return answer;
//            }
//
//            for (int d = 0; d < 4; d++) {
//                int nextX1 = x1 + moveX[d];
//                int nextY1 = y1 + moveY[d];
//                int nextX2 = x2 + moveX[d];
//                int nextY2 = y2 + moveY[d];
//
//                if (isValid(nextX1, nextY1) && isValid(nextX2, nextY2)) {
//                    if (!visited[nextX1][nextY1][nextX2][nextY2]) {
//                        q.push({nextX1, nextY1, nextX2, nextY2});
//                        visited[nextX1][nextY1][nextX2][nextY2];
//                    }
//                }
//            }
//            Rotate(board, x1, y1, x2, y2, q);
//        }
//        cnt++;
//    }
//}
//
//int main() {
//    cout << solution({{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}}) << "\n";
//}

#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> board;
int n;
int moveY[] = {-1,1,0,0};
int moveX[] = {0,0,-1,1};

struct Robot{
    int y1, x1, y2, x2;
    Robot(int y1, int x1, int y2, int x2) : y1(y1), x1(x1), y2(y2), x2(x2) {}

    Robot move(int dir){
        return Robot{y1 + moveY[dir], x1 + moveX[dir] , y2 + moveY[dir], x2 + moveX[dir]};
    }

    pair<Robot,Robot> rotate(int dir){
        return {{y1, x1, y1 + moveY[dir], x1 + moveX[dir]}, {y2, x2, y2 + moveY[dir], x2 +moveX[dir]}};
    }

    bool isValid(){
        return y1 >= 0 && x1 >= 0 && y2 >= 0 && x2 >= 0 && y1 < n && x1 < n && y2 < n && x2 < n  && !board[y1][x1] && !board[y2][x2];;

    }
};

bool operator < (Robot a, Robot b){
    return tie(a.y1, a.x1, a.y2, a.x2) < tie(b.y1, b.x1, b.y2, b.x2);
}

bool operator == (Robot a, Robot b){
    return tie(a.y1, a.x1, a.y2, a.x2) == tie(b.y1, b.x1, b.y2, b.x2)
    || tie(a.y1, a.x1, a.y2, a.x2) == tie(b.y2, b.x2, b.y1, b.x1);
}

map<Robot, int> dist;

vector<Robot> moveRobot(Robot &r){
    vector<Robot> ret;
    for(int i = 0; i < 4; i++){
        ret.push_back(r.move(i));
    }
    return ret;
}

vector<Robot> rotateRobot(Robot &r){
    vector<Robot> ret;
    for(int i = 0; i < 4; i++){
        //이동 방향으로 전진이 가능하면 그 방향으로 회전이 가능하다. 그림을 그려보면 이해가 잘간다.
        if(r.move(i).isValid()){
            pair<Robot, Robot> tmp = r.rotate(i);
            ret.push_back(tmp.first);
            ret.push_back(tmp.second);
        }
    }
    return ret;
}

bool isFinishCheck(Robot r){
    return r.y1 == n - 1 && r.x1 == n - 1 || r.y2 == n - 1 && r.x2 == n - 1;
}

int BFS(Robot protoType){
    dist[protoType] = 0;

    //초기 (0,0)(0,1)지점의 로봇을 탐색 시작값으로 한다.
    queue<Robot> q;
    q.push(protoType);

    while(!q.empty()){
        Robot cur = q.front();
        q.pop();

        int curDist = dist[cur];
        
        //로봇의 일부가 도착지점에 하나라도 도착하면 종료
        if(isFinishCheck(cur)){
            return curDist;
        }

        //움직이는 경우, 회전하는 경우를 구해준다.
        vector<Robot> next[2] = {{moveRobot(cur)}, {rotateRobot(cur)}};
        for(int i = 0; i < 2; i++){
            for(Robot R : next[i]){
                //탐색한적이없고 범위이내의 값이라면 거리를 갱신하고 다음 탐색을 진행한다.
                if(!dist.count(R) && R.isValid()){
                    dist[R] = curDist + 1;
                    q.push(R);
                }
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> Board) {
    board = Board;
    int answer = 0;
    n = board.size();
    answer = BFS({0,0,0,1});
    return answer;
}
int main() {
    cout << solution({{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}}) << "\n";
}

---

7번

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

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

---

접근방법

이전 삼성 SDS 프로 시험에서 본 문제와 유사했습니다. 문자열의 이분 탐색을 통해 lower_bound와 upper_bound를 구해서 빼주면 되는 문제였습니다. 이 과정에서 '?'가 접두사에 있는 경우가 문제가 되는데 reverse연산을 통해 변경해준 뒤 탐색을 진행하면 위치를 구할 수 있습니다. 탐색 값은 lower_bound시 가장 처음에 나오는 것을 구해야 하므로 '?'다음부터 'a'를 query의 size만큼 변경하여 탐색하여 구해주고 upper_bound는 가장 뒤에 있는 것을 구해야 하므로 '?'뒤부터 'z'를 채워서 탐색하여 구하면 됩니다.

---

실수

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

bool cmp(string a, string b){
    //문자열의 길이가 오름차순으로
    if(a.size() != b.size())
        return a.size() < b.size();
    //같다면 알파벳순으로
    if(a.size() == b.size())
        return a < b;
    return false;
}

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    vector<string> rwords = words;
    for(int i = 0; i < rwords.size(); i++){
        reverse(rwords[i].begin(), rwords[i].end());
    }
    //접두사에 ?가 있는 경우를 위한 배열
    sort(rwords.begin(), rwords.end(), cmp);
    sort(words.begin(), words.end(), cmp);

    for(auto &q : queries){
        int lowIndex, hiIndex;
        //query의 접두사에 ?가 있는 경우
        if(q[0] == '?'){
            //query도 뒤집어준다.
            reverse(q.begin(), q.end());
            int idx = q.find('?');
            for(int i = idx; i < q.size(); i++){
                q[i] = 'a';
            }
            lowIndex = lower_bound(rwords.begin(), rwords.end(), q,cmp) - rwords.begin();
            for(int i = idx; i < q.size(); i++){
                q[i] = 'z';
            }
            hiIndex = upper_bound(rwords.begin(), rwords.end(), q,cmp) - rwords.begin();
        }
        else{
            int idx = q.find('?');
            for(int i = idx; i < q.size(); i++){
                q[i] = 'a';
            }
            lowIndex = lower_bound(words.begin(), words.end(), q,cmp) - rwords.begin();
            for(int i = idx; i < q.size(); i++){
                q[i] = 'z';
            }
            hiIndex = upper_bound(words.begin(), words.end(), q, cmp) - rwords.begin();
        }
        //찾으려는 문자열의 뒤이 위치와 앞의 위치를 빼주면 개수가 나온다.
        answer.push_back(hiIndex - lowIndex);
    }
    return answer;
}

int main(){
    vector<string> str= {"frodo", "front", "frost", "frozen", "frame", "kakao"};
    vector<string> queries = {"fro??", "????o", "fr???", "fro???", "pro?"};
    vector<int> ret =  solution(str, queries);
    for(auto n : ret)
        cout << n << " ";
}