22.04.05. 풀었던 문제들

1. n^2 배열 자르기

규칙 찾기 문제였다.

​

n = 3이 주어졌다고 하자. 그러면 arr는 아래 그림과 같다.

1 2 3

2 2 3

3 3 3

idx에 따른 값은 아래와 같다.

(0,0) : 1

(1,0), (1,1), (0,1) : 2

(2, 0), (2, 1), (2,2), (1,2), (0,2) : 3

보이는가? arr[i][j] = max(i, j) + 1이다.

​

또, n이 주어졌을 때, 특정 idx가 주어지면 배열의 그것으로 바꿀 수 있겠는가? -> Yes.

n/4, n%4로 바꿀 수 있다.

​

​

2. 방문 길이

중복되는 경우는 세지 않으니, map이나 set으로 풀면 되는 문제다.

그리고 팁. 이 문제와 같이 좌표평면에서 상하좌우로 이동하는 경우, if나 case를 써서 나누지 말고 아래와 같은 방법을 쓰자. 좀 더 간단하게 이동을 표현할 수 있다.

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

 

3. 이진 변환 반복하기

단순 구현 문제다.

​

​

4. 점프와 텔레포트

2진법 변환 문제다. (규칙찾기)

​

​

5. 게임 맵 최단거리

DFS/BFS로 풀 수 있는 문제다. 안 건든 지 오래되었다보니 조금 어렵다...

일단 DFS의 경우, 모든 경우의 수를 따져봐야 하기 때문에 시간초과가 난다. 따라서 최단거리 탐색 했을 때 해가 보이는 BFS로 탐색을 하는 게 더 빠른 시간 내에 가능할 것이다. 일단 코드는 BFS, DFS 둘 다 올린다. 많이 더럽지만 이 코드를 반면교사 삼아 발전해 나갈 것이다.

 

// 게임 맵 최단거리

#include<vector>
#include <queue>

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

using namespace std;

typedef pair<int, int> pii;

void BFS(pii max_rc, pii init_point, vector<vector<int>>& maps, vector<vector<int>>& dist, vector<vector<bool>>& visited){
    queue<pii> q;
    q.push(init_point);
    dist[init_point.first][init_point.second] = 1;
    visited[init_point.first][init_point.second] = true;
    
    while(!q.empty()){
        pii cur_point = q.front(); q.pop();
        if(cur_point == max_rc){
            return;
        }
        for(int i = 0; i<4; i++){
            pii next_point = cur_point;
            next_point.first += dr[i];
            next_point.second += dc[i];
            if(0 <= next_point.first && next_point.first <= max_rc.first && 0 <= next_point.second && next_point.second <= max_rc.second && maps[next_point.first][next_point.second] && !visited[next_point.first][next_point.second]){
                q.push(next_point);
                dist[next_point.first][next_point.second] = dist[cur_point.first][cur_point.second] + 1;
                visited[next_point.first][next_point.second] = true;
            }
        }
    }
}

int solution(vector<vector<int>> maps)
{
    pii max_rc = {maps.size(), maps[0].size()};
    vector<vector<int>> dist(max_rc.first, vector<int>(max_rc.second, -1));
    vector<vector<bool>> visited(max_rc.first, vector<bool>(max_rc.second, false));
    BFS({max_rc.first-1, max_rc.second-1}, {0, 0}, maps, dist, visited);
    return dist[max_rc.first-1][max_rc.second-1];
}

// BFS ? -> 도달하면 바로 종료 및 해당 값 return. 이게 더 좋을 것임.
// DFS ? -> 모든 탐색 해 보아야 함. 오랜만에 DFS 쓰니까 너무 헷갈린당.

/*
void DFS(int max_r, int max_c, int r, int c, vector<vector<int>>& maps, vector<vector<bool>>& visited, vector<vector<int>>& dist, int cur_dist){
    if(r == max_r && c == max_c){
        dist[r][c] = min(dist[r][c], cur_dist);
        return;
    }
    dist[r][c] = cur_dist;
    for(int i = 0; i<4; i++){
        int tempr = r + dr[i];
        int tempc = c + dc[i];
        if(0 <= tempr && tempr <= max_r && 0 <= tempc && tempc <= max_c && maps[tempr][tempc] == 1 && !visited[tempr][tempc]){
            visited[tempr][tempc] = true;
            DFS(max_r, max_c, tempr, tempc, maps, visited, dist, cur_dist+1);
            visited[tempr][tempc] = false;
        }
    }
}

int solution(vector<vector<int>> maps)
{
    int max_r = maps.size(), max_c = maps[0].size();
    vector<vector<bool>> visited(max_r, vector<bool>(max_c, false));
    vector<vector<int>> dist(max_r, vector<int>(max_c, -1));
    dist[max_r-1][max_c-1] = 1000000;
    DFS(max_r-1, max_c-1, 0, 0, maps, visited, dist, 1);
    int answer = dist[max_r-1][max_c-1];
    return answer == 1000000? -1 : answer;
}
*/

 

 

6. 스킬트리

skill tree가 성립하려면, skill 문자열 안에 있는 순서대로 skill이 있어야 한다. 문제 예시를 들자면 CBD라면 허용되는 skill은

(공백)

C

CB

CBD

이러한 순서로만 허용된다. 따라서 skill tree안에 있는 문자열 중, skill 내부에 있는 문자들만 순서를 유지한 채로 뽑을 것이다. 이 문자열들이 skill.substr(0, x), 0 <= x <= skill.length()를 만족하는지 확인하면 될 것이다.

// 스킬트리

#include <set>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    set<char> skill_set;
    set<string> tree_set;
    for(int i = 0; i<skill.length(); i++){
        skill_set.insert(skill[i]);
        tree_set.insert(skill.substr(0, skill.length()-i));
    }
    
    int answer = 0;
    for(string s : skill_trees){
        string result = "";
        for(char c : s){
            if(skill_set.find(c) != skill_set.end()){
                result += c;
            }
        }
        if(tree_set.find(result) != tree_set.end() || result == "") answer++;
    }
    
    return answer;
}
​

 

7. 영어 끝말잇기

set(중복 여부 판단)과 string의 front(), back() 함수를 알고 있다면 아주 쉽게 풀 수 있는 문제였다.

​

​

8. 괄호 회전하기

stack 기본 + substr을 사용할 수 있는지 문제이다.

​

​

9. 예상 대진표

a와 b가 같은 그룹에 있을 때까지 2로 나눠주면 되는 문제다. 같은 그룹의 판단을 어떻게 하느냐? cnt를 0으로 두고, a==b가 될때까지 돌리면 된다.

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int cnt = 0;
    a--; b--;
    while(a != b){
        a/=2; b/=2;
        cnt++;
    }
    
    /*do{
        if(a&1) a++; if(b&1) b++;
        a/=2; b/=2;
        cnt++;
    }while(abs(a-b) != 0);*/
    
    return cnt;
}