[programmers] ์คํจ์จ - Java
์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ์คํจ์จ์ ๊ณ์ฐํ๋ ์ฝ๋๋ฅผ ์์ฑํด์ผ ํ๋ค. ์คํจ์จ์ ์คํ
์ด์ง์ ๋๋ฌํ์ผ๋ ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์๋ฅผ ์คํ
์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์๋ก ๋๋ ๊ฐ์ด๋ค. ์คํ
์ด์ง์ ๊ฐ์ N๊ณผ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด stages๊ฐ ์ฃผ์ด์ง ๋, ์คํจ์จ์ด ๋์ ์คํ
์ด์ง๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ฒจ์๋ ๋ฐฐ์ด์ ๋ฐํํ๋ solution ํจ์๋ฅผ ์์ฑํด์ผ ํ๋ค. ์ด๋ฅผ ์ํด ๋ฐฐ์ด๊ณผ HashMap์ ์ฌ์ฉํ๋ฉฐ, HashMap์ keySet์ List์ ๋ฃ์ ํ, List์ sort ๋ฉ์๋๋ก ๊ฐ์ ์ ๋ ฌํ๋ค.
Apr 09, 2024
์คํจ์จ
๋ฌธ์ ์ค๋ช
์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋
๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์คํ
์ด์ง ์ฐจ์ด๊ฐ ๋๋ฌด ํฐ ๊ฒ์ด ๋ฌธ์ ์๋ค.
์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํ ๊น ๊ณ ๋ฏผ ํ ๊ทธ๋
๋ ๋์ ์ผ๋ก ๊ฒ์ ์๊ฐ์ ๋๋ ค์ ๋์ด๋๋ฅผ ์กฐ์ ํ๊ธฐ๋ก ํ๋ค. ์ญ์ ์ํผ ๊ฐ๋ฐ์๋ผ ๋๋ถ๋ถ์ ๋ก์ง์ ์ฝ๊ฒ ๊ตฌํํ์ง๋ง, ์คํจ์จ์ ๊ตฌํ๋ ๋ถ๋ถ์์ ์๊ธฐ์ ๋น ์ง๊ณ ๋ง์๋ค. ์ค๋ ๋ฆฌ๋ฅผ ์ํด ์คํจ์จ์ ๊ตฌํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ผ.
- ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค.
- ์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์ ์ฒด ์คํ
์ด์ง์ ๊ฐ์ N, ๊ฒ์์ ์ด์ฉํ๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด stages๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์คํจ์จ์ด ๋์ ์คํ
์ด์ง๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์คํ
์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ฒจ์๋ ๋ฐฐ์ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ๋ผ.
์ ํ์ฌํญ
- ์คํ
์ด์ง์ ๊ฐ์ N์
1
์ด์500
์ดํ์ ์์ฐ์์ด๋ค.
- stages์ ๊ธธ์ด๋
1
์ด์200,000
์ดํ์ด๋ค.
- stages์๋
1
์ด์N + 1
์ดํ์ ์์ฐ์๊ฐ ๋ด๊ฒจ์๋ค. - ๊ฐ ์์ฐ์๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋์ ์ค์ธ ์คํ ์ด์ง์ ๋ฒํธ๋ฅผ ๋ํ๋ธ๋ค.
- ๋จ,
N + 1
์ ๋ง์ง๋ง ์คํ ์ด์ง(N ๋ฒ์งธ ์คํ ์ด์ง) ๊น์ง ํด๋ฆฌ์ด ํ ์ฌ์ฉ์๋ฅผ ๋ํ๋ธ๋ค.
- ๋ง์ฝ ์คํจ์จ์ด ๊ฐ์ ์คํ ์ด์ง๊ฐ ์๋ค๋ฉด ์์ ๋ฒํธ์ ์คํ ์ด์ง๊ฐ ๋จผ์ ์ค๋๋ก ํ๋ฉด ๋๋ค.
- ์คํ
์ด์ง์ ๋๋ฌํ ์ ์ ๊ฐ ์๋ ๊ฒฝ์ฐ ํด๋น ์คํ
์ด์ง์ ์คํจ์จ์
0
์ผ๋ก ์ ์ํ๋ค.
์ ์ถ๋ ฅ ์
N | stages | result |
5 | [2, 1, 2, 6, 2, 4, 3, 3] | [3,4,2,1,5] |
4 | [4,4,4,4,4] | [4,1,2,3] |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
1๋ฒ ์คํ
์ด์ง์๋ ์ด 8๋ช
์ ์ฌ์ฉ์๊ฐ ๋์ ํ์ผ๋ฉฐ, ์ด ์ค 1๋ช
์ ์ฌ์ฉ์๊ฐ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ๋ค. ๋ฐ๋ผ์ 1๋ฒ ์คํ
์ด์ง์ ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ๋ค.
- 1 ๋ฒ ์คํ ์ด์ง ์คํจ์จ : 1/8
2๋ฒ ์คํ
์ด์ง์๋ ์ด 7๋ช
์ ์ฌ์ฉ์๊ฐ ๋์ ํ์ผ๋ฉฐ, ์ด ์ค 3๋ช
์ ์ฌ์ฉ์๊ฐ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ๋ค. ๋ฐ๋ผ์ 2๋ฒ ์คํ
์ด์ง์ ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ๋ค.
- 2 ๋ฒ ์คํ ์ด์ง ์คํจ์จ : 3/7
๋ง์ฐฌ๊ฐ์ง๋ก ๋๋จธ์ง ์คํ
์ด์ง์ ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ๋ค.
- 3 ๋ฒ ์คํ ์ด์ง ์คํจ์จ : 2/4
- 4๋ฒ ์คํ ์ด์ง ์คํจ์จ : 1/2
- 5๋ฒ ์คํ ์ด์ง ์คํจ์จ : 0/1
๊ฐ ์คํ
์ด์ง์ ๋ฒํธ๋ฅผ ์คํจ์จ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
- [3,4,2,1,5]
์
์ถ๋ ฅ ์ #2
๋ชจ๋ ์ฌ์ฉ์๊ฐ ๋ง์ง๋ง ์คํ
์ด์ง์ ์์ผ๋ฏ๋ก 4๋ฒ ์คํ
์ด์ง์ ์คํจ์จ์ 1์ด๋ฉฐ ๋๋จธ์ง ์คํ
์ด์ง์ ์คํจ์จ์ 0์ด๋ค.
- [4,1,2,3]
solution.java
import java.util.*; class Solution { public int[] solution(int N, int[] stages) { int[] arr = new int[N+1]; double reachedPlayer = stages.length; for(int i=0; i<stages.length; i++){ arr[stages[i]-1]++; } HashMap<Integer, Double> map = new HashMap<>(); for(int i=0; i<arr.length-1; i++){ double num = 0.0; if(arr[i]!=0){ num = arr[i] / reachedPlayer; } map.put(i+1, num); reachedPlayer -= arr[i]; } List<Integer> keySet = new ArrayList<>(map.keySet()); int[] answer = new int[N]; keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1))); for(int i=0; i<keySet.size(); i++){ answer[i] = keySet.get(i); } return answer; } }
ํต์ฌ ํค์๋
- ๋ฐฐ์ด์ ์ ์ธํด์ ํด๋นํ๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ ์ด์ง๋ฅผ ๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ก ์ง์ ํด์ ๊ฐ์ ์ฆ๊ฐ์ํจ๋ค.
HashMap
์ ์ ์ธํด์ ์คํจ์จ๊ณผ ์ธ๋ฑ์ค๋ฅผ ์์ผ๋ก ์ ์ฅํ๋ค.- ๊ฐ ์คํ ์ด์ง๋ง๋ค ๋์ ํ ์ฌ์ฉ์๋ ์ด์ ์คํ ์ด์ง์์ ํด๋ฆฌ์ดํ์ง ๋ชปํ ์ฌ์ฉ์๋ฅผ ๋นผ๋ฉด ๊ตฌํ ์ ์๋ค.
HashMap
์keySet
์List
์ ๋ฃ์ ํ,List
์.sort((o1, o2) -> HashMap.get(o2).compareTo(HashMap.get(o1))
๋ฉ์๋๋ก ๊ฐ์ ์ ๋ ฌํ ์ ์๋ค.
๊ฒฐ๋ก !
ํด๋น ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๊ธฐ์กด์ ํท๊ฐ๋ ธ๋ HashMap์ ์ฌ์ฉ๋ฒ๊ณผ ์ ๋ ฌ ๋ฐฉ๋ฒ์ ๋ค์ ์ตํ ์ ์์๋ค.
Share article