λ¬Έμ 1οΈβ£ (π λ¦¬νΈ μ½λ_쑰건μ λ§λ μ§ μ°ΎκΈ°)
π‘ IDEA : νΉλ³ν λ°©λ²μ μμκ³ , μνμ ν΅ν΄ ν΄κ²°
class Solution {
public int countPairs(List<Integer> nums, int target) {
int answer = 0;
// μμ νμ
for (int i=0; i<nums.size()-1; i++) {
for (int j=i+1; j<nums.size(); j++) {
if (nums.get(i)+nums.get(j) < target) {
answer++;
continue;
}
}
}
return answer;
}
}
λ¬Έμ 2οΈβ£ (π νλ‘κ·Έλλ¨Έμ€_μ κ΅ μ¬μ¬)
π λ¬Έμ
nλͺ μ΄ μ κ΅μ¬μ¬λ₯Ό μν΄ μ€μ μμ κΈ°λ€λ¦¬κ³ μμ΅λλ€. κ° μ κ΅μ¬μ¬λμ μλ μ¬μ¬κ΄λ§λ€ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ λ€λ¦ λλ€.
μ²μμ λͺ¨λ μ¬μ¬λλ λΉμ΄μμ΅λλ€. ν μ¬μ¬λμμλ λμμ ν λͺ λ§ μ¬μ¬λ₯Ό ν μ μμ΅λλ€. κ°μ₯ μμ μ μλ μ¬λμ λΉμ΄ μλ μ¬μ¬λλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μ μμ΅λλ€. νμ§λ§ λ 빨리 λλλ μ¬μ¬λκ° μμΌλ©΄ κΈ°λ€λ Έλ€κ° κ·Έκ³³μΌλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μλ μμ΅λλ€.
λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μλ‘ νκ³ μΆμ΅λλ€.
μ κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λ μ n, κ° μ¬μ¬κ΄μ΄ ν λͺ μ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ΄ λ΄κΈ΄ λ°°μ΄ timesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
π« μ ν μ¬ν
- μ κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λμ 1λͺ μ΄μ 1,000,000,000λͺ μ΄νμ λλ€.
- κ° μ¬μ¬κ΄μ΄ ν λͺ μ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ 1λΆ μ΄μ 1,000,000,000λΆ μ΄νμ λλ€.
- μ¬μ¬κ΄μ 1λͺ μ΄μ 100,000λͺ μ΄νμ λλ€.
π μ μΆλ ₯ μ
| n | times | return |
| 6 | [7, 10] | 28 |
π€ νμ΄ λ°©λ²
β‘οΈ λ¬Έμ μμ μ μλ μ ν κ·Έλλ‘ μ΄λΆνμμ μ¬μ©νμλ€. μ΄λ μΆκ°μ μΌλ‘ LowerBound κ°λ κΉμ§ νμ©νμλ€.
STEP β : νμν΄μΌν μ΅λ λ²μλ₯Ό μ€μ
β‘οΈ times λ°°μ΄μ Arrays.sort() λ₯Ό νμ©ν΄ μ€λ¦μ°¨μ μ λ ¬ ν Index 0 μ ν΄λΉνλ μ΅μκ°κ³Ό n μ κ³±ν΄ μ΅λ λ²μλ₯Ό μ€μ νμκ³ , ν΄λΉ λ³μλ maxTime μ΄λΌκ³ λͺ λͺ νμλ€.
μ μΆλ ₯ μμλ‘ νμΈ νλ©΄ times μ μ΅μκ° 7 κ³Ό n μ κ° 6 μ κ³±νμ¬ μ΅λ μμ μκ°μ 42 μ΄κ° λλ€.
STEP β‘ : μ΄λΆ νμ μν
β‘οΈ μ΅λ λ²μλ₯Ό μ νμΌλ, μ΄λΆ νμμ κ°λ μμ left λ₯Ό 0, right λ₯Ό maxTime κ·Έλ¦¬κ³ LowerBound κ°μΈ minTime μ maxTime+1 μΌλ‘ μ΄κΈ°ν ν λ€ μ΄λΆ νμμ μννλ€.
β‘οΈ μ΄λΆ νμ κ³Όμ μμ νμ¬ μκ°μΈ mid κ°κ³Ό times λ³μλ₯Ό λλμ΄ ν΄λΉ μκ°μ κΈ°μ€μΌλ‘ λͺλͺ μ΄ μ κ΅ μ¬μ¬λ₯Ό λ°μ μ μλμ§ νμΈνλ€. λ§μ½ μνλ κ° n μ λ²μ΄λκ² μ»€μ§λ€λ©΄ λ κ³μ°ν νμμμ΄ λμ΄κ°μ λ°λ‘ left κ°μ μ‘°μ νλ€.
β‘οΈ μ΄λ LowerBound λ₯Ό νμ©νλ μ΄μ λ LowerBound λ λͺ©νλ‘ νλ κ°μ μ΄μμΈ μ΅μμ μΈλ±μ€λ₯Ό λ°ννλ κ°λ μ΄κΈ° λλ¬Έμ΄λ€. λ°λΌμ μμ 1 μ λ¦¬ν΄ κ°μΈ 28 μ΄νμ 29, 30 λ± λͺ¨λ κ°λ€μ 6λͺ μ΄μμ μ κ΅μ¬μ¬ ν μ μμ§λ§ μ΅μμ μκ°μ 28μ΄ μ΄κΈ° λλ¬Έμ ν΄λΉ κ°μ λ°ννκ² λλ€.

