코딩테스트 시리즈에는 문제를 해결하다 막힌것, 중요하다고 생각하는 문제 등 복습이 필요한것들을 포스팅하기 위해 만들었습니다.
나머지 문제들은 https://github.com/dev-h99www/codingtest 에 올릴 생각입니다.

달리기 경주

2023-07-04

String 배열에 경주마들의 이름이 저장되어있고, 인덱스가 현재 순위를 의미한다.
callings는 경주마가 호명된 순서대로 경주마의 이름이 저장되어 있는 String 배열이다.

예를들어 a, b, c의 경주마가 달리고있는데 b가 호명되면 b가 앞의 말을 추월했다는 뜻이고,ㅈㅈ
그러면 현재 순위는 b, a, c 이다.

문제 해결을 위한 내가 생각한 순서도는 다음과 같다.

아이디어를 바탕으로 코드를 짰다.

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

결과는 다음과 같다

시간 복잡도를 생각해보니 최대 O($n^2$)이다.

지금 당장 생각나는 해결법은 탐색부분과 스왑부분에서 성능이 좋은 메소드를 제공해주는 자료구조를 사용하는 것인데, 스왑부분에선 더 시간을 유의미하게 줄일 수 있을지 모르겠다.

문제 해결을 위해 배열을 사용해 index를 탐색하는 것 보다 더 빠른 방법이 없을지 다른 자료구조를 사용하는 것에 대해 고민해봐야겠다.

해결

2023-7-8

이전에는 callings를 순차적으로 조회하며 매번 callings[i]의 값이 몇위인지 조회하고, 조회한걸 토대로 players를 갱신해주었다.

그래서 callings 반복 * players 순위조회의 시간이 걸렸는데

순위를 따로 저장해두면 callings 반복에서 나온 선수이름이 몇위인지 바로 비교해서
players를 갱신할 수 있다.

해결하게된 계기는, 탐색을 빨리할 수 없을까 고민하다 Map을 사용하는건 어떨까 생각하고 있었다.그러던중 면접때 알고리즘테스트를 봤는데, 그때 피드백받은 부분이 매번 값을 구하지 말고, ArrayList에 차곡차곡 저장해놓으면 매번 n번씩 반복하는걸 안할 수 있다는 것이었다.
Map에 rank를 저장해두고, 참조하면 for문안에서 rank를 구하던 과정을 줄일 수 있다는 생각에 코드를 작성하고, 통과할 수 있었다.

        Map<String, Integer> rankMap = new HashMap<>();

        for(int i = 0; i < players.length; i++) {
            rankMap.put(players[i], i);
        }

        for(String calling : callings) {
            //호명될 선수의 랭킹
            int rank = rankMap.get(calling);

            //랭킹으로 호명된 선수와, 추월당한 선수 저장
            String passed = players[rank - 1];
            String called = players[rank];

            //맵에 랭크 변경
            rankMap.put(passed, rank);
            rankMap.put(called, rank - 1);

            //원래 배열에 순위 반영
            players[rank] = passed;
            players[rank - 1] = called;
        }