[210718] 가희와 함께 하는 2회 코딩테스트 후기

푹 쉴까 아니면 코테를 응시할까 고민하다가 au0504님이 3시쯤에 코테를 응시한다길래 나도 한 번 응시해본 대회이다.

https://www.acmicpc.net/contest/view/658

가희와 함께 하는 2회 코딩 테스트

+) 1회 코딩테스트 후기는 아래 주소에서 볼 수 있다.

https://kth990303.tistory.com/66

[210523] 가희와 함께하는 1회 코딩테스트 후기

뒤늦게 응시한 대회인데도 5등을 하신 아루님이 정말 대단한 듯하다.

이번 대회 역시 구현, 문자열파싱 위주로 나왔는데

구현쪽 위주이다보니 이쪽 파트가 약한 나로서는 탈탈 털리게 된 대회였다. 하지만 덕분에 배울 점도 굉장히 많았던 대회.

 

간단하게 후기를 남겨보겠다.

---

A. 가희와 파일 탐색기

22232번: 가희와 파일 탐색기

처음에는 map을 이용해 파일 확장자를 쓸 수 있는지의 여부를 cmp함수에서 체크하였다.

그러나 cmp함수에서 VS환경에선 이유를 알 수 없는 런타임에러를 발생시켜 힘들었던 문제.

ideone에선 잘 돌아가서 제출하였지만 30%에서 TLE 또는 WA를 겪어 결국 해결하지 못한 문제이다.

 

아래는 내가 작성한 질문글이다. 이 글에서 런타임에러가 뜬 코드 또한 볼 수 있다.

https://www.acmicpc.net/board/view/71494

글 읽기 - VS에선 컴파일에러(X) 런타임에러(O), ideone에선 돌아가는 이유?

 

이 문제로부터 얻은 교훈은 3개.

1. cmp함수에서 비교 외의 다른 로직은 최대한 지양하자.
2. 비교할 대상이 많은 경우 struct로 따로 묶어서 비교해주자
3. string(문자열)끼리도 lower_bound, upper_bound 비교가 가능하며, 동일한 문자열이 없음에도 불구하고, 앞부분만 겹치면 그 인덱스를 리턴해주므로 주의하자

따라서 아래와 같이 코드를 바꾸었고, 대회가 끝난 후에 업솔빙으로 AC를 받았다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 200001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M;
set<string> S;
vector<string> v;
struct Point {
	string name, flag;
	bool used = false;
};
vector<Point> p;
bool cmp(Point p1, Point p2) {
	if (p1.name == p2.name) {
		if (p1.used == p2.used)
			return p1.flag < p2.flag;
		return p1.used > p2.used;
	}
	return p1.name < p2.name;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	p.resize(N);
	v.resize(M);
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		int idx = s.find('.');
		p[i].name = s.substr(0, idx);
		p[i].flag = s.substr(idx + 1);
	}
	for (int i = 0; i < M; i++) {
		cin >> v[i];
	}
	sort(all(v));
	for (int i = 0; i < N; i++) {
		int idx = lower_bound(all(v), p[i].flag) - v.begin();
		if (idx < v.size() && v[idx] == p[i].flag)
			p[i].used = true;
	}
	sort(all(p), cmp);
	for (auto i : p) {
		cout << i.name << "." << i.flag << "\n";
	}
}

---

B. 가희와 키워드

22233번: 가희와 키워드

 

string의 find기능에서 ,가 여러개여도 결국 맨 첫번째 인덱스를 리턴해주어 어떻게 할지 고민했다.

그런데 string의 find기능에 find(char ch, int idx)와 같이 인자를 두개 작성할 경우, idx번째 이후의 ch 인덱스를 리턴해준다는 사실을 알게 돼 find로 문제를 풀 수 있었다.

처음에는 map으로 접근했다가 TLE를 받았다.

그런데 이 문제는 key, value와 같이 딕셔너리 형태로까지 저장할 필요가 없으므로 set을 써도 충분하며,

정렬조차 필요없고 O(1) 기능 (insert, erase 등)만 사용하므로 unordered_set 또한 사용가능하다.

이렇게 하면 map: TLE, set: 1276ms, unordered_set: 864ms 로 더 빠르게 해결할 수 있다.

