문제 - 수 정렬하기2

해결

#include <iostream>
#include <vector>

using namespace std;

int* arr;
int* result;

void merge(int left, int right)
{   
    int mid = (left + right)/2; //배열의 중간부분
    int i = left; // 왼쪽배열 시작 인덱스
    int j = mid + 1; // 오른쪽 배열 시작 인덱스
    int k = left; // 임시배열의 인덱스

    while (i <= mid && j <= right) // 두 배열중 하나라도 다 비워지면 종료
    {
        if (arr[i] <= arr[j])
        {
            result[k++] = arr[i++];
        }
        else
        {
            result[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        result[k++] = arr[i++];
    }
    while (j <= right) {
        result[k++] = arr[j++];
    }
    for (int i = left; i <= right; i++)
    {
        arr[i] = result[i];
    }
}

void partition(int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right)/2; // 중간에서 하나더 왼쪽으로 가게됨.
        partition(left, mid);
        partition(mid+1, right);
        merge(left, right);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    arr = new int[N];
    result = new int [N];

    for(int i = 0; i<N; i++)
    {
        cin >> arr[i];
    }
    partition(0, N-1);
    
    for (int i = 0; i < N; i++) 
    {
        cout << arr[i] << "\n";
    }
    delete[] arr;
    delete[] result;
}

병합정렬을 사용하여 숫자를 받고 array로 저장한후 정렬하였습니다. 주의할 점은 '\n'대신 endl을 사용 할 경우 버퍼를 계속 flush하여서 매우 느려져서 통과 못합니다. 이것때문에 시간 엄청 썻네요 ㅠㅠ..

문제 - 좌표 정렬하기

해결

#include <iostream>
#include <vector>
#include <utility>

using namespace std;



struct coordinate
{
    int x;
    int y;
};

coordinate* arr;
coordinate* temp;

void merge(int left, int right)
{
    int mid = (left + right)/2;
    int i = left;
    int j = mid + 1;
    int k = left;
    while(i <= mid && j <= right)
    {
        if (arr[i].x < arr[j].x)
        {
            temp[k++] = arr[i++];
        }
        else if (arr[i].x > arr[j].x)
        {
            temp[k++] = arr[j++];
        }
        else //만약에 x 좌표가 같을 경우
        {
            if (arr[i].y < arr[j].y)    
            {
                temp[k++] = arr[i++];
            }
            else 
            {
                temp[k++] = arr[j++];
            }
        }
    }
    while (i <= mid) //왼쪽 행렬이 다 안채워졌을 경우 temp 행렬로 넣어준다.
    {
        temp[k++] = arr[i++];
    }
    while (j <= right) //오른른쪽 행렬이 다 안채워졌을 경우 temp 행렬로 넣어준다.
    {
        temp[k++] = arr[j++];
    }
    for (int i = left; i <= right; i++) // 임시행렬의 값을 원본 행렬로 복사한다.
    {
        arr[i] = temp[i];
    }
}

void partition(int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right)/2;
        partition(left, mid);
        partition(mid + 1, right);
        merge(left, right);
    }
}

int main()
{
    int N;
    cin >> N;
    arr = new coordinate[N];
    temp = new coordinate[N];


    for(int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        arr[i].x = x;
        arr[i].y = y;
    }
    partition(0, N-1);
    for (int i = 0; i < N; i++)
    {
        cout << arr[i].x << " " << arr[i].y <<"\n";
    }
    delete[] arr;
    delete[] temp;  

}

이 문제는 pair로 묶어서 저장하는 것이아니라 coordinate라는 x, y 요소를 가지는 구조체 배열을 만들어서 입력값을 저장했습니다. 동적 메모리 할당을 하기 때문에 함수 종료 시 자동 해제되는 정적 메모리 할당과 달리 main함수가 끝날때 delete[]함수를 통해 메모리를 해제 해주어야 합니다. 이후 병합정렬을 통해 merge알고리즘에서 x값이 같을경우 y값을 비교하여 작은 값을 임시배열에 넣어주는 식으로 해결 했습니다.

문제 - 체스판 다시 칠하기

해결

#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

vector<vector<char>> reference1(8, vector<char>(8));
vector<vector<char>> reference2(8, vector<char>(8)); // reference 1,2는 가능한 두가지 조합의 체스판이다.

char **matrix;

int compare(int N, int M)
{
    int ref1 = 0;
    int ref2 = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (reference1[i][j] == matrix[N+i][M+j])
            {
                ref1++;
            }
            else
            {
                ref2++;
            }
        }
    }
    int temp = (ref1 > ref2) ? ref1 : ref2; //둘중에 큰 값을 저장
    return (64 - temp); // 바꾸어야할 타일의 개수를 반환
}

