๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 8์ผ์ฐจ TIL - ๊ธฐ๋Šฅ ๊ฐœ๋ฐœ

HOONSSACยท2024๋…„ 7์›” 29์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
8/41
post-thumbnail

โณ๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํŒ€์—์„œ๋Š” ๊ธฐ๋Šฅ ๊ฐœ์„  ์ž‘์—…์„ ์ˆ˜ํ–‰ ์ค‘์ž…๋‹ˆ๋‹ค. ๊ฐ ๊ธฐ๋Šฅ์€ ์ง„๋„๊ฐ€ 100%์ผ ๋•Œ ์„œ๋น„์Šค์— ๋ฐ˜์˜ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋˜, ๊ฐ ๊ธฐ๋Šฅ์˜ ๊ฐœ๋ฐœ์†๋„๋Š” ๋ชจ๋‘ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์— ๋’ค์— ์žˆ๋Š” ๊ธฐ๋Šฅ์ด ์•ž์— ์žˆ๋Š” ๊ธฐ๋Šฅ๋ณด๋‹ค ๋จผ์ € ๊ฐœ๋ฐœ๋  ์ˆ˜ ์žˆ๊ณ , ์ด๋•Œ ๋’ค์— ์žˆ๋Š” ๊ธฐ๋Šฅ์€ ์•ž์— ์žˆ๋Š” ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋  ๋•Œ ํ•จ๊ป˜ ๋ฐฐํฌ๋ฉ๋‹ˆ๋‹ค.

๋จผ์ € ๋ฐฐํฌ๋˜์–ด์•ผ ํ•˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์ž‘์—…์˜ ์ง„๋„๊ฐ€ ์ ํžŒ ์ •์ˆ˜ ๋ฐฐ์—ด progresses์™€ ๊ฐ ์ž‘์—…์˜ ๊ฐœ๋ฐœ ์†๋„๊ฐ€ ์ ํžŒ ์ •์ˆ˜ ๋ฐฐ์—ด speeds๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ๊ฐ ๋ฐฐํฌ๋งˆ๋‹ค ๋ช‡ ๊ฐœ์˜ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋˜๋Š”์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • ์ž‘์—…์˜ ๊ฐœ์ˆ˜(progresses, speeds๋ฐฐ์—ด์˜ ๊ธธ์ด)๋Š” 100๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ์ž‘์—… ์ง„๋„๋Š” 100 ๋ฏธ๋งŒ์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • ์ž‘์—… ์†๋„๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • ๋ฐฐํฌ๋Š” ํ•˜๋ฃจ์— ํ•œ ๋ฒˆ๋งŒ ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ํ•˜๋ฃจ์˜ ๋์— ์ด๋ฃจ์–ด์ง„๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ง„๋„์œจ์ด 95%์ธ ์ž‘์—…์˜ ๊ฐœ๋ฐœ ์†๋„๊ฐ€ ํ•˜๋ฃจ์— 4%๋ผ๋ฉด ๋ฐฐํฌ๋Š” 2์ผ ๋’ค์— ์ด๋ฃจ์–ด์ง‘๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

progressesspeedsreturn
[93, 30, 55][1, 30, 5}[2, 1]
[95, 90, 99, 99, 80, 99][1, 1, 1, 1, 1, 1][1, 3 2]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

์ฒซ ๋ฒˆ์งธ ๊ธฐ๋Šฅ์€ 93% ์™„๋ฃŒ๋˜์–ด ์žˆ๊ณ  ํ•˜๋ฃจ์— 1%์”ฉ ์ž‘์—…์ด ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ 7์ผ๊ฐ„ ์ž‘์—… ํ›„ ๋ฐฐํฌ๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
๋‘ ๋ฒˆ์งธ ๊ธฐ๋Šฅ์€ 30%๊ฐ€ ์™„๋ฃŒ๋˜์–ด ์žˆ๊ณ  ํ•˜๋ฃจ์— 30%์”ฉ ์ž‘์—…์ด ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ 3์ผ๊ฐ„ ์ž‘์—… ํ›„ ๋ฐฐํฌ๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด์ „ ์ฒซ ๋ฒˆ์งธ ๊ธฐ๋Šฅ์ด ์•„์ง ์™„์„ฑ๋œ ์ƒํƒœ๊ฐ€ ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ฒซ ๋ฒˆ์งธ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋˜๋Š” 7์ผ์งธ ๋ฐฐํฌ๋ฉ๋‹ˆ๋‹ค.
์„ธ ๋ฒˆ์งธ ๊ธฐ๋Šฅ์€ 55%๊ฐ€ ์™„๋ฃŒ๋˜์–ด ์žˆ๊ณ  ํ•˜๋ฃจ์— 5%์”ฉ ์ž‘์—…์ด ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ 9์ผ๊ฐ„ ์ž‘์—… ํ›„ ๋ฐฐํฌ๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ 7์ผ์งธ์— 2๊ฐœ์˜ ๊ธฐ๋Šฅ, 9์ผ์งธ์— 1๊ฐœ์˜ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

