25억이라는 개수가 아주 단순한 연산으로 구성된 거라면 4초 안에 실행되는 것이 이상하지는 않은 것 같습니다.
코드가 비공개 상태인데, 공개해주시면 테스트해드릴 수 있을 것 같습니다.
2243번 - 사탕상자
공개로 변경했습니다. 보이시나요?
맞으면 공개에서 공개로 바꿨는데 보이시나요??
아직 안 보이시면 아래 소스 보시면 될 것 같습니다.
한 달 전에 푼 거라 헷갈렸는데 누적합 배열이 아니라 빼기 요청마다 사탕 개수를 더해 가며 등수를 새로 구하는 풀이입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static final int MAX_CANDY_SIZE = 1_000_000 + 1;
static final int POP = 1;
static final int ADD = 2;
// RB Tree로 구현되어 정렬된 상태를 유지하는 집합
static Set<Integer> existCandies = new TreeSet<>();
static int[] candies = new int[MAX_CANDY_SIZE + 1];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
candies = new int[MAX_CANDY_SIZE];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int op = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
if (op == POP) {
int id = findIdBy(target);
candies[id]--;
System.out.println(id);
}
if (op == ADD) {
int amount = Integer.parseInt(st.nextToken());
existCandies.add(target);
candies[target] += amount;
if (candies[target] == 0) {
existCandies.remove(target);
}
}
}
}
static int findIdBy(int rank) {
Iterator<Integer> iterator = existCandies.iterator();
int accumulateAmount = 0;
while (iterator.hasNext()) {
int candy = iterator.next();
accumulateAmount += candies[candy];
if (accumulateAmount >= rank) {
return candy;
}
}
return -1;
}
}설정에서 바꾸시는 게 아니라 (이건 앞으로 제출할 코드들에 대한 "기본값"을 설정하는 것입니다), 코드 개별적으로 공개 설정을 하셔야 합니다. https://www.acmicpc.net/source... 에 들어가셔서 하단에 있는 비공개를 공개로 바꿔주시면 됩니다.
덕분에 공개로 바꾸었습니다! 감사합니다.
시간 확인해 볼 생각은 못 했는데 대신 확인해주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
wgwjh05169 1년 전
정적 누적합을 사용한 풀이를 저격하는 테스트케이스가 없는 것 같습니다.
제출 번호: 91030543
위 풀이는 아래 테스트케이스에서 시간 비용이 25억인데 통과됩니다.
tc.in
tc.out
1. 1번 1개, 2번 1개, 3번 1개, ..., 49999번 1개, 50000번 50000개 이상 의 사탕을 넣음
2. 1번 이후 50,000등을 50,000번 꺼냄