240319 TIL - 달리기경주

오늘은 프로그래머스 알고리즘 풀이 달리기 경주를 풀어보았다. https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

이 문제는 현재 순위를 나타내는 배열과 앞의 한 사람을 추월한 사람의 이름이 담긴 배열이 주어지면 최종 순위를 반환해야 하는 문제이다.

 

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        Map<String, Integer> rank = new HashMap<>();
        
        for(int i=0; i<players.length; i++) {
            rank.put(players[i], i);
            answer[i] = players[i];
        }
        
        for(String calling : callings) {
            String passed = answer[rank.get(calling) -1];
            int callingRank = rank.get(calling);
            
            rank.put(passed, callingRank);
            answer[callingRank-1] = calling;
            
            rank.put(calling, callingRank-1);
            answer[callingRank] = passed;
        }
        
        return answer;
    }
}

처음에는 이중 for문을 통해 players 배열의 순위를 바꾸어주었는데 주어진 문제는 연산해야하는 크기가 큰 케이스가 있어서 시간 초과문제로 실패를 했었다.

그래서 이중for문을 사용할 수 없는 문제인 것이라고 판단하고 map과 변수의 값을 서로 바꿔주는 로직을 생각해서 위와 같이 풀이를 하였더니 시간안에 정답을 제출 할 수 있었다. map을 사용할때 key값을 어떻게 찾아와야하는지를 처음에 생각하지 못했는데 생각을 해보니 callings배열에서 key값을 찾고 players배열을 통해 또 다른 key값을 찾을 수 있어서 해결 할 수 있었다. 

 

이제는 제한사항을 보면서 시간복잡도도 생각을 해야 하는 경우가 많아지고 또 이제는 map을 기본정도는 사용할 수 있게 된 것 같아서 그동안 풀리지않았던 알고리즘문제들이 조금씩 풀리면서 기분이 좋다. 이제 구현 문제는 적절한 자료구조를 통해 어느정도 풀이가 가능하지만 dfs라던가 재귀함수 같은 알고리즘을 사용해야하는 문제들이 나오고 있어서 이부분도 공부를 해야할 것 같다.