-
[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๋ฅผ ์ฌ๋ฆผํ๋ฉด ๋๋ค๋ ๊ฒ์ ๊นจ๋ฌ์๋ค. ๊ทธ๋์ ํ์ ์์ ์๊ฐ์ ๋ชจ๋ ๋ฃ์ ๋ค ๋ฐฐํฌ๋๋ง๋ค ํฌํจ๋๋ ๊ธฐ๋ฅ์ ์๋ฅผ ๊ณ์ฐํด์ผ๊ฒ ๋ค๊ณ ์๊ฐํ๋ค.
์ด๋ฅผ ์ข ํฉํด ์๋์ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐํ๋ค.
- ์์ ํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๊ณ์ฐํด์ ํ์ ๋ฃ๋๋ค.
- ๊ฐ ๋ฐฐํฌ๋ง๋ค ๋ฐฐํฌ๋๋ ๊ธฐ๋ฅ์ ์๋ฅผ ์ ์ฅํ๋ List๋ฅผ ๋ง๋ ๋ค.
- ํ๊ฐ ๋น ๋๊น์ง ์๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
- ์์ ํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ ํ๋(d)๋ฅผ dequeํ๋ค.
- ์ถ๊ฐ๋๋ ๊ธฐ๋ฅ์ ์๋ฅผ ๋ํ๋ด๋ numFunc๋ฅผ 1๋ก ์ด๊ธฐํํ๋ค.
- ํ๊ฐ ๋น ๋๊น์ง ์๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
- ๋ค๋ฅธ ์์ ์๊ฐ(o)์ peekํ๋ค.
- o > d์ด๋ฉด break ํ๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด ๋ค๋ฅธ ์์ ์๊ฐ์ dequeํ ํ numFunc๋ฅผ incrementํ๋ค.
- list์ numFunc๋ฅผ addํ๋ค.
- list๋ฅผ ๋ฐฐ์ด๋ก ๋ณํํ๋ค.
๋๋ ๋ฌด์์ ๋ฐฐ์ ๋
์์ ์๊ฐ์ ๊ณ์ฐํ ๋ Math.ceil์ ์ฌ์ฉํ๋๋ฐ argument๊ฐ์ผ๋ก int๊ฐ ๋ค์ด๊ฐ ์ค ๋ชฐ๋ผ์ ๊ณ์ ํด๋งธ๋ค. ์์ผ๋ก ํ๋ณํ์ ์ฃผ์ํด์ผ๊ฒ ๋ค.
Stream์ ์ฌ์ฉํด์ Arraylist๋ฅผ array๋ก ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ ๋ฐฐ์ ๋ค! ์ฝ๋๊ฐ ์์ฒญ ๊ฐ๊ฒฐํด์ง๊ณ ๋ณด๊ธฐ ์ข๋ค! ํด๋ฆฐ ์ฝ๋์ ํ ๋จ๊ณ ๋ค๊ฐ๊ฐ ๊ฒ ๊ฐ์ ๊ธฐ๋ถ์ด ๋ค์ด์ ๋ฟ๋ฏํ๋ค๐ฅฐ
'Algo Rhythm๐บ๐ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