초급반 7주차 풀이 - STL, Greedy

1. [8958] OX퀴즈 (Bronze II)

문자열을 한 글자씩 읽으면서

O가 나올 때마다 점수에 1씩 더하고, X가 나올 때마다 점수를 0으로 초기화시켜주면 됩니다.

최종 점수는 각 글자에서 얻는 점수의 합이 됩니다.

void Main(){
	int t; cin >> t; while (t--){
		string s; cin >> s;
		int ans = 0, com = 0;
		for (char ch : s){
			if (ch == 'O'){ com += 1; } else{ com = 0; }
			ans += com;
		}
		cout << ans << endl;
	}
}

2. [7785] 회사에 있는 사람 (Silver V)

들어올 때마다 셋에 넣고 나갈 때마다 셋에서 빼주면 됩니다.

사전순의 역순 출력은 set의 reverse_iterator를 사용해서 출력해줄 수도 있습니다.

set<string> st;

void Main(){
	int q; cin >> q; while (q--){
		string x, s; cin >> x >> s;
		if (s == "enter"){ st.insert(x); } else{ st.erase(x); }
	}
	for (auto it = st.rbegin(); it != st.rend(); it++){ cout << *it << endl; }
}

3. [9733] 꿀벌 (Silver V)

그냥 각 문자열의 등장 횟수를 map으로 저장하면 됩니다. 그리고 예쁘게 출력해주면 됩니다.

문제 입력 특성상 EOF가 나올 때까지 받아야 하는데, 이는 while문의 조건 안에 cin을 넣어주면 됩니다.

map<string, int> cvt;
string arr[10]; int cnt[10];

void Main(){
	cvt["Re"] = 1; arr[1] = "Re";
	cvt["Pt"] = 2; arr[2] = "Pt";
	cvt["Cc"] = 3; arr[3] = "Cc";
	cvt["Ea"] = 4; arr[4] = "Ea";
	cvt["Tb"] = 5; arr[5] = "Tb";
	cvt["Cm"] = 6; arr[6] = "Cm";
	cvt["Ex"] = 7; arr[7] = "Ex";
	int n = 0;
	string s; while (cin >> s){ cnt[ cvt[s] ] += 1; n += 1; }
	for (int i = 1; i <= 7; i++){
		cout << arr[i] << ' ' << cnt[i] << ' ' << (ld)cnt[i]/n << endl;
	}
	cout << "Total " << n << " 1.00";
}

4. [11279] 최대 힙 (Silver II)

STL priority_queue 연습 문제입니다.

pq.push(x); pq.empty(); pq.top(); pq.pop();을 할 수 있으면 됩니다.

void Main(){
	priority_queue<int> pq;
	int q; cin >> q; while (q--){
		int x; cin >> x;
		if (x != 0){ pq.push(x); }
		else{
			if (pq.empty()){ cout << 0 << endl; }
			else{ cout << pq.top() << endl; pq.pop(); }
		}
	}
}

5. [1927] 최소 힙 (Silver II)

STL priority_queue 연습 문제입니다.

pq.push(x); pq.empty(); pq.top(); pq.pop();을 할 수 있으면 됩니다.

void Main(){
	priority_queue< int, vector<int>, greater<int> > pq;
	int q; cin >> q; while (q--){
		int x; cin >> x;
		if (x != 0){ pq.push(x); }
		else{
			if (pq.empty()){ cout << 0 << endl; }
			else{ cout << pq.top() << endl; pq.pop(); }
		}
	}
}

6. [11399] ATM (Silver III)

총 대기 시간을 최소화해야 하니, 인출 시간이 짧은 사람부터 인출하도록 정렬해봅시다.

 

그렇게 한 뒤 \( i \)번째 사람이 돈을 인출하는데 걸리는 시간을 \( A_{i} \)라고 하면,

각 사람별로 기다리는 시간 + 인출하는 시간은 \( A_{1} = P_{1}, A_{2} = P_{1} + P_{2}, \cdots, A_{i} = \sum_{k=1}^{k=i} P_{i} \)라는, 누적합을 쓰기 좋은 형태의 식이 나오게 됩니다.

