[JAVA] indexOf, contains의 시간복잡도 문제(미해결)

궁금증

: 알고리즘 문제를 풀다보면 주어진 조건이 시간 복잡도를 제한한다는 것을 암시하는 경우가 있다.

: 때문에 이중 반복문으로 문제를 풀어야하지만 이중 반복문을 못 쓸 때가 있다.

: 그런데 이런 경우에 indexOf() 메서드나 contains() 메서드를 문제가 해결된다.

: indexOf(), contains() 모두 다 메서드 내부적으로 순회를 해야하는 것이라고 생각했고 내가 아는 한에서는 시간 복잡도 또한 O(n)이라고 알고 있다.

: 그런데 왜 해결되는 것일까??

출처: https://allo-ew.tistory.com/m/69

 

List.indexOf( )

: 인자로 주어진 값이 List에 존재하면 해당 인덱스를, 존재하지 않으면 -1을 반환하는 메서드

: indexOf 메서드를 조건식의 조건으로 쓰는 경우, IDE는 보통 contains( ) 메서드를 쓰길 권유한다.

List.contains( )

: 인자로 주어진 값이 List에 존재하면 true, 존재하지 않으면 false를 반환하는 메서드

: contains 메서드 내부에는 indexOf 메서드가 존재한다.

: contains 메서드는 indexOf 메서드를 이쁘게 포장한 메서드이다.

 

List.indexOf( ) 내부

//indexOf 메서드 내부
public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
//elementData : The size of the ArrayList (the number of elements it contains).

 

List.contains( ) 내부

//contains 메서드 내부
public boolean contains(Object o) {
        return indexOf(o) >= 0;
}

 

해결

: 아직 잘 모르겠다.

: 구글링의 대부분 내용은 시간 복잡도가 O(mn)이 되어서 해결되는 것이라고 하는 게 많은데, 적합한 이유라고 생각하지 않는다.

: 왜냐하면, 나도 이중 반복문을 사용할 때, 외부 반복문과 내부 반복문의 사이에 중간 탈출이 가능한 지점이 있었는데 문제가 풀리진 않았었다.

: 나의 코드에서는 이중 반복문 중 내부 반복문을 순회한 후 조건문(if)로 중간 탈출구가 있었는데, 내부 반복문 위 혹은 조건문이 내부 반복문을 감쌌으면 indexOf와 같은 효과를 봤을 것 같다.

: 또한, 위 메서드들도 최악의 경우(끝까지 순회해야 하는 경우)는 O(n^2)이 될 것 아닌가.

: 근데 아직도 최악의 경우(끝까지 순회해야 하는 경우)에는 O(n^2)이 될 것이라 생각해서 명쾌하다고 느끼진 못한다. 아마 문제의 예시 입력 코드에 최악의 경우를 주지 않을 것 같다.

: 조금 더 조사할 필요가 있다.