jackcom   4년 전

안녕하세요.
백준 사이트 문제는 아닙니다.
Two Pointer 문제입니다.

주어진 배열 데이타에서 두개의 합이 최소가 되는 배열 원소의 인덱스를 출력 하는 것이 문제입니다.
그런데 제가 이해가 안 가는것이 Two Pointer 문제이긴 하지만 itertools의 combinations 으로도 풀수 있을것 같아서 풀었지만 오답처리가 되었습니다.
아무리 봐도 문제는 없어 보이는데 왜 two pointer 로 하면 정답처리가 되고, combinations 으로 하면 오답처리가 되는 것일까요?

코드에서 A.sort()를 하고는 있지만 입력으로 주어지는 데이타는 오름차순 정렬된 데이타가 주어집니다.
출력조건은 만약 0에 가장 가까운 조합이 여려개 나올경우 먼저 입력된 것을 출력 하는 조건입니다.

그래서 
A = [-102, -58, 59, 78, 101]
의 경우 
-102 + 101 로 차이가 1, -58 + 59도 차이가 1 이지만 먼저 입력된 순임으로 -102와의 조합인 101
인덱스는 0, 4가 정답이 되게 됩니다.

제가 무엇을 놓치고 있는 것인지
고수님들의 리뷰좀 부탁 드려봅니다.

cinador   4년 전

'먼저 입력된 것' 이 어떤 기준인지는 모르겠지만 위 코드와 아래 코드의 답이 다르게 나오는 경우는 있습니다.

만약 -2, 1, 3 이 주어졌다고 하면 위 코드는 양 끝에서 시작하기 때문에 0, 2가 출력되지만

combination의 경우 인덱스가 (0, 1), (0, 2), (1, 2) 순이기 때문에 0, 1이 출력되게 됩니다.

 아니면 혹시 오타가 아니라면 올려주신 정답 코드에 while l<=r : 이라고 되있는데 정답처리 되었다면 같은 인덱스가 허용된다고 생각됩니다. (예를 들어 0이 포함되면 0만 두번)

combination을 이용하면 중복된 인덱스가 답이면 그 답을 찾을 수 없습니다.

jackcom   4년 전

반례 감사합니다.  예외를 생각하고 반례를 생각해 봐야 하는데 이런거에 익숙치 않네요.
그리고 l<=r 이 부분에 대한 two pointer 와 comb 에 대한 차이도 이해 할 수 있었습니다.
너무너무 감사드립니다.

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