강의로 돌아가기
Jungkil Moon

효율성 질문 입니다.

ArrayList에서 지원하는 메서드 처리속도가 영향을 주고있는건가요?

작성중인 코드―Solution.java
1
2
3
4
5
6
7
8
9
10
11
import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        List<String> list = new ArrayList<String>(Arrays.asList(participant));
        for(String com : completion){
            //list.remove(Arrays.asList(participant).indexOf(com));
            list.remove(list.indexOf(com));
        }
        return list.get(0);
    }
}
1 개의 답변
Demi

본 문제는 시간복잡도 O(n) 또는 O( nlogn )이내로 풀어야하는 문제입니다. 그런데 작성하신 코드는 이를 초과하는 O(n2) 이네요.

자바 arraylist의 remove op는 시간복잡도가 O(n)이기 때문에, 로직을 변경해야 통과하실 수 있을거에요.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.