ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Algo Rhythm๐Ÿ•บ๐Ÿ’ƒ] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ๊ณ ๋“์  Kit ๊ธฐ๋Šฅ๊ฐœ๋ฐœ
    Algo Rhythm๐Ÿ•บ๐Ÿ’ƒ/Programmers 2020. 7. 1. 14:30

    ๋ฌธ์ œ ์„ค๋ช…

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

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

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

     

    ์ œํ•œ ์‚ฌํ•ญ

    • ์ž‘์—…์˜ ๊ฐœ์ˆ˜(progresses, speeds๋ฐฐ์—ด์˜ ๊ธธ์ด)๋Š” 100๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
    • ์ž‘์—… ์ง„๋„๋Š” 100 ๋ฏธ๋งŒ์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

    • ์ž‘์—… ์†๋„๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

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

     

    ๋‚˜๋Š” ์–ด๋–ป๊ฒŒ ํ’€์—ˆ๋‚˜

    import java.util.LinkedList;
    import java.util.ArrayList;
    
    class Solution {
        public int[] solution(int[] progresses, int[] speeds) {
            int[] answer;
            int n = progresses.length;
            ArrayList<Integer> distributions = new ArrayList<>();
            LinkedList<Integer> durations = new LinkedList<>();
            
            // calculate the duration
            for(int i = 0; i < n; i++) {
                durations.add((int)Math.ceil((double)(100 - progresses[i]) / speeds[i]));
            }
            
            // calculate the number of functions per distribution
            while(!durations.isEmpty()) {
                int duration = durations.remove();
                int numFunc = 1;
                
                while(!durations.isEmpty()) {
                    int other = durations.element();
                    
                    if(other > duration) break;
    
                    durations.remove();
                    numFunc++;
                }
                
                distributions.add(numFunc);
            }
            
            // convert arraylist to array
            answer = distributions.stream().mapToInt(Integer::intValue).toArray();
            
            return answer;
        }
    }

     

    ๋‚˜๋Š” ์™œ ์ €๋ ‡๊ฒŒ ํ’€์—ˆ๋‚˜

    ๋จผ์ € ๋ฌธ์ œ๋ฅผ ์ฝ๊ณ ๋‚˜์„œ ์Šค์Šค๋กœ์—๊ฒŒ  '๋ช‡ ๋ฒˆ์ด๋‚˜ ๋ฐฐํฌํ•˜๋Š”์ง€ ์•Œ ์ˆ˜ ์žˆ๋Š”๊ฐ€?' ๋ผ๊ณ  ์งˆ๋ฌธํ–ˆ๋‹ค. ๋‹ต์€ '์•„๋‹ˆ์š”.'์˜€๋‹ค. ๊ทธ๋ž˜์„œ List๋กœ ๊ฐ ๋ฐฐํฌ๋งˆ๋‹ค ๋ฐฐํฌ๋˜๋Š” ๊ธฐ๋Šฅ์˜ ์ˆ˜๋ฅผ ์ €์žฅํ•œ ๋’ค ๋ฐฐ์—ด๋กœ ๋ฐ”๊ฟ”์•ผ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

     

    ๊ทธ๋ฆฌ๊ณ ๋‚˜์„œ ์–ด๋–ป๊ฒŒ ์ž‘์—…์‹œ๊ฐ„์„ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋Š”๊ฐ€ ๊ณ ๋ฏผํ•˜๋‹ค๊ฐ€ (100 - progress) / speed๋ฅผ ์˜ฌ๋ฆผํ•˜๋ฉด ๋œ๋‹ค๋Š” ๊ฒƒ์„ ๊นจ๋‹ฌ์•˜๋‹ค. ๊ทธ๋ž˜์„œ ํ์— ์ž‘์—…์‹œ๊ฐ„์„ ๋ชจ๋‘ ๋„ฃ์€ ๋’ค ๋ฐฐํฌ๋•Œ๋งˆ๋‹ค ํฌํ•จ๋˜๋Š” ๊ธฐ๋Šฅ์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•ด์•ผ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค.

     

    ์ด๋ฅผ ์ข…ํ•ฉํ•ด ์•„๋ž˜์™€ ๊ฐ™์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ƒ๊ฐํ–ˆ๋‹ค.

     

    1. ์ž‘์—…ํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ๊ณ„์‚ฐํ•ด์„œ ํ์— ๋„ฃ๋Š”๋‹ค.
    2. ๊ฐ ๋ฐฐํฌ๋งˆ๋‹ค ๋ฐฐํฌ๋˜๋Š” ๊ธฐ๋Šฅ์˜ ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” List๋ฅผ ๋งŒ๋“ ๋‹ค.
    3. ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ์•„๋ž˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
      1. ์ž‘์—…ํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ ํ•˜๋‚˜(d)๋ฅผ dequeํ•œ๋‹ค.
      2. ์ถ”๊ฐ€๋˜๋Š” ๊ธฐ๋Šฅ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” numFunc๋ฅผ 1๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.
      3. ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ์•„๋ž˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
        1. ๋‹ค๋ฅธ ์ž‘์—…์‹œ๊ฐ„(o)์„ peekํ•œ๋‹ค.
        2. o > d์ด๋ฉด break ํ•œ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด ๋‹ค๋ฅธ ์ž‘์—…์‹œ๊ฐ„์„ dequeํ•œ ํ›„ numFunc๋ฅผ incrementํ•œ๋‹ค.
    4. list์— numFunc๋ฅผ addํ•œ๋‹ค.
    5. list๋ฅผ ๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜ํ•œ๋‹ค.

     

    ๋‚˜๋Š” ๋ฌด์—‡์„ ๋ฐฐ์› ๋‚˜

    ์ž‘์—… ์‹œ๊ฐ„์„ ๊ณ„์‚ฐํ•  ๋•Œ Math.ceil์„ ์‚ฌ์šฉํ–ˆ๋Š”๋ฐ argument๊ฐ’์œผ๋กœ int๊ฐ€ ๋“ค์–ด๊ฐ„ ์ค„ ๋ชฐ๋ผ์„œ ๊ณ„์† ํ•ด๋งธ๋‹ค. ์•ž์œผ๋กœ ํ˜•๋ณ€ํ™˜์— ์ฃผ์˜ํ•ด์•ผ๊ฒ ๋‹ค.

     

    Stream์„ ์‚ฌ์šฉํ•ด์„œ Arraylist๋ฅผ array๋กœ ๋ฐ”๊พธ๋Š” ๋ฐฉ๋ฒ•์„ ๋ฐฐ์› ๋‹ค! ์ฝ”๋“œ๊ฐ€ ์—„์ฒญ ๊ฐ„๊ฒฐํ•ด์ง€๊ณ  ๋ณด๊ธฐ ์ข‹๋‹ค! ํด๋ฆฐ ์ฝ”๋“œ์— ํ•œ ๋‹จ๊ณ„ ๋‹ค๊ฐ€๊ฐ„ ๊ฒƒ ๊ฐ™์€ ๊ธฐ๋ถ„์ด ๋“ค์–ด์„œ ๋ฟŒ๋“ฏํ•˜๋‹ค๐Ÿฅฐ

    ๋Œ“๊ธ€

Designed by Tistory.