2020. 7. 5 에 쓴 글
1번 문제
https://www.acmicpc.net/problem/10797
[문제 요약]
첫번째 줄에 일의 자리 숫자가 1개 주어지고 두번째 줄에 일의 자리 숫자가 5개 주어질 때,
그 두번째로 받은 5개 숫자 중 처음 받은 1개의 숫자가 몇 개 들어갔는지 출력.
너무 쉬워서 풀이는 패스
2번 문제
https://www.acmicpc.net/problem/10798
[문제 요약]
5번째 줄 까지 string을 입력 받아서 그것을 세로로 읽은 것을 한 줄로 결과로 출력.
[코드]
#include <iostream>
#include <string>
using namespace std;
int main() {
string words[5];
for (int i = 0; i < 5; i++) {
cin >> words[i];
}
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 5; j++) {
if (words[j].length() > i) cout << words[j][i];
}
}
return 0;
}3번 문제
https://www.acmicpc.net/problem/10799
[문제 요약]
'(' 와 ')' 로 이루어진 string을 입력받는데 이것으로 쇠 막대기들의 위치와 길이, 레이저가 나오는 위치를 알 수 있다.
이때 레이저로 인해 잘려진 쇠 막대기 조각의 갯수를 구하라.
[풀이]
최종 쇠 막대기 조각의 갯수를 count라고 하고 괄호의 깊이를 depth라고 할 때,
count가 올라가는 경우는 레이져를 쏠 때(레이져를 맞은 막대기 수 만큼 플러스)와 막대기가 끝날 때(한 막대기 길이가 끝나면 + 1) 인 것을 알 수 있다.
parenthesis string을 처음부터 끝까지 순회하며,
'(' 이면, depth += 1
')' 이면, depth -= 1 하고
바로 앞이 ')' 일 경우(레이져를 쏘는 경우), count += depth
바로 앞이 '(' 일 경우(막대기가 끝나는 경우), count += 1[코드]
#include <iostream>
#include <string>
using namespace std;
int main() {
string p;
cin >> p;
int count = 0, depth = 0;
for (int i = 0; i < p.length(); i++) {
if (p[i] == '(') depth += 1;
else {
depth -= 1;
if (p[i - 1] == '(')
count += depth;
else
count += 1;
}
}
cout << count;
return 0;
}4번 문제
https://www.acmicpc.net/problem/10800
[문제 요약]
각 플레이어 마다 특정 색, 특정 크기의 공 하나를 가지고 있다.
각 플레이어들은 다른 플레이어의 공이 다음 특성을 모두 만족시키면 사로잡을 수 있다.
i) 내 공 크기 보다 작고
ii) 내 공 색깔과 다를때
각 플레이어들 공의 색깔과 크기가 주어졌을때, 각 플레이어들이 사로잡을 수 있는 공의 갯수를 출력하라.
[풀이]
모든 플레이어들을 순회하며 다른 모든 플레이어들과 비교하면 쉽게 풀리겠지만,
그렇게 하면 시간복잡도가 O(N^2)이 되기 때문에 이 문제에서 N의 최대 크기가 20만이여서 시간초과(TLE)가 난다.
O(NlogN) 풀이 :
플레이어들의 공 배열을 크기 순으로 정렬해서 순회하면 현재 탐색중인 공은 이전에 탐색했던 공보다 항상 크거나 같다는 점을 이용하여,
한 공을 탐색할때 다른 공들과 비교를 위해서 다른 모든 공을 탐색해야하는 시간낭비를 없앰.
그런데 size가 같은 공이 있어 문제가 까다로워지는데 stack을 이용하여 해결함.
변수 설명
count[n] : 각 color에 대한 현재까지의 공 크기 합.
all : 현재까지의 모든 공들의 크기 합.
result[n] : 출력할 결과. (각 player들이 사로잡을 수 있는 공의 갯수)
1. 각 player의 공에 대한 정보를 balls 벡터에 담아서 크기순으로 정렬
2. 크기가 작은 공부터 순회하며,
이전 공의 크기와 달라졌으면,
stack의 모든 ball들을 pop해서 count[]와 all에 반영
현재 공을 stack에 push
result[현재 공의 index] = all - count[현재 공의 컬러]- result 배열 출력
[코드]
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
typedef struct ball {
int idx, color, size;
bool operator<(const struct ball & x) {
return size < x.size;
}
} ball;
using namespace std;
int n, all, result[200000], counts[200000];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector<ball> balls;
stack<ball> st;
cin >> n;
for (int i = 0; i < n; i++) {
int c, s;
cin >> c >> s;
balls.push_back({ i, c - 1, s });
}
sort(balls.begin(), balls.end());
int prev = -1;
for (int i = 0; i < balls.size(); i++) {
if (prev != balls[i].size) {
while (!st.empty()) {
ball b = st.top(); st.pop();
counts[b.color] += b.size;
all += b.size;
}
}
result[balls[i].idx] = all - counts[balls[i].color];
st.push(balls[i]);
prev = balls[i].size;
}
for (int i = 0; i < n; i++) cout << result[i] << '\n';
return 0;
}