[엘리스] 합계 0인 정수 쌍 구하기

합계 0인 정수 쌍 구하기

0을 제외한 n개의 정수가 주어졌을 때, 합이 0에 가장 가까운 숫자쌍을 구하는 sum_0(data)을 작성하세요.

[입력값]

첫 번째 줄에 n개의 정수들이 오름차순으로 주어집니다. n의 값은 따로 주어지지 않습니다.(1≤n≤100,000,000)

[결과값]

합이 0에 가장 가까운 숫자쌍을 빈 칸으로 구분하여 출력합니다. 숫자쌍은 오름차순으로 정렬하여 출력하며, 정답이 여러개일 경우 그 중 하나만 출력하면 됩니다.

[입력 예시]

-193 30 94 100 194

[출력 예시]

-193 194

풀이

• "투포인터" 알고리즘 : 1차원 배열이 있고 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 얻는 형태
• 성립하는 이유 : 배열이 정렬되어 있는 상황이어서 뒤쪽의 값들을 더하면 무조건 값이 커짐 (만일, 정렬되어있지 않다면 모든 값이 0을 포함한 자연수이어야 함)
  
  • 시작 위치를 오른쪽으로 옮기면 값의 합이 커짐 (만일 지금의 합이 이전보다 0에 가까우면 시작 위치를 옮김)  
  • 종료 위치를 왼쪽으로 옮기면 값의 합이 작아짐 (만일 지금의 합이 이전보다 0에 가까우면 종료 위치를 옮김) 
  • 시작 위치를 오른쪽으로 옮긴 경우와 종료 위치를 왼쪽으로 옮긴 경우를 비교해서 더 0에 가까운 쪽으로 옮김 

-193

30

94

100

194

• 시작 위치(s) : - 193 
• 종료 위치(e) : 194
• 둘의 합 : 1  

-193

30

94

100

194

-193

30

94

100

194

• 첫번째 경우 : -93 
• 두번쨰 경우 : 224 
• -93이 0에 가까우므로 종료 위치(e)를 100으로 이동 (첫번째 경우 선택)

-193

30

94

100

194

-193

30

94

100

194

• 첫번째 경우 : -99
• 두번쨰 경우 : 130
• -99가 0에 가까우므로 종료 위치(e)를 94으로 이동 

-193

30

94

100

194

-193

30

94

100

194

• 첫번째 경우 : -163
• 두번쨰 경우 : 124
• 124이 0에 가까우므로 시작 위치(s)를 30으로 이동 

-193

30

94

100

194

-193

30

94

100

194

• 첫번째 경우 : 60
• 두번쨰 경우 : 188
• 60이 0에 더 가까우므로 종료 위치(e)를 30으로 이동하지만, 이때 종료 위치가 시작 위치보다 크지 않기 때문에 60이라는 값은 저장하지 않고 while문을 탈출 

def sum_0(data): 
    # Implement here

    return_pair = [0, 0]

    # 모두 자연수여야 하는 조건이 있음 
    i = 0
    j = len(data)-1
    min_num = 100000000
    while i < j :
        if min_num > abs(data[i]+data[j]) :
            min_num = abs(data[i]+data[j])
            return_pair[0] = data[i]
            return_pair[1] = data[j]
        if abs(data[i]+data[j-1]) > abs(data[i+1]+data[j]) :
            i = i+1
        else :
            j = j-1

    return return_pair

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    given_data = input()

    data = [int(v.strip()) for v in given_data.split()]

    print (*sum_0(data)) 

if __name__ == "__main__":
    main()

참고자료

• https://woovictory.github.io/2019/05/28/Two-Pointer-Algorithm/

출처 : 엘리스 아카데미, https://academy.elice.io/learn