알고리즘 스터디 18일차 (문제 풀이)

1. 집합의 표현(1717)

1) 문제

문제 설명
초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은
$0$ $a$ $b$의 형태로 입력이 주어진다. 이는
$a$가 포함되어 있는 집합과,
$b$가 포함되어 있는 집합을 합친다는 의미이다.
두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은
$1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서
$a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한
$1 ≤ n ≤ 1\,000\,000$ 
$1 ≤ m ≤ 100\,000$
$0 ≤ a, b ≤ n$ 
$a$,
$b$는 정수
$a$와
$b$는 같을 수도 있다.

2) 문제 분석 및 풀이

1) 설계, 분석

유니온 파인드를 구현하면 쉽게 풀 수 있는 문제

2) 풀이

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> parents;

int Find(int x)
{
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

bool DetermineSameSet(int a, int b)
{
    int A = Find(a);
    int B = Find(b);

    return A == B;
}

void Union(int a, int b)
{
    if (!DetermineSameSet(a,b))
    {
        parents[Find(b)] = Find(a);
    }
}

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

    cin >> n >> m;

    // 초기상태
    // 자신의 부모는 자기 자신
    parents.resize(n+1);
    for (int i = 0; i < parents.size(); ++i)
    {
        parents[i] = i;
    }

    while (m--)
    {
        int cmd,a,b;
        cin >> cmd >> a >> b;
        if (cmd == 0)
        {
            Union(a,b);
        }
        else
        {
            cout << (DetermineSameSet(a,b) ? "yes" : "no") << "\n";
        }
    }
}

2. 줄 세우기(2252)

1) 문제

문제 설명
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 키라는 특수조건 때문에 사이클이 생기지 않는다
  • a->b b->c c->a 를 생각해보면 a는 b보다 작고 b는 c보다 작은 상태에서 c가 a보다 작은 것은 모순.
• 위상정렬을 통해서 문제해결 (여기서는 BFS를 사용함)
• 그래프의 정보는 인접 리스트 형태로 저장

2) 풀이

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

using namespace std;

int n, m;
vector<int> enterCount;
vector<vector<int>> adjList;

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

    cin >> n >> m;
    enterCount.resize(n+1, 0);
    adjList.resize(n+1);
    for (int i=0; i < m ; i++)
    {
        int from, to;
        cin >> from >> to;
        adjList[from].push_back(to);
        enterCount[to]++;
    }

    queue<int> q;
    for (int i = 1; i < n+1; i++)
    {
        if (enterCount[i] == 0)
        {
            q.push(i);
        }
    }

    while (!q.empty())
    {
        int front = q.front();
        q.pop();
        cout << front << " ";
        for (auto& to : adjList[front])
        {
            enterCount[to]--;
            if (enterCount[to] == 0)
            {
                q.push(to);
            }
        }
    }
}

3. 트리(4803)

1) 문제

문제 설명
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 사이클의 존재여부를 확인하는 문제
• 유니온 파인드를 통해서 사이클의 여부를 알아내고 추가 작업을 통해 사이클임을 표시
  • 서로 같은 루트를 가지면 양쪽 부모를 모두 0으로 바꿈
• 모든 간선 입력이 끝나면 정점을 순회, 자신의 부모가 자기 자신인 경우 => 자신이 트리의 루트
  • 위 경우를 카운트

2) 풀이

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> parents;

int Find(int x)
{
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

bool DetermineSameSet(int a, int b)
{
    int A = Find(a);
    int B = Find(b);

    return A == B;
}

void Union(int a, int b)
{
    int A = Find(a);
    int B = Find(b);

    if (A == 0 || B == 0)
    {
        parents[B] = 0;
        parents[A] = 0;
    }
    else if (A != B)
    {
        parents[B] = A;
    }
    else if (A == B)
    {
        parents[B] = 0;
        parents[A] = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int caseNum = 1;
    while (true)
    {
        int n, m;
        cin >> n >> m;
        if ((n==0) && (m==0)) break;

        parents.clear();
        parents.resize(n+1);
        for (int i = 0; i < n+1; i++)
        {
            parents[i] = i;
        }

        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            Union(a,b);
        }

        int treecnt = 0;
        for (int i = 1; i < n + 1; i++)
        {
            if (parents[i] == i)
                treecnt++;
        }

        cout << "Case " << caseNum <<": ";
        if (treecnt == 0)
        {
            cout << "No trees.\n";
        }
        else if (treecnt == 1)
        {
            cout << "There is one tree.\n";
        }
        else if (treecnt > 1)
        {
            cout << "A forest of " << treecnt << " trees.\n";
        }
        caseNum++;
    }
}

4 이차원 배열과 연산(17140)

1) 문제

문제 설명
크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력
첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 원하는 행, 열에 대해서 각 숫자의 등장 횟수를 센다.
  • (a,n) 형태로 저장 (a가 n개)
  • n기준 오름차순, 동일시 a기준 오름차순으로 정렬
  • a,n 순서로 원래 행, 열에 차례차례 덮어쓰기
  • 혹시나 길이가 줄었으면 0으로 밀기

2) 풀이

#include <iterator>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int r,c,k;
vector<vector<int>> board(100, vector<int>(100,0));

