[JAVA] 완주하지 못한 선수 - ArrayList

마라톤 완주는 힘들어요. (Photo by Snapwire)

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

생각 과정

- 완주자, 참가자 한명씩 이름을 비교하려면 시간복잡도가 O(n^2)이나 된다.

- 순회를 최대한 적게 하는 방법=> 이름 첫글자로 사전을 만들어서 비교하자

 => 이차원 배열로 만들었지만 요소 삭제/추가하는 과정에서 한번 순회가 필요함.

- ArrayList 배열로 만들면 추가적인 for문 없이 사전을 간편하게 관리할 수 있음.

- Dynamic array라 순회 전 해당 사전이 비었는지 확인할 때 비용소모가 Array에 비해 훨씬 적기 때문에 선택. 

 

구현

import java.util.ArrayList;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        //이차원배열 선언, 최악의 경우 완주자 수만큼 알파벳 사전이 채워질 수 있음.
        ArrayList dict[] = new ArrayList[26];
        for(int i=0; i<26; i++) {
           dict[i] = new ArrayList<String>(); // 배열에 Class를 지정하여 ArrayList 저장
        }
        
        int index = 0;
        
        //마라톤 완주자 리스트를 순회하며 완주자 사전에 추가
        for(int i=0;i<completion.length;i++){
            //완주자 이름의 첫글자를 따서 해당 알파벳의 사전에 넣기
            dict[(int)completion[i].charAt(0)-97].add(completion[i]);
        }
        
        //마라톤 참가자 리스트를 순회하기
       for(int i=0;i<participant.length;i++){
            index = (int)participant[i].charAt(0) - 97;
            //참가자 이름의 첫글자로 사전 찾기
            if(dict[index].size() > 0){
                //이름이 있을 경우 삭제하고 객체 리턴
                if(!dict[index].remove(participant[i])){
                    //이름 없을 경우 종료
                    answer = participant[i];
                    break;
                }
            }
            else{
                //사전에 이름이 없을 경우
                answer = participant[i];
                break;
            }
        }
        
        return answer;
    }
   
}

 

결과

Time Overflow?

- 왜 실패했을까?

 => 최악의 경우: 참가자 전원 이름의 첫글자가 같을 때 O(2n)의 시간복잡도 발생.

 => ArrayList의 메소드 자체의 비용소모가 컸을 경우

 

<참고>

 

- 문자열의 첫 번째 글자 가져오기

String.charAt(index)

- ArrayList 배열

1) 선언

ArrayList<ClassName> arr[] = new ArrayList[number];

2) 추가

arr.add(value);

3) 삭제

arr.remove(index); => return target object

arr.remove(object); => return true if target exists

4) 조회

arr.get(index); => return object

5) 요소 개수

arr.size(); => return int

6) 값 존재 여부

arr.contain(value); => return true/false

 

코드리뷰는 환영입니다^^