초급반 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)
입력을 받으면서, 아래를 처리해봅시다.
- 이미 나왔던 사람이라면, 무시한다. (set으로 중복 체크)
- 장소를 정수로 변환한다. (map<string, int>를 사용)
- 이 때, 처음 보는 장소가 나왔다면 새로운 값을 넣어야 한다.
- 그 장소에서 사진을 찍고 싶은 사람을 추가한다. (누적합을 사용, [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;
}