우리가 원하는 건 \( A_{1} + A_{2} + \cdots + A_{N} = \sum_{i=1}^{i=N} A_{i} \)니, 누적합으로 만든 \( A \)에 누적합을 또 때려서 답을 구할 수 있습니다.

int arr[1020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	for (int i = 1; i <= n; i++){ arr[i] += arr[i-1]; }
	for (int i = 1; i <= n; i++){ arr[i] += arr[i-1]; }
	cout << arr[n];
}

7. [2941] 크로아티아 알파벳 (Silver V)

크로아티아 문자가 등장할 때마다 그 부분을 한 글자로 치고 넘어가줘야 합니다.

이 크로아티아 문자를 "제대로" 판별하는 게 생각보다 어려움에 주의하세요.

void Main(){
	string s; cin >> s; int sl = s.size();
	int cnt = 0;
	int i = 0; while (i < sl){ cnt += 1;
		if (i+1 < sl && s[i] == 'c' && s[i+1] == '='){ i += 2; }
		else if (i+1 < sl && s[i] == 'c' && s[i+1] == '-'){ i += 2; }
		else if (i+2 < sl && s[i] == 'd' && s[i+1] == 'z' && s[i+2] == '='){ i += 3; }
		else if (i+1 < sl && s[i] == 'd' && s[i+1] == '-'){ i += 2; }
		else if (i+1 < sl && s[i] == 'l' && s[i+1] == 'j'){ i += 2; }
		else if (i+1 < sl && s[i] == 'n' && s[i+1] == 'j'){ i += 2; }
		else if (i+1 < sl && s[i] == 's' && s[i+1] == '='){ i += 2; }
		else if (i+1 < sl && s[i] == 'z' && s[i+1] == '='){ i += 2; }
		else{ i += 1; }
	}
	cout << cnt;
}

8. [1302] 베스트셀러 (Silver IV)

입력받은 리스트를 정렬해봅시다. 그럼 동일한 문자열들이 붙어서 나오게 됩니다.

그럼 어떤 문자열의 등장 횟수를 비교하면서 최대 등장 횟수를 찾는 일만 남았는데,

이는 그 문자열이 처음으로 등장하는 위치와 마지막으로 등장하는 위치를 알고 있다면 간단히 계산할 수 있습니다.

string arr[1020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	string mx = ""; int mxc = 0;
	int st = 1; while (st <= n){
		int ed = st; while (ed <= n){
			if (arr[ed] == arr[st]){ ed += 1; }
			else{ break; }
		}
		if (mxc < ed-st){ mx = arr[st]; mxc = ed-st; }
		st = ed;
	}
	cout << mx;
}

9. [23349] 졸업 사진 (Silver I)

입력을 받으면서, 아래를 처리해봅시다.

1. 이미 나왔던 사람이라면, 무시한다. (set으로 중복 체크)
2. 장소를 정수로 변환한다. (map<string, int>를 사용)
   • 이 때, 처음 보는 장소가 나왔다면 새로운 값을 넣어야 한다.
3. 그 장소에서 사진을 찍고 싶은 사람을 추가한다. (누적합을 사용, [st, ed) 구간에 1을 더해준다.)

이러면 남은 건 그냥 가장 많은 사람 수 찾기가 되고, 이는 그냥 다 돌려보면서 구하면 됩니다.

그 뒤로는 그 많은 사람 수의 위치를 찾아야 하는데, 이는 "8. [1302] 베스트셀러"에서 찾던 방식과 비슷하게 해주면 됩니다.

set<string> chk;
map<string, int> cvt; map<int, string> tvc; int cc = 0;
const int M = 50000; int prf[12][50020];