๋ชจ๋“  ๊ธฐ๋Šฅ์ด ํ•˜๋ฃจ์— 1%์”ฉ ์ž‘์—…์ด ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ, ์ž‘์—…์ด ๋๋‚˜๊ธฐ๊นŒ์ง€ ๋‚จ์€ ์ผ์ˆ˜๋Š” ๊ฐ๊ฐ 5์ผ, 10์ผ, 1์ผ, 1์ผ, 20์ผ, 1์ผ์ž…๋‹ˆ๋‹ค. ์–ด๋–ค ๊ธฐ๋Šฅ์ด ๋จผ์ € ์™„์„ฑ๋˜์—ˆ๋”๋ผ๋„ ์•ž์— ์žˆ๋Š” ๋ชจ๋“  ๊ธฐ๋Šฅ์ด ์™„์„ฑ๋˜์ง€ ์•Š์œผ๋ฉด ๋ฐฐํฌ๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ 5์ผ์งธ์— 1๊ฐœ์˜ ๊ธฐ๋Šฅ, 10์ผ์งธ์— 3๊ฐœ์˜ ๊ธฐ๋Šฅ, 20์ผ์งธ์— 2๊ฐœ์˜ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋ฉ๋‹ˆ๋‹ค.


โœ๏ธํ’€์ด

๋‚˜๋Š” ์ธ๋ฑ์Šค ๋ณ€์ˆ˜๋ฅผ ํ•˜๋‚˜ ๋งŒ๋“ค์–ด์„œ ๋ฌธ์ œ์— ์ ‘๊ทผ์„ ํ•ด๋ณด์•˜๋‹ค.
ํ˜„์žฌ ์ธ๋ฑ์Šค ์š”์†Œ์˜ ๊ฐ’์ด 100 ์ด์ƒ์ด๋ฉด, ์ฆ‰, ์ง„๋„๊ฐ€ 100% ์ด์ƒ์ด๋ผ๋ฉด, ์ง„๋„๊ฐ€ 100% ์•„๋‹Œ ๊ฐ’์„ ๋งŒ๋‚  ๋•Œ๊นŒ์ง€, ์ธ๋ฑ์Šค๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ ์ฃผ๋ฉด์„œ ๋™์‹œ์— ๋ฐฐํฌ๋œ ๊ธฐ๋Šฅ์˜ ๊ฐœ์ˆ˜๋ฅผ 1์”ฉ ์ฆ๊ฐ€์‹œ์ผœ์ฃผ๋ฉด ๋  ๊ฒƒ์ด๋ผ ์ƒ๊ฐํ•˜๊ณ  ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ–ˆ๋‹ค.

๐Ÿ–ฅ๏ธ์ตœ์ข… ์ฝ”๋“œ

import java.util.*;

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        int releaseIndex = 0;
        ArrayList<Integer> answer = new ArrayList<>();
        
        while (releaseIndex < progresses.length) {
            for (int j = 0; j < progresses.length; j++) {
                progresses[j] += speeds[j];
            }
            int count = 0;
            while (releaseIndex < progresses.length && progresses[releaseIndex] >= 100) {
                releaseIndex++;
                count ++;
            }
            if (count > 0) {
                answer.add(count);
            }
        }
        return answer;
    }
}

