Codeforces Round #607 (Div. 2)

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

 

A. Suffix Three

문제 요약

문장의 접미사를 체크하여 어느 나라 언어인지 출력하는 문제이다.

 

접근 방법

string을 reverse한 후 맨 앞에서부터 차례대로 체크하면 해결될 것 같았다.

 

시간복잡도

계산하기 복잡하지만, std::reverse 가 O(n)이라고 가정하고(O(1)이라는 이야기도 있지만 어떻게 구현되었는지 몰라 O(n)이라고 두자..) std::string::find도 아래의 코드 상에선 O(n)보다는 작을 것이라 생각하면(무조건 접미사가 일치할 것이라고 문제에서 주어졌으므로) O(n) 정도 될 것 같다.

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

void solution(string& s) {
    reverse(s.begin(), s.end());
    if(s.find("op", 0) == 0) {
        cout << "FILIPINO" << endl;
    } else if(s.find("used", 0) == 0 || s.find("usam", 0) == 0) {
        cout << "JAPANESE" << endl;
    } else if(s.find("adinm", 0) == 0) {
        cout << "KOREAN" << endl;
    }
}

int main(void) {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;
        solution(s);
    }
    return 0;
}

 

B. Azamon Web Services

문제 요약

두 문자열이 주어질 때, 앞의 문자열 중 두 문자를 swap하면, 뒤의 문자열보다 사전순으로 더 앞에 있을 수 있는가에 관한 문제이다.

 

접근 방법

처음에 간단한 문제처럼 보여 간단하게 코드를 작성하였는데, 계속 틀린 부분이 발생하여 결국 Editorial을 읽어보았다. 정렬을 시켜 확인한다는 부분을 보고 코드를 다시 작성해 보았고, 예시 코드를 보니 비스무리하게 푼 것 같다.

시간복잡도

O(|S|log|S|)라고 하네..

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

using namespace std;

void solution(string& s, string& c) {
    string s2 = s;
    for(int i = s.size() - 2; i >= 0; i--) { //[i, s.size()) 사이에서 최소값을 s2[i]에 넣음
        s2[i] = min(s2[i], s2[i+1]);
    }
    for(int i = 0; i < s.size(); i++) {
        if(s[i] != s2[i]) {
            int j;
            for(j = i; j < s.size()-1; j++) {
                if(s2[j] != s2[j+1]) break;
            }
            
            //swap
            char temp = s[j];
            s[j] = s[i];
            s[i] = temp;
            break;
        }
    }
    if(s.compare(c) < 0) { //사전 순으로 앞에 있으면 출력
        cout << s << endl;
    } else {
        cout << "---" << endl;
    }
}

int main(void) {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        string s, c;
        cin >> s >> c;
        solution(s, c);
    }
}

 

총평

지난 휴가 때 리액트만 하느라 알고리즘 문제를 풀지 않아서 2문제 밖에 해결하지 못했다. C번 문제도 어떻게 푸는지는 대충 알겠는데 도저히 구현을 할 수가 없어서 포기했다. 시간 나면 확인해 봐야겠다.