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번 꺼냄

djm03178   1년 전

25억이라는 개수가 아주 단순한 연산으로 구성된 거라면 4초 안에 실행되는 것이 이상하지는 않은 것 같습니다.

코드가 비공개 상태인데, 공개해주시면 테스트해드릴 수 있을 것 같습니다.

wgwjh05169   1년 전

공개로 변경했습니다. 보이시나요?

djm03178   1년 전

아니요. 아직 비공개 상태인 것 같습니다.

공개 상태라면 저에게 아래의 제출처럼 언어 이름에 링크가 보여야 합니다.

preview

wgwjh05169   1년 전

맞으면 공개에서 공개로 바꿨는데 보이시나요??

아직 안 보이시면 아래 소스 보시면 될 것 같습니다.

한 달 전에 푼 거라 헷갈렸는데 누적합 배열이 아니라 빼기 요청마다 사탕 개수를 더해 가며 등수를 새로 구하는 풀이입니다.

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;
    }
}

djm03178   1년 전

설정에서 바꾸시는 게 아니라 (이건 앞으로 제출할 코드들에 대한 "기본값"을 설정하는 것입니다), 코드 개별적으로 공개 설정을 하셔야 합니다. https://www.acmicpc.net/source... 에 들어가셔서 하단에 있는 비공개를 공개로 바꿔주시면 됩니다.

djm03178   1년 전

아무튼 올려주신 코드는 TreeSet을 순회하는 코드라 절대 가벼운 연산이 아니네요. 실제로 돌려봤을 때 거의 1분이 걸리는 것을 확인했습니다.

wgwjh05169   1년 전

덕분에 공개로 바꾸었습니다! 감사합니다.

시간 확인해 볼 생각은 못 했는데 대신 확인해주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.