์šฐ์„  ๋™์‹œ์— ๋ฐฐ๋ณด๋œ ๊ธฐ๋Šฅ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‹ด๋Š” ArrayList answer๋ฅผ ์„ ์–ธํ•ด ์ฃผ์—ˆ๋‹ค.
progresses๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๊ธฐ ์œ„ํ•ด releaseIndex๋„ ์„ ์–ธํ•ด ์ฃผ์—ˆ๊ณ , progresses์˜ ๊ธธ์ด๋งŒํผ ์ˆœํšŒํ•˜๋„๋ก ๋ฐ˜๋ณต๋ฌธ์„ ๋งŒ๋“ค์—ˆ๋‹ค.
์ผ๋‹จ, ์ž‘์—…์„ ํ•œ ๋ฒˆ ์ง„ํ–‰์‹œ์ผœ ์ฃผ๊ธฐ ์œ„ํ•ด ๊ฐ๊ฐ์˜ ์ง„๋„์— ๊ฐ๊ฐ์˜ speed๋ฅผ ๋”ํ•ด์ฃผ์—ˆ๋‹ค.

์ด์ œ, ๋งŒ์•ฝ, releaseIndex๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ์ง„๋„๊ฐ€ 100%๋ผ๋ฉด,
๊ทธ๋ฆฌ๊ณ , ๊ทธ ๋’ค์— ์ง„๋„๊ฐ€ 100%์ธ ์š”์†Œ๊ฐ€ ๋” ์กด์žฌํ•œ๋‹ค๋ฉด,
๊ทธ ๊ฐœ์ˆ˜๋งŒํผ ๋ฐฐํฌ๋ฅผ ์‹œ์ผœ์ฃผ์–ด์•ผ ํ•œ๋‹ค.

์ด๋ฅผ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ํ˜„์žฌ releaseIndex๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ์ง„๋„๊ฐ€ 100% ์ด์ƒ์ด๋ผ๋Š” ์กฐ๊ฑด์˜ ๋ฐ˜๋ณต๋ฌธ์„ ๋งŒ๋“ค์–ด releaseIndex๊ฐ€ ๋‹ค์Œ ์ธ๋ฑ์Šค๋กœ ์ด๋™ํ•˜๋„๋ก 1์„ ์ฆ๊ฐ€์‹œ์ผœ ์ฃผ์—ˆ๊ณ , ๋ฐฐํฌ๋œ ๊ธฐ๋Šฅ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” count๋ณ€์ˆ˜์—๋„ 1์„ ์ฆ๊ฐ€์‹œ์ผœ ์ฃผ์—ˆ๋‹ค.

๊ทธ๋ ‡๊ฒŒ ํ•œ ๋ฒˆ์— ๋ฐฐํฌ๋œ ๊ธฐ๋Šฅ์˜ ๊ฐœ์ˆ˜๋ฅผ answer์— ์ถ”๊ฐ€ํ•ด์คŒ์œผ๋กœ์จ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค!