그동안 unordered_set/map의 필요성을 못느꼈는데 확실히 정렬을 하지 않으니 시간단축이 된다는 장점이 있었다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 200001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M;
unordered_set<string> S;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		S.insert(s);
	}
	while (M--) {
		int i = 0;
		string s;
		cin >> s;
		while (i < s.length()) {
			string k;
			if (s.find(',', i) == string::npos)
				k = s.substr(i);
			else
				k = string(s.begin() + i, s.begin() + s.find(',', i));
			if (S.find(k) == S.end()) {
				i += k.length() + 1;
				continue;
			}
			S.erase(k);
			i += k.length() + 1;
		}
		cout << S.size() << "\n";
	}
}

---

C. 가희와 은행

22234번: 가희와 은행

queue와 priority_queue를 적절히 이용하여 시뮬레이션하는 문제.

은행 업무 시작 전 손님들은 먼저 queue에 넣어 줄서게 하고,

시작 후 손님들은 온 시간에 따라 priority_queue에 넣어, 시간이 되면 대기열 queue에 집어넣어준다.

문제 조건에 queue가 비는 순간은 존재하지 않는다 돼있으므로 예외처리 없이 수월하게 시뮬레이션을 하여 풀 수 있다.

주의할 점은 아래 부분이다.

• 그렇지 않으면 대기 큐의 맨 뒤로 이동하게 됩니다. 만약에 이 때 도착한 손님이 있다면, 도착한 손님 뒤로 가게 됩니다.

이 때 우선 순서를 생각해 실수없이 잘 구현하도록 하자.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> pii;
const int MAX = 100001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, T, W, M;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> T >> W;
	queue<pi> q;
	for (int i = 0; i < N; i++) {
		int id, t;
		cin >> id >> t;
		q.push({ id, t });
	}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int id, t, t2;
		cin >> id >> t >> t2;
		pq.push({ t2, {id, t} });
	}
	int i = 0;
	while (i < W) {
		int cur = q.front().first;
		int time = q.front().second;
		q.pop();
		for (int j = 0; j < min(T, time); j++) {
			if (i >= W)
				break;
			cout << cur << "\n";
			i++;
		}
		if (i >= W)
			break;
		while (!pq.empty() && pq.top().first <= i) {
			q.push({ pq.top().second.first, pq.top().second.second});
			pq.pop();
		}
		if (time > T)
			q.push({ cur, time - T });
	}
}

---

D. 가희와 btd5

22238번: 가희와 btd5

개인적으로 문제 조건을 잘못 판단할 확률이 높다고 생각하는 문제.

또한, 이유는 모르겠지만 대회에선 4번이었는데, 문제 공개 때 7번으로 옮겨진 문제이다.

 

문제 중 아래와 같은 조건이 있다.

• 초기 상태에 Darting Gun Tower가 특정 방향으로 데미지가 1e9 이상의 공격을 했을 때, 모든 풍선을 제거할 수 있는 방법이 존재합니다. 

이 조건이 나중에 알고보니 풍선이 일직선 상에 존재한다는 조건이었다는데,

난 풍선이 일직선이 아닌 무작위로 여러 방향에 있고, 1e9 이상의 데미지로 공격할 경우 예외적으로 모든 풍선을 제거한다는 소리인 줄 알았다.

 

다만, 잘 생각해보면 위 조건은 포탑 공격방향에 해당하는 모든 풍선을 제거할 수 있다는 소리이므로 모든 풍선은 일직선 내에 존재한다는 뜻임을 알 수 있다. 다만, 위처럼 오해할 수도 있을 듯하여 지문이 썩 맘에 들진 않는다.

 

이 문제 또한 대회가 끝난 후에 해결했다. 대회 전에는 문제를 오해하여 틀린 코드를 계속 제출하였다. (그런데 나중에 알고보니 오해하지 않았어도 실수 오차때문에 어차피 틀린 코드를 제출했을 듯하다.)

 

여러 포탑의 체력을 깎고 관리할 때 이중for문으로 O(N^2) TLE 코드를 작성하지 않도록 주의하자.

또한, 포탑 방향을 기울기로 접근하여 double 형태로 넣는다면 큰 수를 큰 수로 나눌 때 임의정밀도 부분에서 실수오차가 무시될 수 있다. 아래 예시 때문이다.

