글 읽기 - 1933번] 스카이라인 38% 출력초과

ruddks1001 3년 전 0

정말 정말 정말 모르겠습니다 ...

38%에서 출력초과라고 나오길래 StringBuilder 에서 공백도 지워보고

별 짓을 다해봤는데 안되네요...

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static ArrayList<long[]> queue ;
    public static void main(String[] args)throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        queue = new ArrayList<>();
        for(int i = 0 ; i < n ; i ++){
            String[] str = bf.readLine().split(" ");
            long l = Long.parseLong(str[0]);
            long height = Long.parseLong(str[1]);
            long r = Long.parseLong(str[2]);
            queue.add(new long[]{l,height});
            queue.add(new long[]{r,-height});
        }
        Collections.sort(queue, new Comparator<long[]>() {
            @Override
            public int compare(long[] o1, long[] o2) {
                if(o1[0] == o2[0])return (int)(o1[1] - o2[1]);
                return (int)(o1[0] - o2[0]);
            }
        });
        long maxHeight = 0;
        TreeMap<Long,Long> tmp = new TreeMap<>();
        TreeMap<Long,Long> answer = new TreeMap<>();
        for(long[] t : queue){
            // 시작점일경우
            if(t[1] > 0){
                tmp.put(t[1],tmp.getOrDefault(t[1],(long)0)+1);
                //갱신
                if(maxHeight < t[1]){
                    maxHeight = t[1];
                    answer.put(t[0],maxHeight);
                }
            }
            //끝점일경우
            else{
                long tmpH = t[1]*(-1);
                // 높이의 개수를 하나 줄인다.
                if(tmp.containsKey(tmpH)){
                    tmp.put(tmpH, tmp.get(tmpH) - 1);
                    // 0일경우 아에 삭제
                    if(tmp.get(tmpH) == 0){
                        tmp.remove(tmpH);
                    }
                    if(maxHeight == tmpH){
                        // 현재 지점에서 가장 높은 높이를 찾는다.(두번째로 높은)
                        if(!tmp.isEmpty()) {
                            long tmpKey = tmp.lastKey();
                            maxHeight = tmpKey;
                        }
                        else{
                            maxHeight = 0;
                        }
                        // 찾은 높이보다 현재 위치의 높이가 높다면 ( 끝점이므로 내려가는지점 만약 높이가 같다면 유지이므로 answer에 추가 x)
                        if(maxHeight < tmpH) {
                            answer.put(t[0], maxHeight);
                        }
                    }
                }
            }
        }
        // 정답 출력문
        StringBuilder sb = new StringBuilder();
        Set<Long> it = answer.keySet();
        for(Long k : it){
            long key = k;
            long value = answer.get(key);
            sb.append(key).append(" ").append(value).append(" ");
        }
        // 정말 혹시 몰라서 공백 하나 끝에있는거 지움
        sb.deleteCharAt(sb.length()-1);
        System.out.print(sb);

    }
}

jinhan814 3년 전 6

제가 자바를 로컬에서 돌려볼 수가 없어서 올바른 반례인지는 잘 모르겠는데 저는 아래 두 케이스를 고려해주니까 AC받았어요

1. 같은 위치에 건물이 여러 개가 있는 경우 -> 가장 큰 건물 하나만 고려해야 o

1 1 2

1 2 2

2. 건물이 겹쳐서 있는 경우 -> 붙어있는 부분은 출력하면 x

1 1 2

2 1 3

ruddks1001 3년 전 1

앗 이 글 올리고 좀 더 고민하다가 결국 강의듣고 해결 했습니다 ㅠㅠ 정말정말 감사합니다!

noname2048 1년 전 0

@ruddks1001 님 감사합니다. 저도 같은 문제로 해매고 있었네요 :P
@jinhan814 님 고맙습니다. 1번 해결하고 왜 안되지 하다가 글보고 2번을 놓쳤음을 알았네요 큰 도움 되었습니다. :)
감사합니다.

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

문제

문제

출처

ICPC

1933번] 스카이라인 38% 출력초과

ruddks1001 3년 전 0

jinhan814 3년 전 6

ruddks1001 3년 전 1

noname2048 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말