글 읽기 - 테스트 케이스

밑에 질문들을 보면서 테스트 케이스가 부족해서 찾아봤던 1인입니다.

저는 시간복잡도 O(n^2)으로 해결했고, 밑에 질문들에 다른 사람들이 올려주신 테스트 케이스 몇개 정리해 올려드립니다.

틀렸습니다 나온다면 아래 테스트케이스 4개중 몇 개는 다른 수를 출력할거라 예상됩니다.

testcase #1

3 4

1 2 1

-> 3 출력

testcase #2

3 2

1 3 1

-> 1 출력

testcase #3

5 11

1 2 3 4 5

-> 3 출력

testcase #4

3 4

0 1 1

-> 0 출력

자바의 보너스 시간 덕분에 O(N^2)로 통과되는 것이지, O(N) 풀이가 있는 이상 정해라고 보기는 어렵습니다. C나 C++로도 커팅으로 통과된 케이스들이 있는 것 같습니다만, O(N)으로 하면 자바로도 넉넉하게 세자릿수 MS에 풀 수 있는 문제입니다.

djm03178님 말씀대로 O(N)으로 해결하는 것이 가장 이상적인 방법이라고 생각합니다.

하지만 아직 제가 그정도 수준까진 되진 않는것 같습니다.

그렇기에 좀 더 효율적으로 구현하고자 열심히 공부중입니다.

좋은 말씀 감사합니다.

O(N)으로도 구현하도록 노력해보겠습니다.

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

Baekjoon Online Judge