bool cmp(const pair<int,int>& a, const pair<int,int>& b)
{
     if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> r >> c >> k;
    int cr = 3;
    int cc = 3;

    int eA, eB, eC;
    for (int i=0; i < 3; i++)
    {
        cin >> eA >> eB >> eC;
        board[i][0] = eA;
        board[i][1] = eB;
        board[i][2] = eC;
    }

    int sec = 0;
    while (true)
    {
        if (sec > 100)
        {
            cout << -1 << '\n';
            break;
        }

        if (board[r-1][c-1] == k)
        {
            cout << sec << '\n';
            break;
        }

        unordered_map<int, int> cntMap;
        // R operation
        if (cr >= cc)
        {
           int ccindex = cc;
           int crindex = cr;
           // 현재 행렬을 순회
           for (int i=0; i < crindex; i++)
           {
                cntMap.clear();
                //i번째 행에서 각 숫자가 몇번 나오는지 기록
                for (int j=0; j < ccindex; j++)
                {
                    if (board[i][j] == 0 ) continue;
                    cntMap[board[i][j]]++;
                }
                // 위 정보를 토대로 정렬 (횟수 오름차순, 값 오른차순)
                vector<pair<int,int>> forSort (cntMap.begin(), cntMap.end());
                sort(forSort.begin(), forSort.end(), cmp);

                // 새로운 값으로 교환
                // 1 2 1 -> 2가 1개, 1이 2개 식으로 정렬
                // key value를 차례로 넣으면 됨
                // 2 1 1 2
                int j = 0;
                for (j=0; j < forSort.size() && j < 50 ; j++)
                {
                    board[i][2*j] = forSort[j].first;
                    board[i][2*j + 1] = forSort[j].second;
                }

                // 333 같은 경우 3이 3개 로 길이가 줄어들기 때문에
                // 남은 공간에 0으로 밀어야함
                for (j = forSort.size() * 2; j < ccindex; j++)
                {
                    board[i][j] = 0;
                }

                // 열의 최대값 저정
                cc = max(cc , static_cast<int>(forSort.size()) * 2);
                if (cc > 100) cr = 100;
           }
        }
        // C operation
        // 위의 함수를 단순이 행과 열을 바꿔서 할 뿐 원리는 같음
        else if (cr < cc)
        {
           int ccindex = cc;
           int crindex = cr;
           for (int i=0; i < ccindex; i++)
           {
                cntMap.clear();
                for (int j=0; j < crindex; j++)
                {
                    if (board[j][i] == 0 ) continue;
                    cntMap[board[j][i]]++;
                }
                vector<pair<int,int>> forSort (cntMap.begin(), cntMap.end());
                sort(forSort.begin(), forSort.end(), cmp);

                int j = 0;
                for (j=0; j < forSort.size() && j < 50 ; j++)
                {
                    board[2*j][i] = forSort[j].first;
                    board[2*j + 1][i] = forSort[j].second;
                }

                for (j = forSort.size() * 2; j < ccindex; j++)
                {
                    board[j][i] = 0;
                }

                cr = max(cr , static_cast<int>(forSort.size()) * 2);
                if (cr > 100) cr = 100;
           }
        }
        sec++;
    }
}

4 사이클 게임(20040)

1) 문제

문제 설명
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

입력
입력은 표준입력을 사용한다. 입력의 첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다. 게임에서 사용하는 n개의 점에는 0 부터 n − 1 까지 고유한 번호가 부여되어 있으며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다 (1 ≤ i ≤ m).

출력

출력은 표준출력을 사용한다. 입력으로 주어진 케이스에 대해, m 번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력하고, m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 유니온 파인드를 통한 사이클 판별

2) 풀이

#include <iterator>
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> parents;
vector<int> rankVec;

int Find(int x)
{
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

bool Union(int a, int b)
{
    int A = Find(a);
    int B = Find(b);
    bool mergeSucess = false;

    if (A != B)
    {
        if (rankVec[A] <= rankVec[B])
        {
            parents[A] = B;
            rankVec[B] += rankVec[A];
        }
        else
        {
            parents[B] = A;
            rankVec[A] += rankVec[B];
        }
        mergeSucess = true;
    }
    return mergeSucess;
}

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

    cin >> n >> m;

    // 초기상태
    rankVec.resize(n+1,1);
    // 자신의 부모는 자기 자신
    for (int i = 0; i <= n; ++i)
    {
        parents.push_back(i);
    }

    int answer = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        if (!Union(a,b))
        {
            answer = i;
            break;
        }
    }

    cout << answer << "\n";
}

4 Orderly Queue

1) 문제

문제 설명
You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string.
?
Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

Example 1:

Input: s = "cba", k = 1
Output: "acb"
Explanation:
In the first move, we move the 1st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1st character 'b' to the end, obtaining the final result "acb".
Example 2:

Input: s = "baaca", k = 3
Output: "aaabc"
Explanation:
In the first move, we move the 1st character 'b' to the end, obtaining the string "aacab".
In the second move, we move the 3rd character 'c' to the end, obtaining the final result "aaabc".

2) 문제 분석 및 풀이

1) 설계, 분석

• 횟수 상관없이 만들 수 있는 단어중 사전순으로 제일 작은 단어 만들기
  • K>1 이면 원하는 순서의 문자열을 만들 수 있음 (정렬 후 반환)
  • K == 1이면 문자열 회전 시키면서 가장 작은 것 출력

2) 풀이

class Solution {
public:
    string orderlyQueue(string s, int k) {
        string temp = s;
        if (k > 1)
        {
            sort(temp.begin(), temp.end());
        }   
        else
        {
            string smallest = temp;
            for (int i=0; i<s.size(); i++)
            {
                temp = "";
                for (int j=0; j<s.size(); j++)
                {
                    temp += s[(j + i) % s.size()];
                }
                if (temp < smallest)
                    smallest = temp;
            }
            temp = smallest;
        }
        return temp;
    }
};