글 읽기 - 반례 부탁드립니다...

changhoi0522 2년 전 0

반례찾기가 어렵네요... 한 55퍼에서 틀리는 것 같아요

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static List<List<int[]>> list = new ArrayList<>();
    static int[] arr;

    static int upperBound(int val) {
        int r = list.size();
        int l = 0;
        while (l < r) {
            int mid = (r + l) / 2;
            List<int[]> candidates = list.get(mid);
            if (val >= candidates.get(candidates.size() - 1)[0]) l = mid + 1;
            else r = mid;
        }

        return r;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
        List<int[]> zero = new ArrayList<>();
        zero.add(new int[]{arr[0], -1});
        list.add(zero);
        int top = 1;

        for (int i = 1; i < n; i++) {
            int val = arr[i];
            int idx = upperBound(val);
            if (idx == top) {
                List<int[]> added = new ArrayList<>();
                List<int[]> last = list.get(idx - 1);
                added.add(new int[]{val, last.size() - 1});
                list.add(added);
                top++;
            } else if (idx == 0) {
                list.get(idx).add(new int[]{val, -1});
            } else {
                List<int[]> last = list.get(idx - 1);
                list.get(idx).add(new int[]{val, last.size() - 1});
            }
        }

        System.out.println(list.size());
        StringBuilder sb = new StringBuilder();
        int[] head = list.get(list.size() - 1).get(0);
        sb.insert(0, " " + head[0]);
        int idx = head[1];
        for (int i = list.size() - 2; i >= 0; i--) {
            int[] target = list.get(i).get(idx);
            sb.insert(0, " " + target[0]);
            idx = target[1];
        }

        System.out.println(sb.toString().trim());
    }
}

tlsdydaud1 2년 전 1

같은 수에 대한 처리가 제대로 안 된 것 같습니다.
2

1 1

이런 입력을 넣었을 때

1 1
이렇게 출력되네요.

changhoi0522 2년 전 0

감사합니다 ㅠㅠ 그 부분 해결했더니 이후 시간초과가 생기네요 ㅎㅎ 다시 봐야겠습니다

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

문제

문제

출처

ICPC

반례 부탁드립니다...

changhoi0522 2년 전 0

tlsdydaud1 2년 전 1

changhoi0522 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말