문제
n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
입력: [1, 4, 3, 2]
출력: 4
min(1, 2) + min(3, 4)일 경우에 최대값 4를 출력하게된다.
나의 코드
# min(a, b)의 합으로 만들 수 있는 가장 큰수
# 정렬
# 앞에서 2개씩 묶기
# 작은겄기리 묶고 큰것끼리 묶어야 최소값의 합이 가장 커진다
# [1, 4, 3, 2] -> [1, 2, 3, 4]
# 앞에서부터 2개씩 묶었을때 짝수번째의 원소만 추출하면 된다.
nums = [1, 4, 3, 2]
nums.sort()
result = 0
# 반복문 인덱스를 사용하여 짝수번째 원소만 추출
for i, a in enumerate(nums):
if i % 2 == 0:
result += a
print(result)
해당 문제의 의도를 파악하면 쉬운 문제다. 예시의 경우 리스트가 [1, 4, 3, 2]일 때를 보자. 결과적으로 최대값 추출이 목적이지만 함수는 min() 이기 때문에 최소값을 구하여 덧셈을 실행하게 된다. 이때 작은수끼리, 큰수끼리 묶여야 각 min(a, b)에서 최소값이 추출되더라도 충 합은 최대값이 될 수 있다. 그리고 또 알수있는 점은 리스트가 정렬된 경우이다. [1, 4, 3, 2]가 정렬된다면 [1, 2, 3, 4]가 된다. 따라소 오름차순으로 정렬된 리스트가 되기 때문에 여기서 짝수번째의 원소를 추출하면 그게 최소값이 된다. 2개씩 묶이기 때문에 정렬된 데이터에서는 왼쪽이 작은 값임을 알 수 있다.
정답코드
1) 2개씩 건너띄며 합하는 방식
from typing import List
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
# 정렬 후 2개씩 건너띄며 합하기
return sum(sorted(nums)[::2])
2) pair 리스트를 활용하는 방식
from typing import List
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
pair = []
# 정렬
nums.sort()
for n in nums:
# 앞에서 부터 오름차순으로 페어를 만들어 합 계산
pair.append(n)
# pair 리스트에 2개씩 쌓일때마다 실행한다는 의미
if len(pair) == 2:
sum += min(pair)
pair = [] # 2개가 쌓였으면 다시 리셋하여 그 다음 2개 쌓일때를 기다림
return sum
출처: github.com/onlybooks/algorithm-interview
문제풀이
1번의 정답코드 풀이
1) 설명
# 정렬 후 2개씩 건너띄며 합하기
return sum(sorted(nums)[::2])
위 '나의코드'에서 내가 짠 코드와 비슷하다. 리스트의 정렬을 실행하고 2개씩 건너띄며 원소를 찾는다. 따라서 0번째, 2번째 원소를 찾게되고 해당 번째의 원소를 찾은 이유는 내가 위에서 설명한 이유와 같다.
2번의 정답코드 풀이
1) 설명
pair = []
pair 라는 리스트 타입의 변수를 선언했다.
2) 설명
# 정렬
nums.sort()
정렬을 수행한다.
3) 설명
for n in nums:
# 앞에서 부터 오름차순으로 페어를 만들어 합 계산
pair.append(n)
# pair 리스트에 2개씩 쌓일때마다 실행한다는 의미
if len(pair) == 2:
sum += min(pair)
pair = [] # 2개가 쌓였으면 다시 리셋하여 그 다음 2개 쌓일때를 기다림
return sum
pair 리스트에 각 원소를 차례대로 담는다. 반복문이 실행될때마다 담으므로 정렬된 리스트에서는 최소값부터 담아지는 것을 확인할 수 있다. 그리고 그렇게 담아지면서 pair에 원소가 2개씩 쌓일때마다 최소값을 구해서 sum 변수에 담는다. 그리고 pair 리스트를 다시 비어주게 된다. 이렇게 되면 pair 리스트는 2개씩 쌓일때마다 min() 함수를 호출하게되고, 리스트가 비어지게된다.
'Coding Test 연습' 카테고리의 다른 글
[코딩인터뷰] 연결리스트 - 팰린드롬 연결리스트 문제풀이 (0) | 2021.02.07 |
---|---|
[이것이 코딩테스트다] 다이나믹 프로그래밍 - 바닥공사 문제풀이 (1) | 2021.02.06 |
[코딩인터뷰] 배열 - 주식을 사고팔기 가장 좋은 시점 문제풀이 (0) | 2021.02.05 |
[이것이 코딩테스트다] 그리디 - 1이 될때까지 문제풀이 (0) | 2021.02.04 |
[이것이 코딩테스트다] 그리디 - 큰 수의 법칙 문제풀이 (0) | 2021.02.04 |