Codetesing의 코딩공부

그래프 최단거리 탐색 문제이다.

다익스트라로 풀려다가 그냥 DFS로 풀어봤는데 통과되었다.

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

using namespace std;

vector<vector<pair<int, int>>> G(51, vector<pair<int, int>>());
vector<int> node;
bool visited[51] = { false };
int cnt = 0;

void DFS(int ind, int len, int max_len)
{
    if (len > max_len)
        return;

    visited[ind] = true;
    node.push_back(ind);
    for (int i = 0; i < G[ind].size(); i++)
        if (!visited[G[ind][i].first])
            DFS(G[ind][i].first, len + G[ind][i].second, max_len);
    visited[ind] = false;
}

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;

    for (int i = 0; i < road.size(); i++)
    {
        G[road[i][0]].push_back(make_pair(road[i][1], road[i][2]));
        G[road[i][1]].push_back(make_pair(road[i][0], road[i][2]));
    }

    DFS(1, 0, K);

    sort(node.begin(), node.end());
    node.erase(unique(node.begin(), node.end()), node.end());

    answer = node.size();

    return answer;
}

딱히 어렵진 않았는데 경우 생각하는게 귀찮았다.

string 변환에 최적화가 안된 느낌인데 잘 모르겠다 ㅠ

옳은 문자열인지 확인은 stack 개념을 이용해서 했다.

#include <string>
#include <vector>

using namespace std;

bool IS_RIGHT(string s)
{
    vector<char> stack;

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            stack.push_back(s[i]);
        else
        {
            if (stack.empty())
                return false;
            else
            {
                if (stack[stack.size() - 1] == '(' && s[i] == ')')
                    stack.pop_back();
                else if (stack[stack.size() - 1] == '{' && s[i] == '}')
                    stack.pop_back();
                else if (stack[stack.size() - 1] == '[' && s[i] == ']')
                    stack.pop_back();
                else
                    return false;
            }
        }
    }

    if (!stack.empty())
        return false;
    else
        return true;
}

int solution(string s) {
    int answer = 0;

    for (int i = 0; i < s.size(); i++)
    {
        if (IS_RIGHT(s))
            answer++;
        char temp = s[0];
        s.erase(s.begin());
        s.push_back(temp);
    }

    return answer;
}

그냥 시뮬레이션 문제같다.

어려운것 없이 조건에 맞춰 구현하면 되었다.

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 1;

    while (1)
    {
        if (a % 2 == 1)
            a++;
        if (b % 2 == 1)
            b++;

        if (a / 2 == b / 2)
            break;
        a /= 2;
        b /= 2;
        answer++;
    }

    return answer;
}

자주 풀던 문제의 유형중 하나이다.

처음엔 그냥 BFS해서 풀었더니 TL이 초과되어서 visited를 최단거리로 바꾸어 풀었다.

#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> map;
vector<vector<int>> visited(101, vector<int>(101, 987654321));
int N, M;
int ROTATE_X[] = { 0, -1, 0, 1 };
int ROTATE_Y[] = { -1, 0, 1, 0 };

void BFS()
{
    queue<pair<int, int>> loc;
    int cur_x, cur_y;
    int next_x, next_y;

    loc.push(make_pair(0, 0));
    visited[0][0] = 1;

    while (!loc.empty())
    {
        cur_x = loc.front().first;
        cur_y = loc.front().second;
        loc.pop();
        for (int i = 0; i < 4; i++)
        {
            next_x = cur_x + ROTATE_X[i];
            next_y = cur_y + ROTATE_Y[i];

            if (next_x < 0 || next_x > N || next_y < 0 || next_y > M)
                continue;
            if (map[next_x][next_y] == 0)
                continue;
            if (visited[next_x][next_y] > visited[cur_x][cur_y] + 1)
            {
                visited[next_x][next_y] = visited[cur_x][cur_y] + 1;
                loc.push(make_pair(next_x, next_y));
            }
        }
    }
}

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    map = maps;

    N = maps.size() - 1;
    M = maps[0].size() - 1;

    BFS();

    if (visited[N][M] == 987654321)
        answer = -1;
    else
        answer = visited[N][M];

    return answer;
}

그냥 시키는대로 구현 하면 되었다.

#include <string>
#include <algorithm>

using namespace std;

int solution(string name)
{
    int answer = 0;
    int shift = name.length() - 1;
    for (int i = 0; i < name.length(); i++)
    {
        if (name[i] == 'A')
        {
            int target = i;
            while (target < name.length() && name[target] == 'A')
                target += 1;
            int left = i == 0 ? 0 : i - 1;
            int right = name.length() - target;
            shift = min(shift, left + right + min(left, right));
        }
    }
    answer += shift;
    for (auto c : name)
        answer += min(c - 'A', 'Z' - c + 1);
    return answer;
}