Codeforces Round #599 (Div.2)

문제 링크 : https://codeforces.com/contest/1243

A. Maximum Square

문제 요약

1 x n 길이의 직사각형들을 붙여서 만들 수 있는 최대 크기의 정사각형(한 변의 길이가 k)을 찾는 문제이다.

 

접근 방법

어차피 직사각형들을 서로 붙일 것인데 정렬을 시키면 더욱 편하게 풀 수 있을 것이라 생각했고,

직사각형의 개수 n도 최대 1,000 이하라서 O(nlogn)인 정렬을 사용해도 큰 문제가 되지 않을 거라 판단했다.

 

시간복잡도

시간복잡도는 정렬에서 O(nlogn) 이 소요되고 최대 한 변의 길이(square)를 찾는 부분에서 O(n)이 소요되므로,

총 O(nlogn) 이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int>& V) {
    sort(V.begin(), V.end()); //vector 오름차순 정렬
    
    int square = 1; //한 변의 길이
    int min_height, max_width;
    for(int i = V.size()-1; i >= 0; i--) {
        min_height = V[i]; //정렬한 vector이므로 min_height는 제일 좌측(i-th)의 값과 동일
        max_width = V.size() - i; //너비 계산

        int min_sq = min(max_width, min_height);
        if(square > min_sq) return square; //너비, 높이 중 최솟값과 square 변수 비교. square가 더 크면 이 값이 최대이므로 반환
        square = min_sq; //square 값 갱신
    }

    return square;
}

int main(void) {
    int N;
    cin >> N;
    for(int n = 0; n < N; n++) {
        int K;
        cin >> K;
        vector<int> V;
        for(int i = 0; i < K; i++) {
            int temp;
            cin >> temp;
            V.push_back(temp);
        }
        cout << solution(V) << endl;
    }
}

B1. Character Swap (Easy Version)

문제 요약

같은 길이의 두 문자열 중 각각 한 글자씩 스왑하여 동일한 문자열을 만들 수 있는지 검사하는 문제이다.

 

접근 방법

두 글자만 서로 다르고 나머지 n-2글자의 글자들이 같은 위치에서 서로 같다면 비트 연산이 좋을 것이라 생각했고,

다른 곳이 세 군데 이상이면 더 계산하지 않고 틀린 답으로 간주하도록 하였다.

 

시간복잡도

처음부터 끝까지 문자열들을 훑는 과정이 O(n)정도 소요되므로 총 O(n) 이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool solution(int N, char* A, char* B) {
    vector<int> cmp;

    for(int i = 0; i < N; i++) {
        if((A[i] ^ B[i]) != 0) {
            cmp.push_back(i);
            if(cmp.size() > 2) return false;
        }
    }

    if(cmp.size() == 2 && A[cmp[0]] == A[cmp[1]] && B[cmp[0]] == B[cmp[1]]) return true;
    return false;
}

int main(void) {
    int N;
    scanf("%d", &N);
    for(int n = 0; n < N; n++) {
        int K;
        char A[10001];
        char B[10001];
        scanf("%d %s %s", &K, A, B);

        if(solution(K, A, B)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        
    }
}

 

총평

뒤로 갈수록 어려운 문제들이 있었다.

전역까지 열심히 공부해야지..