Programmers - 두 개 뽑아서 더하기 (Python 풀이)

문제

[문제 설명]

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

[입출력 예]

numbers	result
[2,1,3,4,1]	[2,3,4,5,6,7]
[5,0,2,7]	[2,5,7,9,12]

 

예시 설명은 아래 클릭

입출력 예 #1

• 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3 입니다.
• 5 = 1 + 4 = 2 + 3 입니다.
• 6 = 2 + 4 입니다.
• 7 = 3 + 4 입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2 입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

문제 풀이

1. 조합을 이용하여 배열에서 원소 2개를 뽑는다.
2. 뽑은 2개의 원소를 더한 값을 answer에 담는다.
   • 중복되는 값은 SKIP
   • 새로 들어온 값은 추가
3. 오름차순으로 정렬하여 return 한다.

 

Python 코드

인덱스를 가지고, 원소의 합을 구할때는 map 함수를 이용하여 한 줄로 요약할 수 있다.

def solution(numbers):
    answer = []
    
    pick_number = set()  # 뽑은 number를 담는 집합
    
    
    def __combination(index, count):
        # 2개를 뽑았다면, STOP
        if count == 2:
            # 원소의 합 구하기
            _sum = sum(list(map(lambda x: numbers[x], pick_number)))
            
            if _sum in answer:
                pass  # 이미 answer에 들어있는 값이면 pass
            else:
                answer.append(_sum)  # answer에 없는 신규 값이면 append
            return

        else:
            for i in range(index, len(numbers)):
                # 경우 1. 원소를 뽑는 경우
                pick_number.add(i)
                __combination(i+1, count+1)  # 그 다음 index 부터 시작 / 1개를 뽑았으니 count 증가
                
                # 경우 2. 원소를 뽑지 않는 경우
                pick_number.remove(i) 

    # 시작
    __combination(0, 0)
    
    # 오름차순으로 정렬
    return sorted(answer)

 

결과

결과 확인

 

참고

다 풀고 나서 Python에 combinations 함수가 존재한다는 것을 알았다.

파이썬이 편하긴 편하구나..

from itertools import combinations

def solution(numbers):
    answer = []

    for i in list(combinations(numbers, 2)):
        _sum = i[0]+i[1]
        if _sum not in answer:
            answer.append(_sum)

    return sorted(answer)