park780172   4년 전

우선 제가 첨부한 코드는 정답 코드입니다.

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

정답 스포주의

우선 제가 생각한 풀이는 집합 개념이라고 생각하시면 될 것 같습니다.

답 = 누적된 총 크기의 합 - (자신의 컬러에 맞는 크기의 합 + 자신하고 같거나 큰 크기들의 크기의 합) + 자신과 똑같은 칼라에서 자신의 크기와 같거나 그 이상의 크기들의 합

우선 제 코드가 O(n2)이라고 생각하여 시간 초과가 발생할 것 같았는데 통과가 돼서 질문드려봅니다.

제 생각에는 60 ~ 66번 째 줄에서 벡터 v에서 하나 씩 꺼내므로 n이고,

마찬가지로 64번 째 줄의 same() 함수에서 또 다시 for문을 통해 same_color[c]에서 하나 씩 꺼내므로 n이라서 O(n2)이라고 생각했었습니다.

심지어 same_color[c]는 누적합을 사용하지 않았습니다.

제가 생각한 것이 맞는지 궁금합니다.

koosaga   4년 전

같은 색깔을 가진 공이 많고 break가 걸리지 않는 입력에서 많이 느려질 것 같습니다.

park780172   4년 전

@koosaga

저도 같은 색깔을 가진 공이 많으면 어쩌지 라고 생각을 하긴 했는데 아쉽군요.

제 코드를 저격하는 데이터가 없는 듯 하네요.

감사합니다~

O(n) 방법을 생각해봐야겠네요.

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