1 분 소요

해시맵 문제

문제링크

풀이 접근

  1. 그냥 딱 봤을 때 링크드 리스트 문제라고 생각했고 시간복잡도도 O(n*m) 이라서 충분히 통과할 줄 알았다.
    1. n = players , m = callings
  2. 근데 아래와 같이 통과를 하지 못 했다.

구현 코드 (실패)

import java.util.Arrays;
import java.util.LinkedList;

class Solution {
    public String[] solution(String[] players, String[] callings) {

    LinkedList<String> linkedList = new LinkedList<>(Arrays.asList(players));
    for (String s : callings){
      if(linkedList.contains(s)){
        // 해당 요소의 인덱스를 찾음
        int index = linkedList.indexOf(s);
        // 해당 요소를 제거하고, 다시 그 앞에 삽입하여 위치 변경
        linkedList.add(index - 1, linkedList.remove(index));
      }
    }
    return linkedList.toArray(new String[0]);
  }

}

원인

LinkedList 에서 contains() 및 indexof() 는 각각 O(n) 시간 복잡도를 갖는다. 여기서 HashSet을 사용한다면 이 부분을 O(1) 로 줄일 수 있다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        LinkedList<String> linkedList = new LinkedList<>(Arrays.asList(players));
        Set<String> playerSet = new HashSet<>(Arrays.asList(players)); 
        // HashSet으로 players 배열의 요소를 저장

        for (String s : callings) {
            if (playerSet.contains(s)) { 
            // O(1) 시간 복잡도로 요소의 존재 여부 확인
                // 해당 요소의 인덱스를 찾음
                int index = linkedList.indexOf(s);
                // 해당 요소를 제거하고, 다시 그 앞에 삽입하여 위치 변경
                linkedList.add(index - 1, linkedList.remove(index));
            }
        }
        return linkedList.toArray(new String[0]);
    }
}

예상대로 줄긴 했지만 링크드 리스트보다 효율적인 자료구조를 사용해서 풀어야하는데 해시맵 밖에 생각이 안났다.
처음에 해시맵을 생각하기는 했었지만 복잡해질 것 같아서 선택을 안했는데 시간도 다 써서 다른 사람은 어떻게 해결했는지 확인해 봤다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        int numOfPlayers = players.length;
        Map<String, Integer> ranking = new HashMap<>();
        
        for (int i=0; i<numOfPlayers ; i++) {
            ranking.put(players[i], i);
        }
        

        
        //경주 진행
        for (String player : callings) {
            //1) player의 이름에 해당하는 value를 저장한다. 
            int playerRanking = ranking.get(player);
            
            //2) player보다 앞에 있는 사람을 발견하고, value를 변경함
            String frontPlayer = players[playerRanking-1];
            
            ranking.replace(frontPlayer, playerRanking);
            players[playerRanking] = frontPlayer;
            
            //3) player의 랭킹을 앞으로 변경함.
            ranking.replace(player, playerRanking-1);
            players[playerRanking-1] = player; 
        }
        
        return players;
    }
}
  • hashMap에 replace 메소드를 사용해서 해결

    정리

  • hashMap에 대해서 잘 안다고 생각했는데 replace를 오늘 처음 알게 되었다.
  • 다른 사람이 풀어놓은 답도 대충 보고 안다고 생각하지 말고 자세히 봐야겠다.

댓글남기기

참고