달리기 경주 (자바)

김재현·2023년 12월 8일
0

알고리즘 풀이

목록 보기
46/90

문제

오답 (시간초과)

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

        return players;
    }
}

쉽네..? -> 시간초과

calling된 선수의 이름과 비교하여 바로 players 배열을 교체하니 시간초과가 발생했다.

수정된 정답 코드

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        // 플레이어 랭킹을 맵으로 만듦
        Map<String, Integer> playerRankingMap = new HashMap<>();
        for (int i=0;i< players.length;i++) {
            playerRankingMap.put(players[i], i+1);
        }

        // 이름 부르면 랭킹을 바꿈
        for (String calling : callings) {
            int calledPlayerRanking = playerRankingMap.get(calling);
            String frontPlayer = players[calledPlayerRanking-2];

            // map의 랭킹을 바꿈
            playerRankingMap.replace(frontPlayer,calledPlayerRanking);
            playerRankingMap.replace(calling,calledPlayerRanking-1);

            // players 배열의 순서를 바꿈
            players[calledPlayerRanking-2]=players[calledPlayerRanking-1];
            players[calledPlayerRanking-1]=frontPlayer;
        }

        return players;
    }
}

그렇다면 맵으로 바꾸며 미리 랭킹을 넣어놓는다면 이중for문을 사용하지 않을 수 있겠다고 생각했다.

맵의 replace라는 메서드가 있다는 것을 검색을 통해 알아내고 사용했다.

다른 사람 풀이

import java.util.HashMap;

public class Solution {
    public String[] solution(String[] players, String[] callings) {
        int n = players.length;
        HashMap<String, Integer> indexMap = new HashMap<>();

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

        for (String calling : callings) {
            int idx = indexMap.get(calling);
            if (idx > 0) {
                String temp = players[idx - 1];
                players[idx - 1] = players[idx];
                players[idx] = temp;

                indexMap.put(players[idx - 1], idx - 1);
                indexMap.put(players[idx], idx);
            }
        }

        return players;
    }
}

문제 풀이는 나와 동일하다.
다른 점은, 문제의 조건에 보면 1등은 이름이 불리지 않는다는 것이 있는데, 이분은 그것을 모르고 if문을 통해서 그 조건을 걸러줬다.

profile
I live in Seoul, Korea, Handsome

0개의 댓글