글 읽기 - n^2 이 아닌 nlogn으로 해결해보려하는데...

ckdrb7067 2년 전 0

안녕하세요.

N이 너무작아 N^2으로 풀었는데

우선순위큐를 이용해서 풀려고하니 막히는 부분이 잘 이해가 되지않아 질문드리게 되었습니다.

우선순위큐로 몸무게와 키가 가장 큰사람부터 정렬하도록 한 후

완전한 rank를 보장하지 않으니 pq를 빼면서 랭크를 매기게 하였는데

틀렸다고 나옵니다.

제 로직에 어느부분이 잘못된 걸까여?

반례를 찾으려고 하는데 잘 안찾아지네여...

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val pq = PriorityQueue<Person> { o1, o2 -> if (o1.height < o2.height && o1.weight < o2.weight) 1 else -1 }
    val arrayList = arrayListOf<Person>()
    for(i in 0 until N){
        val input = br.readLine().split(" ")
        pq.add(Person(input[0].toInt(), input[1].toInt(),i ))
    }
    var rank = 1
    var count = 0
    var prevPerson = Person(0,0, -1);
    while (pq.isEmpty().not()){
       val currentPerson = pq.poll()
       count++

       if(prevPerson.weight > currentPerson.weight && prevPerson.height>currentPerson.height){
           rank = count
       }
       currentPerson.rank = rank
       arrayList.add(currentPerson)
       prevPerson = currentPerson
    }

    arrayList.sortBy {
        it.index
    }


    arrayList.forEach {
        print("${it.rank} ")
    }

}

data class Person(val weight: Int, val height: Int, val index: Int, var rank: Int = 0)

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

문제

문제

출처

ICPC

n^2 이 아닌 nlogn으로 해결해보려하는데...

ckdrb7067 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말