[랜덤 마라톤] Trading(11853)

1. 문제 풀이 아이디어

• 입력 값을 우선순위큐에 넣은 후 조건에 따라 스위핑 알고리즘을 사용하여 문제를 해결하려고 했으나 메모리 초과로 인해 해결하지 못하였다.

• 다른 풀이를 찾아보고 싶었으나 찾지 못해 결국 날짜가 지나버려 마라톤이 끝나 버렸다

• 질문글을 올려서 다른 사람의 도움을 받아봐야할 것 같다.

2. 나의 오답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int[] v = new int[n + 1];
        PriorityQueue<Input> pq = new PriorityQueue<>((o1, o2) -> o1.l - o2.l);
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int l = Integer.parseInt(stringTokenizer.nextToken());
            int r = Integer.parseInt(stringTokenizer.nextToken());
            int x = Integer.parseInt(stringTokenizer.nextToken());
            pq.add(new Input(l, r, x));
        }
        while (!pq.isEmpty()) {
            Input cur = pq.poll();
            List<Input> list = new ArrayList<>();
            while (!pq.isEmpty()) {
                Input next = pq.poll();
                if (cur.r < next.l) {
                    pq.add(next);
                    break;
                }
                if (next.l - cur.l + cur.x > next.x) {
                    next.x = next.x + cur.r - next.l + 1;
                    next.l = cur.r + 1;
                    if (next.l <= next.r)
                        list.add(next);
                } else {
                    if (cur.r <= next.r) {
                        cur.r = next.l - 1;
                    } else {
                        list.add(new Input(next.r + 1, cur.r, cur.x + next.r - cur.l + 1));
                        cur.r = next.l - 1;
                    }
                    list.add(next);
                }
            }
            for (int i = cur.l; i <= cur.r; i++) {
                v[i] = cur.x++;
            }
            pq.addAll(list);
        }
        for (int i = 1; i <= n; i++) {
            stringBuilder.append(v[i]).append(' ');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

class Input {
    int l;
    int r;
    int x;

    public Input(int l, int r, int x) {
        this.l = l;
        this.r = r;
        this.x = x;
    }
}