1 2
999999999 1000000000 10
999999998 999999999 20
999999997 999999998 30

ans
1
1

만약 61%에서 틀린다면 위 예제 결과값이 0 0이 나올 확률이 높다.

애초에 실수를 나누는 작업을 지양해야 하므로 기울기 y/x 조건이 아닌 x/=gcd, y/=gcd를 하여 x, y가 같은지 비교해주는 작업을 거치도록 해주자. 이 때, gcd는 abs(x), abs(y)와의 gcd를 구해야 함에 주의하자.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, double> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> pii;
const int MAX = 200001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M, cnt;
ll D;
vector<pii> v;
int gcd(int a, int b){
	int r=a%b;
	if(!r) return b;
	return gcd(b, r);
}
bool cmp(pii p1, pii p2) {
	return p1.first < p2.first;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x, y, hp;
		cin >> x >> y >> hp;
		if (!x && y > 0)
			v.push_back({ hp, {0, 1} });
		else if (!x && y < 0)
			v.push_back({ hp , {0, -1} });
		else if (!y && x > 0)
			v.push_back({ hp, {1, 0} });
		else if (!y && x < 0)
			v.push_back({ hp, {-1, 0} });
		else{
			int r=gcd(abs(x), abs(y));
			v.push_back({ hp, {x/r, y/r} });
		}
	}
	sort(all(v));
	for (int i = 0; i < M; i++) {
		int x, y;
		ll d;
		cin >> x >> y >> d;
		if (!N) {
			cout << 0 << "\n";
			continue;
		}
		if (!x && !y) {
			cout << N << "\n";
			continue;
		}
		else if (!x && y > 0)
			y=1;
		else if (!x && y < 0)
			y=-1;
		else if (!y && x > 0)
			x=1;
		else if (!y && x < 0)
			x=-1;
		else{
			int r=gcd(abs(x), abs(y));
			x/=r;
			y/=r;
		}
		if (v[0].second.first != x || v[0].second.second!=y) {
			cout << N << "\n";
			continue;
		}
		D += d;
		int idx = upper_bound(all(v), pii(D, pi(x, y)), cmp) - v.begin();
		N -= (idx - cnt);
		cnt = idx;
		cout << N << "\n";
	}
}

---

UpSolving

F. 가희와 비행기

22236번: 가희와 비행기

뒷번호에 갑자기 점화식이 잘 보이는 dp문제가 보여 김이 좀 빠지는 감이 있었다.

dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] (i: index, j: 현재 고도)의 점화식을 세워 쉽게 해결할 수 있다.

 

정해는 카탈란 수라는데, 문제를 풀 때 카탈란 수를 생각조차 하지 않았고, dp 점화식이 쉽게 도출돼 좀 당황했던 문제.

대회가 끝난 후에 풀어서 그럴 수도 있겠다.

 

카탈란 수인 이유도 후에 생각해보았는데, 고도가 0 이하로 중간에 절대 갈 수 없기 때문에 괄호쌍 문제와 굉장히 비슷해진다. 만약 점화식을 세우기 많이 까다로운 카탈란 수 문제라 하면 G3이 가장 적당한 티어가 아닐까 싶다.

#include <iostream>
#include <algorithm>
#include <cstring>
const int MAX=4001;
typedef long long ll;
using namespace std;
ll D, M, d[MAX][MAX];
ll dp(int cur, int dis){
	if(cur && cur<D && dis<=0)
	    return 0;
	if(cur==D)
	    return !dis?1:0;
	ll&ret=d[cur][dis];
	if(ret!=-1)
	    return ret;
	ret=0;
	ret+=dp(cur+1, dis+1)+dp(cur+1, dis-1);
	return ret%M;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin>>D>>M;
	memset(d, -1, sizeof(d));
	cout<<dp(0, 0)<<"\n";
}

---

일단 문제들이 꽤 재밌었다.

그리고 아주 탈탈 털렸다. 그러나 탈탈 털린 만큼 얻은 점도 많았다.

가희 코테의 특징이 구현 위주의 문제이다보니 다른 분들의 코드를 보면서 어떻게 더 속도를 빠르게 할 수 있을지, 어떻게 더 생산성을 높일지, 어떤 부분에서 틀리는지를 고민하면서 많이 배웠던 대회였다.