void Main(){
	int n; cin >> n; while (n--){
		string nam, pos; int st, ed; cin >> nam >> pos >> st >> ed;
		if (chk.count(nam)){ continue; } chk.insert(nam);
		if (!cvt.count(pos)){ cc += 1; cvt[pos] = cc; tvc[cc] = pos; }
		int idx = cvt[pos];
		prf[idx][st] += 1; prf[idx][ed] -= 1;
	}
	for (int i = 1; i <= cc; i++){
		for (int j = 1; j <= M; j++){ prf[i][j] += prf[i][j-1]; }
	}
	string mx = ""; int mxc = 0;
	for (int i = 1; i <= cc; i++){
		string s = tvc[i]; int res = 0;
		for (int j = 1; j <= M; j++){ res = max(res, prf[i][j]); }
		if (mkp(res, mx) > mkp(mxc, s)){ mx = s; mxc = res; }
	}
	int idx = cvt[mx]; int cnt = 0; pi2 ans = {0, 0};
	int st = 0; while (st <= M){
		int ed = st; while (ed <= M){
			if (prf[idx][ed] == prf[idx][st]){ ed += 1; }
			else{ break; }
		}
		if (cnt < prf[idx][st]){ cnt = prf[idx][st]; ans = {st, ed}; }
		st = ed;
	}
	cout << mx << ' ' << ans.fr << ' ' << ans.sc;
}

10. [2751] 수 정렬하기 2 (Silver V)

std::sort 연습 문제입니다.

범위가 [st, ed)이기 때문에 끝 부분에서 한 칸을 더 가야 함에 주의하세요.

int arr[1000020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	for (int i = 1; i <= n; i++){ cout << arr[i] << endl; }
}

11. [2075] N번째 큰 수 (Silver I)

사실 이게 별해가 아닐까 싶긴 한데...

그냥 \( N^2 \)개의 수를 다 입력받고 신나게 정렬해주면 됩니다.

int arr[2310420];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n*n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n*n+1, [](int a, int b){ return a > b; });
	cout << arr[n];
}

현재 상태에서 가장 큰 수는 각 열의 맨 아래에 있는 수임을 사용하는 방법도 있습니다.

pq를 사용해서 1번째 큰 수부터 하나씩 빼고 바로 위에 있는 수들을 새로 후보로 넣어주면서

N번째 큰 수를 찾아주면 됩니다.

int arr[1520][1520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	priority_queue<pi3> pq;
	for (int i = 1; i <= n; i++){ pq.push({ arr[n][i], {n, i} }); }
	for (int i = 1; i <= n; i++){
		int val = pq.top().fr;
		int y = pq.top().sc.fr, x = pq.top().sc.sc;
		if (i == n){ cout << val; return; }
		pq.pop(); pq.push({ arr[y-1][x], {y-1, x} });
	}
}

pq를 쓰지 않고 그냥 나이브하게 최댓값을 찾아줘도 됩니다.

int arr[1520][1520];
int ptr[1520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	for (int i = 1; i <= n; i++){ ptr[i] = n; }
	for (int i = 1; i <= n; i++){
		int mx = -2e9, mxp = 0;
		for (int j = 1; j <= n; j++){
			int val = arr[ ptr[j] ][j];
			if (val > mx){ mx = val; mxp = j; }
		}
		if (i == n){ cout << mx; return; }
		ptr[mxp] -= 1;
	}
}

12. [1026] 보물 (Silver IV)

직관적으로 생각해보면, 오름차순 * 오름차순 또는 오름차순 * 내림차순입니다.

N = 2일 때로 비교해보면, 오름차순 * 내림차순이 더 적절해 보이죠.

그리고 실제로 그게 맞습니다.

 

\( A_1 < A_2 \)이고 \( B_1 < B_2 \)라면, \( (A_2 - A_1)(B_2 - B_1) > 0 \)이고,

\( A_2B_2 - A_2B_1 - A_1B_2 + A_1B_1 > 0 \)이니 \( A_2B_2 + A_1B_1 > A_2B_1 + A_1B_2 \)라는 식이 나오게 됩니다.

위 식이 말하는 건, 오름/내림이 안 맞는 두 원소가 있다면 이를 맞춰주는 게 더 최적임을 의미합니다.

int arr[60], brr[60];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ cin >> brr[i]; }
	sort(arr+1, arr+n+1); sort(brr+1, brr+n+1, [](int a, int b){ return a > b; });
	int ans = 0;
	for (int i = 1; i <= n; i++){ ans += arr[i]*brr[i]; }
	cout << ans;
}