โฐ๋ฌธ์
์์์๋ ๋งค๋ ๋ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ๊ฐ ์ด๋ฆฝ๋๋ค. ํด์ค์ง๋ค์ ์ ์๋ค์ด ์๊ธฐ ๋ฐ๋ก ์์ ์ ์๋ฅผ ์ถ์ํ ๋ ์ถ์ํ ์ ์์ ์ด๋ฆ์ ๋ถ๋ฆ ๋๋ค. ์๋ฅผ ๋ค์ด 1๋ฑ๋ถํฐ 3๋ฑ๊น์ง "mumu", "soe", "poe" ์ ์๋ค์ด ์์๋๋ก ๋ฌ๋ฆฌ๊ณ ์์ ๋, ํด์ค์ง์ด "soe"์ ์๋ฅผ ๋ถ๋ ๋ค๋ฉด 2๋ฑ์ธ "soe" ์ ์๊ฐ 1๋ฑ์ธ "mumu" ์ ์๋ฅผ ์ถ์ํ๋ค๋ ๊ฒ์ ๋๋ค. ์ฆ "soe" ์ ์๊ฐ 1๋ฑ, "mumu" ์ ์๊ฐ 2๋ฑ์ผ๋ก ๋ฐ๋๋๋ค.
์ ์๋ค์ ์ด๋ฆ์ด 1๋ฑ๋ถํฐ ํ์ฌ ๋ฑ์ ์์๋๋ก ๋ด๊ธด ๋ฌธ์์ด ๋ฐฐ์ด players์ ํด์ค์ง์ด ๋ถ๋ฅธ ์ด๋ฆ์ ๋ด์ ๋ฌธ์์ด ๋ฐฐ์ด callings๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๊ฒฝ์ฃผ๊ฐ ๋๋ฌ์ ๋ ์ ์๋ค์ ์ด๋ฆ์ 1๋ฑ๋ถํฐ ๋ฑ์ ์์๋๋ก ๋ฐฐ์ด์ ๋ด์ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- 5 ≤ players์ ๊ธธ์ด ≤ 50,000
- players[i]๋ i๋ฒ์งธ ์ ์์ ์ด๋ฆ์ ์๋ฏธํฉ๋๋ค.
- players์ ์์๋ค์ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- players์๋ ์ค๋ณต๋ ๊ฐ์ด ๋ค์ด๊ฐ ์์ง ์์ต๋๋ค.
- 3 ≤ players[i]์ ๊ธธ์ด ≤ 10
- 2 ≤ callings์ ๊ธธ์ด ≤ 1,000,000
- callings๋ players์ ์์๋ค๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๊ฒฝ์ฃผ ์งํ์ค 1๋ฑ์ธ ์ ์์ ์ด๋ฆ์ ๋ถ๋ฆฌ์ง ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
players | callings | result |
["mumu", "soe", "poe", "kai", "mine"] | ["kai", "kai", "mine", "mine"] | ["mumu", "kai", "mine", "soe", "poe"] |
์ ์ถ๋ ฅ ์ ์ค๋ช
์ ์ถ๋ ฅ ์ #1
- 4๋ฑ์ธ "kai" ์ ์๊ฐ 2๋ฒ ์ถ์ํ์ฌ 2๋ฑ์ด ๋๊ณ ์์ 3๋ฑ, 2๋ฑ์ธ "poe", "soe" ์ ์๋ 4๋ฑ, 3๋ฑ์ด ๋ฉ๋๋ค. 5๋ฑ์ธ "mine" ์ ์๊ฐ 2๋ฒ ์ถ์ํ์ฌ 4๋ฑ, 3๋ฑ์ธ "poe", "soe" ์ ์๊ฐ 5๋ฑ, 4๋ฑ์ด ๋๊ณ ๊ฒฝ์ฃผ๊ฐ ๋๋ฉ๋๋ค. 1๋ฑ๋ถํฐ ๋ฐฐ์ด์ ๋ด์ผ๋ฉด ["mumu", "kai", "mine", "soe", "poe"]์ด ๋ฉ๋๋ค.
๐กํ์ด
โญ์ฒ์ ์ ์ถ ์ฝ๋
class Solution {
public String[] solution(String[] players, String[] callings) {
String[] answer = new String[players.length];
for(int i=0; i<callings.length; i++){
for(int j=0; j<players.length; j++){
if(callings[i].equals(players[j])){
String tmp = players[j];
players[j] = players[j-1];
players[j-1] = tmp;
break;
}
}
}
for(int i=0; i<players.length; i++){
answer[i] = players[i];
}
return answer;
}
}
์ ์ถ์ ํ๋ฉด ํ ์คํธ9~13์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ๋ค.
callings์ ๊ธธ์ด๊ฐ 1,000,000์ด๋ผ ๋๋ฌด ๋ง์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. ์ด๋ฐ ๋ฐฉ์์ผ๋ก ํ๋ฉด O(N^2)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๊ฒ๋๋ค.
โญ์ ์ถ ์ฝ๋
import java.util.*;
class Solution {
public String[] solution(String[] players, String[] callings) {
Map<String, Integer> map = new HashMap<>(); // <์ ์๋ช
, ๋ฑ์>
for(int i=0; i<players.length; i++){
map.put(players[i], i);
}
for(String player : callings){
//๋ฑ์ ํธ์ถ
int rank = map.get(player);
//์ ์ ์ ํธ์ถ
String beforePlayer = players[rank-1];
//players ๋ฐฐ์ด ๊ฐฑ์
players[rank-1] = player;
players[rank] = beforePlayer;
//map ๊ฐฑ์
map.put(player, rank-1);
map.put(beforePlayer, rank);
}
return players;
}
}
Hash๋ก ํ๊ฒ๋๋ฉด O(N) ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๋๋ค.
์ฌ๊ธฐ์ ์ค์ํ ์ ์ map์ ์๋ ๋ฑ์์ players์ ์๋ ๋ฑ์๋ฅผ ๋ค ๋ณ๊ฒฝํด์ค์ผ ํ๋ค๋ ๊ฒ์ด๋ค.
์๋ํ๋ฉด callings๋ก ์์ฐจ์ ์ผ๋ก ๋์จ ์ ์A๋ฅผ map์์ ๊ฐ์ ธ์ค๊ณ A ๋ฐ๋ก ์ ๋ฑ์์ธ B๋ฅผ ๊ฐ์ ธ์ค๊ธฐ ์ํด players๋ฅผ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ map๊ณผ players๋ฅผ ๋ค ๋ณ๊ฒฝํด์ค์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค.
'๐ Algorithm > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Programmers] ํน์ดํ ์ ๋ ฌ(์๋ฐ) (1) | 2023.10.27 |
---|---|
[Programmers] ๋ฑ์ ๋งค๊ธฐ๊ธฐ(์๋ฐ) (0) | 2023.08.01 |
[Programmers] ์น์์ด(2)(์๋ฐ) (0) | 2023.06.12 |
[Programmers] ์ต์์ง์ฌ๊ฐํ(์๋ฐ) (0) | 2023.05.15 |
[Programmers] ์ด์ง์ ๋ํ๊ธฐ(์๋ฐ) (0) | 2023.04.25 |