프로그래머스 달리기 경주 풀이

안녕하세요, 오늘은 오랜만에 프로그래머스 코딩테스트 연습할겸 문제를 풀었는데, 달리 경주라는 문제였습니다.

처음 문제를 봤을때는 설명도 쉽고 풀이도 쉽다고 생각했는데, 많은 분들이 속도에서 제한이 많이 걸렸을꺼 같습니다 저 역시도 속도에서 정답 제출이 되지않아서 한참을 고민하다가 결국 다른분들의 풀이를 참고하긴 했습니다. 이러면서 시간복잡도를 다시 한번 공부하게 된 계기가 된거 같네요.

 

문제설명

제가 처음 풀었던 풀이부터 설명드리겠습니다.

 

 

 

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};     
                
        for(String calling : callings){            
            for(int i=0; i< players.length; i++){
                if(calling.equals(players[i])){
                    String tmp = players[i-1];
                    players[i-1] = players[i];
                    players[i] = tmp;
                    
                    break;
                }
            }
        }
               
        return players;
    }
}

처음에는 이런식으로 풀었습니다. 해설진이 부르는 선수 배열 callings를 for문을 돌리면서 선수 배열 players와 동일하면 배열 인덱스를 한칸씩 앞으로 당기는 방식으로 하였는데

저렇게 푸니깐 테스트 9~13번이 시간 초과로 실패가 나오더라고요 그래서 한참을 고민해봐도 속도 개선할 방법을 찾지못해서 처음에는 질문하기 쪽을 봤는데 다른 분들도 시간초과로 고민하시더라고요, 그래서 속도에 대한 부분을 찾다가 시간복잡도 O(n) 이런거 예전에 공부하거나 학교 수업들을때만 보고 신경 잘안썼는데, 이런 부분이 들어가더라고요 자료구조에서 그래서 수정한 코드는

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};     
        HashMap<String, Integer> playersHm = new HashMap<String, Integer>();
        HashMap<Integer, String> playersRankHm = new HashMap<Integer, String>();
        
        for(int i=0; i<players.length; i++){
            playersHm.put(players[i],i);
            playersRankHm.put(i,players[i]);
        }
        
        for(String calling : callings){
            int rank = playersHm.get(calling); // 등수
            String tmp = playersRankHm.get(rank-1); // 상위 사용자 명
            playersHm.put(calling, rank-1);
            playersRankHm.put(rank-1, calling);
            
            playersHm.put(tmp, rank);
            playersRankHm.put(rank, tmp);
        }
        
        answer = new String[players.length];
        for(int i=0; i<players.length; i++){
            answer[i] = playersRankHm.get(i);
            
        }
        
        return answer;
    }
}

위에 처럼 풀었습니다. HashMap으로 키값을 지정하였을 경우에는 인덱스 검색 속도가 훨씬 빠르다고 하더군요, 코딩테스트 연습하면서 속도에 대한 문제를 매번 체감하게 되면서 오늘은 시간복잡도에 대해서 다시 한번 알아야하는구나 라는것을 느끼게 되면서 다른분들도 한번 도움이 되었으면 좋겠다는 생각에 포스팅 하게되었습니다.