[PG/프로그래머스/Java] 달리기 경주

문제는 프로그래머스에 가서 읽어보자.

https://school.programmers.co.kr/learn/courses/30/lessons/178871

정답여부: 정답
시간: 20분

Feedback

Map을 이용하는 전형적인 대표문제 중 하나. 하지만, 생각보다 코테로 나오면 생각의 늪에 빠질 확률이 큰 문제이다. 기준을 하나로 확실하게 잡아놓고 , 천천히 쭉 풀어나가는게 중요함.

• 선형 탐색으로 풀어나가면 , O(NM)이므로 50이므로, 선형탐색은 불가능
• 탐색을 줄이는 방법은 탐색 자체를 빠르게 하던가, 데이터를 이쁘게 저장하면됨.
  • 탐색을 빠르게 한다 → 이진탐색
  • 데이터를 이쁘게 저장한다 → 자료구조(Map,Array 등을 응용)
• 2가지 정도를 먼저 생각했음.
  • 선형탐색이 안된다 → 이진탐색
  • Key-value의 Map구조를 이용할 수 있을까?
• 이진탐색으로 먼저 풀어봤는데, 생각해보니 특정 기준이 되는 값이 애매했음. 이진탐색은 항상 정렬된 상태에서, 특정 기준으로 탐색을 함. (기준이 없기 때문에 탐색을 할 수 없음)
  • 심지어, 내가 구현한다고 구현한건 이분탐색이 아님. (이분 탐색은 기준을 정해서 1개가 남을 때 까지 탐색을 해야함)

지금 위 문제가 껄끄러운 이유가, 입력값으로 이름 을 받기 때문임. 이름을 통해서 등수를 알아내기 위해서는 탐색을 하던가, 이름을 key로 등수를 value로 저장된 Map이 필요함.

수정 전 코드

이진 탐색한답시고 이상한 코드를 짜버렷다.

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        //binary Search 
        for(int i=0;i<callings.length;i++){
            binary_search(players,callings,i);
        }
        answer = Arrays.copyOf(players,players.length);
        return answer;
    }
    
    public void binary_search(String[] players,String[] callings,int idx){
            int start = 0;
            int end = players.length-1;
            
            while(start<end){
                int mid = (start + end)/2;
                if(players[mid] == callings[idx]){
                    //swap
                    swap(players,mid,mid-1);
                    System.out.println("players"+players[mid],)
                    return;
                }
                start = mid;
            }
    }
    
    public <T> void swap(T[] a,int f,int s){
        T temp;
        temp = a[f];
        a[f] = a[s];
        a[s] = temp;
    }
}

수정 후 코드

import java.util.HashMap;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        
        HashMap<String,Integer> nameKeyRanking = new HashMap<>();
        
        for(int i=0;i<players.length;i++){
            nameKeyRanking.put(players[i],i);
        }
        for(String calling : callings){
            //기존의 등수 
            int curRank = nameKeyRanking.get(calling);
            int newRank = curRank-1;
            //Map Update
            nameKeyRanking.put(calling,newRank);
            nameKeyRanking.put(players[newRank],curRank);
            //swap
            players[curRank] = players[newRank];
            players[newRank] = calling;
        }
        return players;
    }
}