알고리즘 스터디 17일차 (정렬 문제 풀이)

1. 지형 이동

1) 문제

문제 설명
N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한 사항
land는 N x N크기인 2차원 배열입니다.
land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
land의 원소는 각 격자 칸의 높이를 나타냅니다.
격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
height는 1 이상 10,000 이하인 자연수입니다.

입출력 예

and height result
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18

2) 문제 분석 및 풀이

1) 설계, 분석

• 내가 도전했던 풀이
  • BFS를 통해서 구역을 나눔
  • 구역간의 이동가능한 경로중 최솟값을 가진 경로 기록
  • 최소 경로 찾기 <- 여기서 실패
    • 0->1, 0->2 같은 경우를 제대로 처리하지 못함
• 실제 풀이
  • 우선순위 큐를 이용한 BFS 사용
  • 현재까지 오면서 사용한 사다리 비용이 최소인 Cell이 맨 위로 오도록

2) 풀이

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

using namespace std;

vector<vector<bool>> visited;

struct Cell
{
    Cell(int x, int y): _x(x), _y(y), _heightDiff(0) {}
    Cell(int x, int y, int heightDiff): _x(x), _y(y), _heightDiff(heightDiff) {}
    int _x;
    int _y;
    //현재까지 오면서 사용한 사다리 비용
    int _heightDiff;

    bool operator<(const Cell& other) const
    {
        return _heightDiff > other._heightDiff;
    }
};

bool canGo(int x, int y, int n)
{
    if (x < 0 || x >= n) return false;
    if (y < 0 || y >= n) return false;
    if (visited[x][y]) return false;

    return true;

}

int BFS(vector<vector<int>>& land, const int& height)
{
    priority_queue<Cell> pq;
    visited.resize(land.size(), vector<bool>(land.size(), false));
    int totalCost = 0;

    pq.push(Cell(0,0));

    while(!pq.empty())
    {
        Cell top = pq.top();
        pq.pop();
        int cx = top._x;
        int cy = top._y;

        if (visited[cx][cy]) continue;

        visited[cx][cy] = true;
        totalCost+= top._heightDiff;

        vector<int> dx = {0, 1,  0, -1};
        vector<int> dy = {1, 0, -1,  0};

        for (int i=0; i<4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (canGo(nx, ny, land.size()))
            {
                int diff = abs(land[cx][cy]-land[nx][ny]);
                if ( diff > height)
                    pq.push(Cell(nx, ny, diff));

                else
                    pq.push(Cell(nx, ny, 0));
            }
        }
    }
    return totalCost;
}

int solution(vector<vector<int>> land, int height) {
    return BFS(land, height);
}

2. 튜플

1) 문제

문제 설명
셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, ..., an)
튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.
원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항
s의 길이는 5 이상 1,000,000 이하입니다.
s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
숫자가 0으로 시작하는 경우는 없습니다.
s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

입출력 예

s result
"{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4]
"{{20,111},{111}}" [111, 20]
"{{123}}" [123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1]

2) 문제 분석 및 풀이

1) 설계, 분석

• 나의 풀이
  • 2차원 벡터 생성
  • 각 부분 집합을 백터에 삽입
  • 벡터들을 크기순으로 오름 차수 정렬
  • 벡터들을 순회하며 원소가 set에 있는지 확인
    • 있으면 넘어가고
    • 없으면 set에 추가, answer에 추가
      • 크기순 정렬 했을때 전 부분집합과 비교해서 추가된 원소를 추가
• 다른 풀이
  • 계수정렬을 통해서 해결
  • 중복이 가장 많은 원소 -> 우선 순위가 높은 원소
  • 위 기준으로 원소 추가

