[99club/TIL] 1주차 - 화요일 TIL(Today I Learned)

안녕하세요! delay100입니다. 

잠을 자고 일어나니,, 오늘의 코딩 문제도 출제해주셨더라구요! (월, 목에만 문제를 주시는 줄 알았는데 아니어서 넘 좋았습니다..ㅎㅎ)

---

2일차에 주어진 미들러의 문제는 아래와 같습니다.

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

프로그래머스

 

1. 시간초과 

사실 이 코드를 작성할 때, 시간초과(2중 for문으로 구현)가 날 것 같았습니다.

구현 방법은 2중 for문을 이용해 현재 호명된 사람의 트랙에서의 현 위치를 찾아내고 앞 사람과 자리를 바꾸는 방법이었습니다.

그러나 일단 당장 생각나는 구현방법이어서 해보았고, 정말 시간초과가 났습니다.

시간복잡도가 O(n^2)이기 때문인듯 싶습니다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        
        for(int i=0; i<callings.length; i++) {
            
            // 현재 calling된 사람 이름의 위치를 알아냄
            for(int j=0; j<players.length; j++) {
                if(players[j].equals(callings[i])) {
                    String s = players[j-1];
                    players[j-1] = players[j];
                    players[j] = s;
                    break;
                }
            }
        }
                   
        for(int i=0; i<players.length; i++) {
            answer[i] = players[i];
        }
        
        return answer;
    }
}

2중 for문 이용 - 시간초과

 

2. 문제 해결 

시간복잡도를 O(n)으로 줄이기 위해 HashMap을 도입했습니다.

입출력 예시

입력으로 들어오는 players에 대해 hashmap을 만들었습니다.

이 hashmap으로 현재 이름 불린 player가 몇 등인지 바로 알 수 있게 합니다.

Map<String, Integer> map = new HashMap<String, Integer>(); // 이름 별 랭크를 관리하는 map 생성

map의 초기값은 "이름, 등수"로 해주었습니다. 예를 들어 아래와 같습니다.

// map의 초기값
// 이름, 등수
mumu, 0
soe, 1
poe, 2
kai, 3
mine, 4

players 배열과 동일하게 map을 관리합니다.

players 배열은 등수에 따라 이름을 알 수 있게 하고, map은 이름에 따라 등수를 알 수 있게 합니다.

이 작업을 통해 O(n)으로 시간복잡도를 줄일 수 있습니다.

상세 코드는 주석으로 추가 설명을 두었습니다. 정답 코드는 아래와 같습니다.

import java.io.*;
import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> map = new HashMap<String, Integer>(); // 이름 별 랭크를 관리하는 map 생성
        
        // map에 초기값 할당
        for(int i=0; i<players.length; i++) {            
            map.put(players[i], i);
        }

        // callings 배열을 하나씩 확인
        for(int i=0; i<callings.length; i++) {
            String callingName = callings[i]; // 현재 호명된 사람이 누군지 저장
            int callingRank = map.get(callingName); // 현재 호명된 사람의 현재 랭크를 찾음
            map.replace(callingName, callingRank - 1); // 현재 호명된 사람의 랭킹을 하나 줄임
            
            String overtakingName = players[callingRank - 1]; // 현재 추월당한 사람의 이름을 찾음
            map.replace(overtakingName, callingRank); // 추월당한 사람의 랭킹을 호명된 사람의 랭킹으로 바꿈 (서로 자리 교체)
            
            // players 배열도 map과 동일하게 구성되게 바꿔줌
            players[callingRank - 1] = callingName; 
            players[callingRank] = overtakingName;
        }   
        
        return players;
    }
}

---

+ 비기너 문제

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

프로그래머스

 

+ 챌린저 문제

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

프로그래머스

---

백준으로만 코딩테스트를 준비해서 실제 코딩테스트 할 때 적응이 안 된 점이 많이 있었는데,

프로그래머스랑 점점 친해지고 있는 것 같아 기쁩니다!