16221번 모독
이왜틀?
예전에 하스스톤 해 본 사람은 다 아는 모독 각.
매 케이스 마다 모독으로 죽는 하수인이 몇 개인지 출력하는 문제다.
모독이 무엇인가?
카드를 확인해보도록 하자.
5년 전 답안을 볼까?
int q=Integer.parseInt(br.readLine());
int[] arr=new int[q+1];
for(int i=0;i<q;i++) {
StringTokenizer st=new StringTokenizer(br.readLine()," ");
int t=Integer.parseInt(st.nextToken());
int k=Integer.parseInt(st.nextToken());
if(t==1) arr[k]++;
else arr[k]--;
long c=0;
for(int j=1;j<=q;j++) {
if(arr[j]>0) c+=arr[j];
else break;
}
bw.write(c+"\n");
}
심플한 접근, 심플한 시간초과
설계
Q와 K가 100만이다.
시간초과를 어떻게 피할 수 있을 것인가?
문제 분류가 세그먼트 트리라 아무 생각없이 구현했다가 시간초과에 걸렸다.
자바가 문제인가 해서 빠른 입출력을 직접 구현해도 시간초과 나는 걸 보고 로직 자체에 문제가 있다는 걸 알았다.
C++로 시간초과가 나지 않아야 Java로 건드릴 수나 있겠다 싶어서 언어 전환
극단적인 케이스에서 시뮬레이션을 돌리면 터질 수 밖에 없는 구조인데 어떻게 시간을 단축 시킬 것인가?
결국 펜윅트리 + 이진탐색으로 해결 봤다.
C++ 구현
1. 초기화
우선 C++로 구현한다.
update 함수는 펜윅트리에 값을 추가하거나 제거한다.
처음에 필드에 하수인이 없으므로 update 함수를 통해 트리를 초기화한다.
// 하수인
int minions_bit[1000001];
// 전장에 없는 체력
int absent_bit[1000001];
int check[1000001];
// BIT에 값 추가, 제거
void update(int bit[], int i, int n) {
while (i < 1000001) {
bit[i] += n;
i += i & -i;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 초기화
for (int i = 1; i < 1000001; i++) {
update(absent_bit, i, 1);
}
}
2. 하수인 상태 반영 및 구간합 계산
T에 따라서 하수인을 추가하거나 제거한다.
absent 트리는 check 배열을 통해 해당 하수인 존재 여부를 확인 후 업데이트 한다.
하수인 배치가 끝나면 모독각을 봐야한다.
이진탐색으로 전장에 없는 가장 작은 체력을 찾는다.
모독으로는 그 체력 아래까지 하수인이 전부 죽기 때문에 그 아래 체력까지의 하수인 수를 구해서 출력한다.
// 1~i까지 합
int bit_sum(int bit[], int i) {
int result = 0;
while (i > 0) {
result += bit[i];
i -= i & -i;
}
return result;
}
// ... 중략 ...
// 1이면 하수인 추가 2면 제거
if (T == 1) {
if (check[K]++ == 0) {
// 하수인 처음 추가될때만 제거
update(absent_bit, K, -1);
}
update(minions_bit, K, 1);
} else {
update(minions_bit, K, -1);
if (--check[K] == 0) {
// 하수인 마지막 제거될때만 추가
update(absent_bit, K, 1);
}
}
// 이진 탐색
int idx = 0;
int bitMask = 1 << 20;
int sum = 0;
while (bitMask) {
int t = idx + bitMask;
// 없는 체력이 있으면
if (t < 1000001 && sum + absent_bit[t] < 1) {
sum += absent_bit[t];
idx = t;
}
bitMask >>= 1;
}
// 실제 체력 보정
++idx;
cout << bit_sum(minions_bit, idx - 1) << '\n';
C++ 채점
아 뭐지 왜이렇게 문제 빡세지
이제 이대로 자바로 포팅해본다.
Java 구현
특별한 유틸을 쓴게 없기 때문에 간단하게 포팅할 수 있다.
빠른 입출력은 구현해둔게 있기 때문에 그대로 가져가서 쓴다.
// 빠른 입출력 구현
public static class InputReader {
private final InputStream in = System.in;
private final byte[] buf = new byte[1<<20];
private int ptr = 0;
private int buflen = 0;
int nextInt() throws IOException {
int c = 0;
int x = 0;
boolean negative = false;
while(true) {
c = read();
if (c > ' ') break;
}
if (c == '-') {
negative = true;
c = read();
}
while(c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c= read();
}
return negative ? -x : x;
}
private int read() throws IOException {
if (ptr >= buflen) {
buflen = in.read(buf);
ptr = 0;
if (buflen <= 0) {
return -1;
}
}
return buf[ptr++] & 0xFF;
}
}
Java 채점
드디어 성공
반성
바빠서 깨작깨작 만져서 그런가 집중도 제대로 못해서 그런지 상당히 까다로웠다
그냥 내가 못해서 시간초과난건데 이건 Java가 구려서 그래 하면서 애꿎은 Java 탓만 하고 있었네…
코드 확인