2) 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    vector<vector<int>> setVec;
    unordered_set<int> answerSet;

    bool canInsert = false;
    int index = 0;
    string temp = "";
    for (auto it = s.begin() + 1; it != s.end() - 1; ++it)
    {
        if (canInsert && ( '0'<= *it && *it <= '9'))
        {
            temp += *it;
        }
        if (canInsert && *it == ',')
        {
            setVec[index].push_back(stoi(temp));
            temp = "";
        }
        if (*it == '{')
        {
            canInsert = true;
            setVec.push_back(vector<int>());
        }  
        if (*it == '}')
        {
            canInsert = false;
            setVec[index].push_back(stoi(temp));
            temp = "";
            index++;
        }
    }

    sort(setVec.begin(), setVec.end(), [](const vector<int> a, const vector<int> b){
        return a.size() < b.size();
    });

    for (auto& vec : setVec)
    {
        for (auto& e : vec)
        {
            if (answerSet.find(e) == answerSet.end())
            {
                answerSet.insert(e);
                answer.push_back(e);
            }
        }
    }

    return answer;
}

3. 파일명 정렬

1) 문제

문제 설명
소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.

파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.

HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
파일명 HEAD NUMBER TAIL
foo9.txt foo 9 .txt
foo010bar020.zip foo 010 bar020.zip
F-15 F- 15 (빈 문자열)
파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.

파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
무지를 도와 파일명 정렬 프로그램을 구현하라.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

입력 형식
입력으로 배열 files가 주어진다.

files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)

입출력 예제

입력: ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]
출력: ["img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"]

입력: ["F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"]
출력: ["A-10 Thunderbolt II", "B-50 Superfortress", "F-5 Freedom Fighter", "F-14 Tomcat"]

2) 문제 분석 및 풀이

1) 설계, 분석

• 각 문자열의 Head, Number, Tail 정보를 가진 구조체 정의
• 문자열 순회하며 위 정보를 가지는 구조체들을 생성
• 구조체들을 정렬
  • Head 사전순인데 대소문자 무시 때문에 그냥 대문자로 놓고 비교
    • Head 사전순 동일 시 Number를 정수로 바꿔서 오름차순
    • Head 사전순 다를시 사전순

2) 풀이

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

using namespace std;

struct FileName
{
    string Head;
    string Number;
    string Tail;
};

bool cmp(const FileName a, const FileName b)
{
    string Ahead = a.Head;
    string Bhead = b.Head;
    transform(Ahead.begin(), Ahead.end(), Ahead.begin(), ::toupper);
    transform(Bhead.begin(), Bhead.end(), Bhead.begin(), ::toupper);

    if (Ahead == Bhead)
    {
        int A = stoi(a.Number);
        int B = stoi(b.Number);
        return A < B;
    }
    return Ahead < Bhead;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<FileName> fileNameVec;

    for (auto& file : files)
    {
        string head = "";
        string number = "";
        string tail = "";
        bool headDone = false;
        bool numberDone = false;
        for (auto it = file.begin(); it != file.end(); ++it)
        {
            if ('0'<= *it && *it <= '9')
                headDone = true;
            if (headDone && !('0'<= *it && *it <= '9'))
                numberDone = true;

            if (!headDone)
            {
                head += *it;
            }
            else if (!numberDone)
            {
                number += *it;
            }
            else
            {
                tail += *it;
            }
        }
        fileNameVec.push_back({head, number, tail});
    }

    stable_sort(fileNameVec.begin(), fileNameVec.end() ,cmp);
    for (auto& fn : fileNameVec)
    {
        string temp = "";
        temp += fn.Head;
        temp += fn.Number;
        temp += fn.Tail;
        answer.push_back(temp);
    }
    return answer;
}

4. H-index

1) 문제

문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한 사향
입력으로 배열 files가 주어진다.

과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예제

citations return
[3, 0, 6, 1, 5] 3

2) 문제 분석 및 풀이

1) 설계, 분석

• 배열 오름차순 정렬
• 배열을 순회
  • h = size - 현재 인덱스 : 이후의 논문 개수 ( 현재 논문보다 인용이 많이된 논문 개수)
  • h 가 현재 논문의 인용수 보다 작거나 같으면 ( "인용 수가 h 이상인 논문이 h편 이상인가?" )
    • answer = max (answer, h)

2) 풀이

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

using namespace std;

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

    sort(citations.begin(), citations.end());

    for (int i=0; i<citations.size(); i++)
    {
        int h = citations.size() - i;
        if (h <= citations[i])
            answer = max(answer , h);
    }
    return answer;
}