adamdoha   3년 전

예를 들어 다음과 같은 데이터가 들어올 때 TLE를 받는 것이 타당하다고 느끼는 코드가 AC를 받습니다.

즉, n>=15000 인 데이터가 부족하다고 느껴집니다.

[채점번호] 23044230

adamdoha   3년 전

위의 데이터를 만드는 코드를 첨부합니다.

djm03178   3년 전

코드를 공개하지 않으셔서 정확히 어떤 로직으로 되어있는지는 모르겠으나, 요즘 컴퓨터의 속도를 감안한다면 단순 연산으로 10억 ~ 20억 번의 연산이 가능하기 때문에 상수만 작다면 N^2이 통과되는 것도 이상하지 않습니다.

adamdoha   3년 전

List로 풀이하여 AC를 받은 코드입니다.

자바 내부 메서드에서 indexOf의 코드는 다음과 같이 순차 탐색으로 구현되어 있습니다.

public int indexOf(Object o) {
    if (o == null) {
        for(int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

위와 같은 데이터가 들어온다면 50000*50001/2 번의 연산을 통해 index를 리턴하게 됩니다.

djm03178   3년 전

현재 얼마나 강력한 데이터가 들어있는지는 모르겠지만, 저 반복문은 사실상 있을 수 있는 가장 단순한 형태에 속하고, 루프가 도는 총 횟수도 N^2/2번 정도에 불과해서 최악의 경우에도 지금 받은 시간 정도 나오는 게 맞는 것 같습니다.

adamdoha   3년 전

그렇군요. 몰랐던 사실입니다.

지금까지 항상 시간복잡도를 연산량에 초점을 맞춰서 생각했습니다. 알려주셔서 감사합니다.

그리고 답변해주셔서 감사합니다.

jh05013   3년 전

BOJ Stack에서 직접 돌려 보니 2900 ms가 걸렸습니다.

시간 초과가 안 나더라도, 수행 시간이 유의미하게 증가하면 데이터 추가 요청이 승인되기도 합니다.

adamdoha   3년 전

답변 감사합니다 :)

startlink   3년 전

재채점했습니다.

댓글을 작성하려면 로그인해야 합니다.