์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์คํจ์จ
์คํจ์จ ์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋ ๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์ค
programmers.co.kr
๐ ๋ฌธ์ ์ค๋ช
์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋ ๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์คํ ์ด์ง ์ฐจ์ด๊ฐ ๋๋ฌด ํฐ ๊ฒ์ด ๋ฌธ์ ์๋ค.
์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํ ๊น ๊ณ ๋ฏผ ํ ๊ทธ๋ ๋ ๋์ ์ผ๋ก ๊ฒ์ ์๊ฐ์ ๋๋ ค์ ๋์ด๋๋ฅผ ์กฐ์ ํ๊ธฐ๋ก ํ๋ค. ์ญ์ ์ํผ ๊ฐ๋ฐ์๋ผ ๋๋ถ๋ถ์ ๋ก์ง์ ์ฝ๊ฒ ๊ตฌํํ์ง๋ง, ์คํจ์จ์ ๊ตฌํ๋ ๋ถ๋ถ์์ ์๊ธฐ์ ๋น ์ง๊ณ ๋ง์๋ค. ์ค๋ ๋ฆฌ๋ฅผ ์ํด ์คํจ์จ์ ๊ตฌํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ผ.
- ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค.
- ์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์ ์ฒด ์คํ ์ด์ง์ ๊ฐ์ 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]
๐คจ ๊ณ ๋ฏผ
- ์คํ ์ด์ง ํด๋ฆฌ์ดํ ์ ์ ์ ์คํจํ ์ ์ ๊ตฌ๋ถ
- ๋ฐ์ดํฐ ๊ฐ์ฒด ์ ํ.
- ๋ญํฌ ์ ์ฉ ํ์ฌ ๋ต์์ง ์ธํ
๐ป ์ฝ๋ฉ
1์ฐจ ์ ์ถ.
import java.util.HashMap;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
HashMap<Integer,Double> map = new HashMap<Integer,Double>();
// N๊ฐ์ ์คํ
์ด์ง ๋งํผ ๋๋ for๋ฌธ
for (int i = 1; i < N+1; ++i) {
int fail = 0;
int succ = 0;
// ๋์ ์ค์ธ ์ ์ ์์ ์คํ
์ด์ง ๋งํผ ๋๋ for๋ฌธ
for(int stage : stages){
// ์ ์ ์ ์คํ
์ด์ง๊ฐ i์ ์คํ
์ด์ง๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค๋ฉด ์ฑ๊ณต์นด์ดํธ++
if ( i <= stage) succ++;
// ์ ์ ์ ์คํ
์ด์ง๊ฐ i์ ์คํ
์ด์ง์ ๊ฐ๋ค๋ฉด ์คํจ ์นด์ดํธ++
if ( i == stage) fail++;
}
double failure = 0.0;
// 0์ผ๋ก ๋๋์ด ์ง๋ ๊ฒฝ์ฐ๊ฐ ์๊ฒ ํ๊ธฐ ์ํด ์ ํจ์ฑ ๊ฒ์ฌ๋ฅผ ํ๊ณ , ์คํจ์จ์ ๊ณ์ฐํ๋ค.
if(succ!=0 && fail!=0) {
failure = (double)fail/(double)succ;
}
// ์คํ
์ด์ง i ๋ฒ๊ณผ, ์คํจ์จ์ map์ ๋ด๋๋ค.
map.put(i, failure);
}
// ์ ๋ ฌํ๊ธฐ ์ํด ์คํ
์ด์ง N๊ฐ ๋งํผ ๋๋ outer i for
for (int i = 0; i < N; i++) {
// max๊ฐ ์ฒ๋ฆฌ๋ฅผ ์ํด i๋ฃจํ ๋๋๋ง๋ค max:-1, idx=0 ์ด๊ธฐํ
double max = -1;
int idx = 0;
// map์ keySet๋ฉ์๋๋ฅผ ํธ์ถํ์ฌ ์กด์ฌํ๋ mapKey๋งํผ ๋๋ inner for
for(Integer mapKey : map.keySet()){
// max๊ฐ๊ณผ value๊ฐ์ ๋น๊ตํ ๊ฐ ์ธํ
if(max < map.get(mapKey)){
max = map.get(mapKey);
idx = mapKey;
}
}
// ๋ต์์ง์ธํ
.
answer[i] = idx;
// ์ธํ
ํ idx์ ๊ฑฐํ๋ค.
map.remove(idx);
}
return answer;
}
}
๐ ์ฑ์
โฑ ์์์๊ฐ ๋ฐ ํ๊ธฐ
์ฝ 8์๊ฐ.
๋ด ์์ค์ ์ ์ ์์๋ ๋ฌธ์ . ์๊ฐ๋ณด๋ค ๋๋ฌด ์ด๋ ค์ ๋ค.
๋จ์ํ๊ฒ ์คํจ์จ ๊ตฌํ๋ ๊ฒ๋ง ์ผ๋ก ๋๋๋ ๊ฒ์ด ์๋์๊ณ , ๋ด๊ฐ ์์ฑํ ์ฝ๋๊ฐ ์ฑ์ ๊ฒฐ๊ณผ์์ ํจ์จ์ฑ์ด ์ด๋ ๊ฒ ๋จ์ด ์ง ์ค์ ๋ชฐ๋๋ค. ์ง๊ธ ์ฌ๊ธฐ์์ ์ฝ๋๋ฅผ ์ด๋ป๊ฒ ๋ ๊ฐ์ ํด์ผ ํ ์ง ๊ฐ์ด ์์กํ์ง๋ง,
๊พธ์คํ ๋ ธ๋ ฅํ๋ค ๋ณด๋ฉด ๊ฐ์ ํด์ผ ๋ ๋ถ๋ถ์ ์ฐพ๊ฒ ๋ ์ ์๋ค๋ ๊ฐ๋ฅ์ฑ์ ๋ฏฟ์ด์ผ๊ฒ ๋ค.
๋๋๊ธฐ ์ฐ์ฐ์ด ๋ค์ด๊ฐ๋ ๋ถ๋ถ์๋ 0์ฒดํฌ๋ฅผ ๋ฐ๋์ ํด์ค์ผํ๋ค๋ ์ , ๊ฐ์ฒด๋ณ ๋ญํฌ ์ฒ๋ฆฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋ณต์๋ฌํ์ฌ ๋ด ๊ฒ์ผ๋ก ๋ง๋ค์ด์ผ๊ฒ ๋ค๋ ์๊ฐ์ด ๋ ๋ค.