[엘리스] 합계 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://academy.elice.io/learn

'EDA Study > 알고리즘' 카테고리의 다른 글

[엘리스] 점토 놀이  (0) 2020.03.28
[알고리즘] 우선순위 큐  (0) 2020.03.28
[엘리스] 합계 0인 정수 쌍 구하기  (0) 2020.03.28
[엘리스] 소수 판정  (0) 2020.03.28
[엘리스] 두 번째 최대값  (0) 2020.03.28
[엘리스] 이진트리 만들기  (0) 2020.03.28

댓글(0)

Designed by JB FACTORY