[일반] 정수배열 중에 두개 뽑아서 타겟값이랑 같은지 확인하느거

[ㅁㄴㅇ(211.59)]

제일 빡세게 구현하면 시간복잡도 어떻게됨?

예를들면

배열 [1,7,4,3,6,2]

타겟값 9

이렇게 주어지면 답은 (1,5) 랑 (3,4)

암튼 이거 N^2 말고 더 빠른 방법도 있음?

[익명(218.54)]

개수가 아니라 각각의 쌍을 전부 구하란 거임?

[익명(218.54)]

우선 정수 범위일 경우 무조건 O(N^2)이고, 0보다 큰 수만 있으면 O(N)임. 개수만 구하려면 O(NlgN)이나 O(N)에 가능

[ㅁㄴㅇ(211.59)]

헉 어케 N이 나옴?

[시아닌(kimjg1119)]

정렬빼면 O(N) 가능할듯. 투포인터라고 들어보셨습니까 휴먼?

[익명(218.54)]

아잠만 착각한듯 ㅅㅂ 0보다 큰 수가 아니라 모두 서로 다른 수일 때임

[익명(218.54)]

근데 보통 그런 문제가 있을린 없을 테고 걍 왠만하면 O(N^2)같음

[ㅁㄴㅇ(211.59)]

오오 투포인터 좋은데

[메리체리(mrscherry)]

0보다큰게 먼상관?

[익명(218.54)]

투포인터 못쓰나 생각하다가 최대부분합이랑 착각한듯.. 개소리니가 잊어줬으면

[ㅅㅅ(223.62)]

일단 간단한 방법은 정렬해서 lowerbound 쓰면 nlogn

[ㅅㅅ(223.62)]

아님 set 써도 되고

[ㅁㄴㅇ(211.59)]

lowerbound가 뭔지 처음들어봐서 알아봐야겠다

[익명(223.33)]

입력받을때 정렬로 입력받으면 정렬 해결아니냐

[AhriPhilia(dccon1592)]

정렬해서 양쪽 끝 둘을 더해서 타겟보다 크면 오른쪽을 내리고 작으면 왼쪽을 올리고 정렬되어있으면 O(N)

[AhriPhilia(dccon1592)]

정렬 안되어있다고하더라도 input의 범위가 충분히 작으면 카운팅해서 인덱스 저장한다음에 arr[target-input[i]] 이런식으로 접근하면 O(N)에 될거같은데

[메리체리(mrscherry)]

인풋 작으면 카운팅소트하면 똑같지

[AhriPhilia(dccon1592)]

ㄴ 그러네 씹ㅋㅋ