Codeforces Round 944 (Div. 4)

https://codeforces.com/contest/1971

Dashboard - Codeforces Round 944 (Div. 4) - Codeforces

 

일단 ABC 3솔입니다...

D는 솔직히 할만했는데 피곤해서 잘못된 알고리즘을 세워서 틀렸습니다.

---

A. My First Sorting Problem

테스트케이스마다 a, b를 입력받고 두 값 중 작은 값과 큰 값을 순서대로 출력하는 문제입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	int t; cin>>t;
	while(t--){
		int a, b; cin>>a>>b;
		cout<<min(a,b)<<' '<<max(a,b)<<'\n';
	}
	return 0;
}

 

B. Different String

문자열을 입력받고, 문자열을 섞어서 기존과 다른 문자열을 만들 수 있는지 묻는 문제입니다.

만들 수 없다면 NO를, 만들 수 있다면 YES와 만들어진 문자열을 출력해야 합니다.

 

기존과 다른 문자열이 만들어지지 않는 경우는 한 문자로만 구성된 문자열일 경우입니다.

처음에는 중복 제거를 하려고 했는데, 이 작업 구현이 굉장히 귀찮을 것 같아서 Sort로 해결했습니다.

입력된 문자열 S를 Sort한 문자열 Tmp1과 Sort 후 Reverse한 문자열 Tmp2가 있다고 가정합니다.

S가 Tmp1, Tmp2와 같으면 NO를, 아니면 때에 따라 Tmp1이나 Tmp2를 출력하도록 했습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	int t; cin>>t;
	while(t--){
		string x; cin>>x;
		string tmp1,tmp2;
		tmp1=x;
		sort(tmp1.begin(),tmp1.end());
		tmp2=x;
		sort(tmp2.begin(),tmp2.end());
		reverse(tmp2.begin(),tmp2.end());
		if(x==tmp1 && x==tmp2) cout<<"NO\n";
		else{
			cout<<"YES\n";
			if(x!=tmp1) cout<<tmp1<<'\n';
			else if(x!=tmp2) cout<<tmp2<<'\n';
		}
	}
	return 0;
}

 

C. Clock and Strings

1 ~ 12로 라벨링된 시계가 있을 때, 4개의 점을 골라 실을 묶는다고 할 때, 실들이 교차하는지를 묻는 문제입니다.

 

테스트케이스마다 입력 a, b, c, d가 주어질 때, a와 b를 잇는 선을 a - b라고 정의했습니다.

a - b는 고정시켜두고, c와 d의 위치를 파악합니다.

a - b를 기준으로 시계는 두 개로 쪼갤 수 있습니다.

c와 d의 위치가 두 곳 중 한 곳에 몰려있다면 교차하지 않는 것이고, 아니라면 교차하는 것입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	int t; cin>>t;
	while(t--){
		int a,b,c,d; cin>>a>>b>>c>>d;
		int aa,bb,cc,dd;
		aa=min(a,b); bb=max(a,b);
		cc=min(c,d); dd=max(c,d);
		vector<int> tmp;
		int cnt=0;
		for(int i=aa+1;i<=bb-1;i++){
			tmp.push_back(i);
		}
		for(int x : tmp){
			if(x==cc || x==dd) cnt++;
		}
		if(cnt==0 || cnt==2) cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}

 

D. Binary Cut

0과 1로 구성된 문자열이 입력됩니다.

문자열을 쪼개서 오름차순으로 정렬시킬 때, 최소 몇 개로 쪼개야 하는지 묻는 문제입니다. 

 

대회 때는 str을 돌면서 이전 값과 같거나 01이 나오면 건너뛰고, 10이 나오면 cnt++로 문자열을 잘랐습니다.

이때 문제는 01이 나오는 경우에 건너뛰는 것입니다.

하지만 그럴 경우 01이 여러 개가 나온다면 정렬이 불가능해집니다.

ex) 01 | 01 | 01 | 01

 

대회 때 이것을 떠올렸어야 했는데 끝나고 잠깐 누우니까 바로 떠올랐습니다...

알고리즘을 수정해야 합니다.

prev와 cur이 같을 경우에만 continue를 하고, 다를 경우에는 항상 cnt++로 문자열을 잘라줍니다.

그리고 01은 한 번만 카운트하여서 cnt - (01 유무) 를 출력해줍니다.

 

이렇게 하면 올바른 출력을 얻을 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while(t--){
        string str; cin>>str;
        int cnt=1; //초기에 한 덩어리라고 정의
        int flag=0; //01이 존재하는가?
        char prev=str[0];
        for(int i=1;i<str.size();i++){
            if(str[i]==str[i-1]) continue; //같다면 넘어감
            if(str[i]!=str[i-1]) cnt++; //다르다면 자름
            if(str[i-1]=='0' && str[i]=='1') flag=1; //다르더라도 01은 그대로 사용가능함
        }
        cout<<cnt-flag<<'\n';
    }
    return 0;
}