๐Ÿ˜ฒ๋‹ค๋ฅธ ํ’€์ด

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        // ๊ฐ ๊ธฐ๋Šฅ์˜ ๊ฐœ๋ฐœ์ด ์™„๋ฃŒ๋˜๋Š” ๋ฐ ํ•„์š”ํ•œ ๋‚  ์ˆ˜๋ฅผ ์ €์žฅํ•  ๋ฆฌ์ŠคํŠธ
        List<Integer> days = new ArrayList<>();
        
        // ๊ฐ ๊ธฐ๋Šฅ๋ณ„๋กœ ๊ฐœ๋ฐœ ์™„๋ฃŒ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ๋‚  ์ˆ˜๋ฅผ ๊ณ„์‚ฐ
        for (int i = 0; i < progresses.length; i++) {
            int progress = progresses[i];  // ํ˜„์žฌ ์ž‘์—…์˜ ์ง„๋„
            int speed = speeds[i];          // ํ˜„์žฌ ์ž‘์—…์˜ ๊ฐœ๋ฐœ ์†๋„
            // ์ž‘์—… ์™„๋ฃŒ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ๋‚  ์ˆ˜ ๊ณ„์‚ฐ
            int daysToComplete = (int) Math.ceil((100 - progress) / speed);
            // ๋ฆฌ์ŠคํŠธ์— ๊ณ„์‚ฐ๋œ ๋‚  ์ˆ˜ ์ถ”๊ฐ€
            days.add(daysToComplete);
        }
        
        // ๊ฐœ๋ฐœ ์™„๋ฃŒ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ๋‚  ์ˆ˜๋ฅผ ํ์— ์ €์žฅ
        Queue<Integer> queue = new LinkedList<>(days);
        // ๊ฐ ๋ฐฐํฌ์ผ์— ๋ช‡ ๊ฐœ์˜ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋˜๋Š”์ง€๋ฅผ ์ €์žฅํ•  ๋ฆฌ์ŠคํŠธ
        List<Integer> result = new ArrayList<>();
        
        // ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต
        while (!queue.isEmpty()) {
            // ํ˜„์žฌ ์ฒ˜๋ฆฌํ•  ๊ธฐ๋Šฅ์˜ ๊ฐœ๋ฐœ ์™„๋ฃŒ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ๋‚  ์ˆ˜
            int currentDay = queue.poll();
            int count = 1;  // ํ˜„์žฌ ๊ธฐ๋Šฅ์„ ํฌํ•จํ•˜์—ฌ ๋ฐฐํฌ๋˜๋Š” ๊ธฐ๋Šฅ ์ˆ˜ (์ตœ์†Œ 1๊ฐœ๋Š” ๋ฐฐํฌ๋จ)
            
            // ํ˜„์žฌ ๊ธฐ๋Šฅ์ด ๋ฐฐํฌ๋  ๋‚ ์— ๋ฐฐํฌ๋  ์ˆ˜ ์žˆ๋Š” ํ›„์† ๊ธฐ๋Šฅ๋“ค ํ™•์ธ
            while (!queue.isEmpty() && queue.peek() <= currentDay) {
                queue.poll();  // ํ›„์† ๊ธฐ๋Šฅ์„ ํ์—์„œ ์ œ๊ฑฐ
                count++;       // ๋ฐฐํฌ๋˜๋Š” ๊ธฐ๋Šฅ ์ˆ˜ ์ฆ๊ฐ€
            }
            
            // ๋ฐฐํฌ๋˜๋Š” ๊ธฐ๋Šฅ์˜ ์ˆ˜๋ฅผ ๊ฒฐ๊ณผ ๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€
            result.add(count);
        }
        
        // ๊ฒฐ๊ณผ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ๋ฐ˜ํ™˜
        return result.stream().mapToInt(i -> i).toArray();
    }
}

์š”๊ฑด ์˜ค๋Š˜ ์„ธ์…˜์—์„œ ๋ณธ ๋‹ค๋ฅธ ๋ถ„์˜ ์ฝ”๋“œ์ด๋‹ค

๊ฐ ๊ธฐ๋Šฅ๋ณ„๋กœ ๊ฐœ๋ฐœ ์™„๋ฃŒ๊นŒ์ง€ ๊ฑธ๋ฆฌ๋Š” ๋‚  ์ˆ˜๋ฅผ ๋จผ์ € ๊ณ„์‚ฐํ•œ ๋‹ค์Œ,
ํ๋ฅผ ์‚ฌ์šฉํ•ด ํ˜„์žฌ ๊ธฐ๋Šฅ๊ณผ ํ›„์† ๊ธฐ๋Šฅ์˜ ๋ฐฐํฌ ๊ฐ€๋Šฅ ์—ฌ๋ถ€๋ฅผ ๋”ฐ์ง€๋ฉด์„œ ํ์—์„œ ์š”์†Œ๋“ค์„ ํ•˜๋‚˜์”ฉ ์ œ๊ฑฐํ•˜๋ฉฐ ์ˆซ์ž๋ฅผ ์นด์šดํŠธ ํ•ด์ฃผ๋Š” ๋ฐฉ์‹์ด๋‹ค.

๋‚ ์งœ๋ฅผ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด์„œ ํ‘ธ๋Š” ๋ฐฉ๋ฒ•๋„ ์žˆ์—ˆ๋‹ค๋‹ˆ..!
์˜ค๋Š˜๋„ ํ•œ ์ˆ˜ ๋ฐฐ์šฐ๊ณ  ๊ฐ‘๋‹ˆ๋‹ค!๐Ÿ’ช


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปReposiroty

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 7์›” 29์ผ

๐Ÿ‘๐Ÿ‘๐Ÿ‘

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