STEP β’ : minTime κ° λ°ν
β‘οΈ μ΄λΆ νμμ΄ μ’ λ£λλ©΄ LowerBound μ ν΄λΉ νλ κ°μΈ minTime μ λ°ννλ©΄ λλ€.
π» νμ΄ μ½λ
import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
// times λ°°μ΄ μ€λ¦μ°¨μ μ λ ¬
Arrays.sort(times);
// *μ£Όμ* long μΌλ‘ νλ³ν νμ!
long maxTime = (long) n * times[0];
// μ΄λΆνμ μ€ν
long left = 1;
long right = maxTime+1;
long minTime = maxTime;
while (left <= right) {
long mid = (left + right) / 2;
// System.out.printf("νμ¬ μκ° : %d\n", time[mid]);
long cnt = 0;
for (int i=0; i<times.length; i++) {
cnt += mid / times[i];
if (cnt > n) break;
// System.out.printf("%d λν¨\n", time[mid]/times[i]);
}
// System.out.printf("νμ¬ minIdx κ° : %d\n", minIdx);
if (cnt >= n) {
// System.out.printf("cnt κ° %d μΌλ‘ λ ν¬κ±°λ κ°μ\n", cnt);
right = mid-1;
minTime = Math.min(minTime, mid);
}
else {
left = mid+1;
}
// System.out.printf("μ‘°μ ν minIdx κ° : %d\n", minIdx);
}
return minTime;
}
}
β‘οΈ νμ΄νλ©΄μ μ‘°μ¬ν΄μΌν μ μ μ ν μ¬νμμ κ°λ€μ΄ ν¬λ―λ‘ int μλ£νμ νμ©ν κ²½μ° κ°μ΄ λμ΄κ° μλͺ»λ κ°μ λΌ μ μλ€. λ°λΌμ λͺ¨λ κ°μ long μΌλ‘ μ΄κΈ°ν λλ νλ³ννμ¬ νμ΄νμ¬μΌ νλ€.

'TIL π' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
| TIL (2024.06.13) (1) | 2024.06.15 |
|---|---|
| TIL (2024.06.12) (0) | 2024.06.13 |
| TIL (2024.06.08) (1) | 2024.06.09 |
| TIL (2024.06.06) (0) | 2024.06.07 |
| TIL (2024.06.05) (1) | 2024.06.05 |