int difference(int row, int col)
{
    int N = row - 8;
    int M = col - 8;
    int min = 10000;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            int m = compare(i, j); // m은 i,j번째의 타일을 8x8 모양의 체스판의 (1,1)이라고 할때 reference와 비교할때때 색을 바꾸어야할 타일의 최소 개수
            if (m < min)
            {
                min = m;
            }
        }
    }
    return min;
}

int main()
{
    int N, M;
    cin >> N >> M;
    matrix = new char*[N];
    for (int i = 0; i < N; i++)
    {
        matrix[i] = new char[M];
    }
    vector<char> row1 = {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'};
    vector<char> row2 = {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'};
    for (int i = 0; i < 8; i++)
    {
        if (i%2 == 0) // 짝수일 경우
        {
            reference1[i] = row1;
            reference2[i] = row2;   
        }
        else{
            reference1[i] = row2;
            reference2[i] = row1;
        }
    }
    for (int i = 0; i < N; i++){
        string temp;
        cin >> temp;
        for (int j = 0; j < M; j++){
            matrix[i][j] = temp[j];
        }
    }
    int min = difference(N, M);
    cout << min;

}

이 문제에서는 이차원 배열로 체스판을 저장해야 했습니다. char 자료형을 가진 동적 2차원 배열을 만들어줍니다. 이때 더블포인터로 저장하는것은 matrix = new char*[N]; 포인터를 저장하는 배열이기 떄문입니다. 예를들어 char[1]은 두번재 row의 첫번째 원소를 가리키는 포인터인 것이죠. 또한 char로 저장하기 위해서는 'B'로 저장하여야지 "B"로 저장하기 되면 B와 null문자를 저장하게 되어서 char자료형으로 담을수가 없게 됩니다. 이렇게 입력으로 들어온 체스판과 reference로 저장된 체스판(만들어질수 있는 두가지 경우의 수를 저장합니다)의 원소를 비교하여 바꾸어야하는 타일의 수만큼을 반환하는 함수를 작성했습니다.

문제 - 카드2

해결

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

using namespace std;


int calculate(vector<int> vec, bool is_even) // is_even은 전에 함수가 짝수 엿는지에 대한 정보를 가지고 있음.
{
    vector<int> temp;
    int index = 0;
    if (vec.size() == 1)
    {
        return vec.back();
    }
    for (int i : vec)
    {
        if (index % 2 != 0 && is_even) //전의 벡터 사이즈가 짝수였으면 인덱스가 홀수인 값을 벡터로 복사
        {
            temp.emplace_back(i);
        }
        else if(index % 2 == 0 && !is_even) // 전의 벡터 사이즈가 홀수 이면 인덱스가 짝수인 값을 복사
        {
            temp.emplace_back(i);
        }
        index++;
    }
    if (vec.back() == temp.back())
    {
        is_even = true;
    }
    else 
    {
        is_even = false;
    }
    int result = calculate(temp, is_even);
    
    return result;
}


int main()
{
    int num;
    bool is_even = true;
    vector<int> numbers;
    cin >> num;
    for (int i = 1; i <= num; i++)
    {
        numbers.emplace_back(i);
    }
    int result = calculate(numbers, is_even);
    cout << result;
}

위의 코드는 큐로 푸는 문제인지 모르고 시도했을때의 코드입니다. 모든 카드를 vector형태로 저장한 후 재귀형태의 함수를 작성해서 N개의 카드 중 짝수번째 혹은 홀수번째 카드를 저장한 벡터를 만듭니다. temp 벡터와 기존 벡터의 마지막 값이 같은지로 다음 함수의 짝수번째를 저장할지 홀수 번째를 저장할지 결정합니다.

문제 - 괄호

해결

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


using namespace std;

string is_vps(string s)
{
    int count = 0;
    for (char i : s)
    {
        if (i == '(')
        {
            count++; // 오른쪽 괄호가 나오면 count up
        }
        else
        {
            count--; // 왼쪽 괄호가 나오면 count down
        }
        if (count < 0)
        {
            return "NO";
        }
    }
    if (count == 0)
    {
        return "YES";
    }
    else 
    {
        return "NO";
    }
}

int main()
{
    int num;
    vector<string> vec;
    cin >> num;
    cin.ignore();
    for (int i = 0; i < num; i++)
    {
        string line;
        getline(cin, line);
        vec.emplace_back(line);
    }
    for (string i : vec)
    {
        string result = is_vps(i);
        cout << result << endl;
    }
}

vps가 되기 위해서는 문장이 끝났을때 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 합니다. 또한 count를 0으로 초기화 시키고 왼쪽 괄호가 들어올 때를 +1 오른쪽 괄호가 들어올때 -1 이라고 할때 count가 음수가 되는 순간이 생기면 안됩니다. 따라서 is_vps()라는 함수를 만들고 들어오는 string에서 이러한 점을 확인한후 string을 return하게 됩니다.