2024.04.28.일 달리기 경주
달리기 경주
문제 설명
얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.
단순한 자료구조 문제.
처음에는 그냥 값의 index를 알 수 있는 자료구조를 사용해서 호출이 될 때마다 순서만 바꿔주면 끝 아닌가? 생각해서
List를 사용해서 구현했다. 내친김에 자주 사용하던 C#말고 Java를 사용해 봤다.
import java.util.LinkedList;
class Solution {
public String[] solution(String[] players, String[] callings) {
String[] answer = new String[players.length];
LinkedList<String> ranking = new LinkedList<String>();
for(var player : players)
{
ranking.add(player);
}
for(var calling : callings)
{
int index = ranking.indexOf(calling);
String prevFront = ranking.get(index-1);
ranking.set(index-1,calling);
ranking.set(index,prevFront);
}
answer = ranking.toArray(new String[players.length]);
return answer;
}
}
엣
LinkedList의 get()과 set()의 시간복잡도는 O(n)이다. ArrayList로 바꾸는게 맞다고 생각을 해봤지만 결국 Index의 값을 알아야 하기에 (앞에 어떤 요소가 들어있는지 알기 위해) indexOf()메서드는 사용해야한다. indexOf()의 시간복잡도는 LinkedList나 ArrayList나 둘다 O(n)이여서 결국
자료구조를 바꿔서 생각해봐야 한다.
잠깐 생각해봐도 제일 적절한 것은 검색과 수정에 걸리는 시간복잡도가 O(1)인 Dictionary(Map)
HashMap을 사용해 구현해 봤다.
import java.util.Collection;
import java.util.HashMap;
class Solution {
public String[] solution(String[] players, String[] callings) {
String[] answer = new String[players.length];
HashMap<String,Integer> ranking = new HashMap<String,Integer>();
HashMap<Integer,String> chainRank = new HashMap<Integer,String>();
int i=1;
for(var player : players)
{
ranking.put(player,i);
chainRank.put(i,player);
i++;
}
for(var calling : callings)
{
int index = ranking.get(calling);
String front = chainRank.get(index-1);
chainRank.put(index-1,calling);
chainRank.put(index,front);
ranking.put(calling,index-1);
ranking.put(front,index);
}
for(int j=0;j<players.length;j++)
{
answer[j] = chainRank.get(j+1);
}
return answer;
}
}
HashMap을 하나만 만들어서 하려다가 callings에서 주어지는 calling 문자열(Key값)을 사용해 해당 플레이어의 순위를 바로 알 수 있다. 하지만 바로 앞의 플레이어를 구하기 위해서는 마찬가지로 O(n)의 검색 과정을 수행해야 하기에 (하나만 가지고는 검색을 처음부터 끝까지 다 해야 할 수 밖에 없기에) HashMap을 하나 더 만들어서 한번 더 각 플레이어 끼리 매핑을 해 줬다.
잘 된다..
다 풀고 생각해보니 굳이 HashMap을 하나 더 만들지 말고 배열에다가 했어도 되겠다 싶었다.
import java.util.Collection;
import java.util.HashMap;
class Solution {
public String[] solution(String[] players, String[] callings) {
String[] answer = new String[players.length];
HashMap<String,Integer> ranking = new HashMap<String,Integer>();
int i=0;
for(var player : players)
{
ranking.put(player,i++);
}
for(var calling : callings)
{
int index = ranking.get(calling);
String front = players[index-1];
players[index-1] = calling;
players[index] = front;
ranking.put(calling,index-1);
ranking.put(front,index);
}
for(int j=0;j<players.length;j++)
{
answer[j] = players[j];
}
return answer;
}
}
쓸데없는 HashMap 지우고 다시 ..
잘 된다...레벨 1 들이라 그런가 간단히 심심풀이로 풀 만하다.