[programmers] μΌκ·Ό μ§μ - Java
νμ¬μ Demiμ μΌκ·Ό νΌλ‘λλ₯Ό μ΅μννλ λ¬Έμ μμ, μ΄κΈ° μ½λλ λ°°μ΄μ μ λ ¬νμ¬ μ΅λ μμ
λμμ 1μ λΉΌλ λ°©μμΌλ‘ μ κ·ΌνμμΌλ, ν¨μ¨μ± ν
μ€νΈλ₯Ό ν΅κ³Όνμ§ λͺ»νλ€. μ΄λ₯Ό κ°μ νκΈ° μν΄ μ°μ μμ νλ₯Ό μ¬μ©νμ¬ μμ
λμ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬νκ³ , κ°μ₯ λ§μ μμ
λμ κ°μ Έμμ 1μ λΉΌλ λ°©μμΌλ‘ μ κ·Όνμλ€. μ΄ λ°©λ²μ ν ꡬ쑰λ₯Ό νμ©νμ¬ O(log n)μ μκ° λ³΅μ‘λλ₯Ό κ°μ§λ€.
Apr 22, 2024
μΌκ·Ό μ§μ
λ¬Έμ μ€λͺ
νμ¬μ Demiλ κ°λμ μΌκ·Όμ νλλ°μ, μΌκ·Όμ νλ©΄ μΌκ·Ό νΌλ‘λκ° μμ
λλ€. μΌκ·Ό νΌλ‘λλ μΌκ·Όμ μμν μμ μμ λ¨μ μΌμ μμ
λμ μ κ³±νμ¬ λν κ°μ
λλ€. Demiλ Nμκ° λμ μΌκ·Ό νΌλ‘λλ₯Ό μ΅μννλλ‘ μΌν κ²λλ€.Demiκ° 1μκ° λμ μμ
λ 1λ§νΌμ μ²λ¦¬ν μ μλ€κ³ ν λ, ν΄κ·ΌκΉμ§ λ¨μ N μκ°κ³Ό κ° μΌμ λν μμ
λ worksμ λν΄ μΌκ·Ό νΌλ‘λλ₯Ό μ΅μνν κ°μ 리ν΄νλ ν¨μ solutionμ μμ±ν΄μ£ΌμΈμ.
μ ν μ¬ν
works
λ κΈΈμ΄ 1 μ΄μ, 20,000 μ΄νμΈ λ°°μ΄μ λλ€.
works
μ μμλ 50000 μ΄νμΈ μμ°μμ λλ€.
n
μ 1,000,000 μ΄νμΈ μμ°μμ λλ€.
μ μΆλ ₯ μ
works | n | result |
[4, 3, 3] | 4 | 12 |
[2, 1, 2] | 1 | 6 |
[1,1] | 3 | 0 |
μ μΆλ ₯ μ μ€λͺ
μ
μΆλ ₯ μ #1
n=4 μΌ λ, λ¨μ μΌμ μμ
λμ΄ [4, 3, 3] μ΄λΌλ©΄ μΌκ·Ό μ§μλ₯Ό μ΅μννκΈ° μν΄ 4μκ°λμ μΌμ ν κ²°κ³Όλ [2, 2, 2]μ
λλ€. μ΄ λ μΌκ·Ό μ§μλ 22 + 22 + 22 = 12 μ
λλ€.
μ
μΆλ ₯ μ #2
n=1μΌ λ, λ¨μ μΌμ μμ
λμ΄ [2,1,2]λΌλ©΄ μΌκ·Ό μ§μλ₯Ό μ΅μννκΈ° μν΄ 1μκ°λμ μΌμ ν κ²°κ³Όλ [1,1,2]μ
λλ€. μΌκ·Όμ§μλ 12 + 12 + 22 = 6μ
λλ€.
μ
μΆλ ₯ μ #3
λ¨μ μμ
λμ΄ μμΌλ―λ‘ νΌλ‘λλ 0μ
λλ€.
μ²μ μλν μ½λ
import java.util.*; class Solution { public long solution(int n, int[] works) { long answer = 0; for(int i=n; i>0; i--){ Arrays.sort(works); if(works[works.length-1]>0){ works[works.length-1]--; } } for(int i=0; i<works.length; i++){ answer += Math.pow(works[i], 2); } return answer; } }
κ°μ ν μ½λ
import java.util.PriorityQueue; import java.util.Collections; class Solution { public long solution(int n, int[] works) { PriorityQueue<Integer> overtime = new PriorityQueue<>(Collections.reverseOrder()); for (int work : works) { overtime.offer(work); } for (int i = 0; i < n; i++) { int max = (int)overtime.poll(); if (max <= 0) break; overtime.offer(max - 1); } return sumPow(overtime); } long sumPow(PriorityQueue<Integer> works) { long sum = 0; while (!works.isEmpty()) { sum += Math.pow(works.poll(), 2); } return sum; } }
ν΅μ¬ ν€μλ
- μ²μ μλν μ½λλ
n
λ§νΌ λ°λ³΅ν λλ§λ€ λ°°μ΄μ μ λ ¬ν΄μ λ°°μ΄μ μ΅λκ°μμ 1μ λΉΌλ λ°©μμΌλ‘ μ κ·Όνλ€. - μ΄ κ²½μ° μκ° λ³΅μ‘λλ
O(nlogn)
μ΄κ³ , ν¨μ¨μ± ν μ€νΈλ₯Ό ν΅κ³Όνμ§ λͺ»νλ€.
- μ΄λ₯Ό ν΄κ²°νκΈ° μν΄ μ°μ μμ νλ₯Ό μ¬μ©ν΄μ μμ λμ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬ν΄μ μ μ₯νλ€.
- μ£Όμ΄μ§ λ°°μ΄μ μννλ©΄μ κ° μμ
λμ μ°μ μμ νμ μ μ₯νκ³ ,
n
λ§νΌ λ°λ³΅λ¬Έμ μννλ€. - μ°μ μμ νμμ κ°μ₯ λ§μ μμ
λμ κ°μ Έμ€κ³
max
λ³μμ μ μ₯νλ€. - λ§μ½
max
κ° 0 μ΄νλΌλ©΄ λ μ΄μ μμ μ ν μ μμΌλ―λ‘ λ°λ³΅μ μ’ λ£νλ€. - μμ
μ ν μ μλ€λ©΄
max
μμ 1μ λΉΌκ³ λ€μ μ°μ μμ νμ λ£μ΄μ€λ€. - κ·Έ ν μ°μ μμ νμ μλ κ°λ€μ μ κ³±μ ν©μ λ°ννλ€.
κ²°λ‘ !
ν΄λΉ λ¬Έμ λ₯Ό νλ©΄μ μ°μ μμ νλ₯Ό νμ©νμ¬ λ¬Έμ λ₯Ό ν μ μλ€λ κ²μ μκ² λμκ³ , ν κ΅¬μ‘°λ‘ μΈν΄
O(log n)
μκ°μ΄ κ±Έλ¦°λ€λ κ²μ μκ² λμλ€.Share article