fman1335   1년 전

제가 푼 건 O(N^3)인 거 같은데 O(N)으로 어떻게 풀 수 있을까요?..
메모리 초과가 나네요. 

chldn323   1년 전

작성하신 코드는 O(n^2)이고 시간 안에 통과 가능합니다.

단, HashSet로 중복을 처리하려면 경우의 수가 다 들어가야 돼서 메모리 초과가 발생합니다.

for문이랑 if문의 조건을 잘 조절해서 중복이 안 생기게 하고 HashSet이 아니라 count만 늘리는 식으로 해보세요.

fman1335   1년 전

넵 감사합니다. sortedBy 때문에  O(n^3)라고 생각했는데, 이건 제외하고 for loop 2개로만 판단하면 되는 걸까요?

fman1335   1년 전

추가로 밑에 질문 보니 O(N)으로 해결할 수 있다는데, 이건 어떤 방식으로 접근하면 좋을까요?

chldn323   1년 전

sort는 대부분 nlogn이라서 n^3이 넘을 수도 있지만 여기선 정렬할 원소가 3개 고정이라서 괜찮습니다.

O(N)으로 하는 건 저도 잘 몰라서 찾아봤습니다.

https://gumgood.tistory.com/16...   https://www.acmicpc.net/source...

이런 식으로 하면 될 거 같네요.

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