| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
- leetcode #subsets #dfs #itertools #python
- leetcode #python #dfs #재귀
- 아스테리스크 #Asterisk #파이썬
- dfs #그래프 #graph #python #leetcode #course #schedule
- python #백준 #2580 #스도쿠 #dfs #백트래킹
- dfs #python #leetcode #combination
- python #백준 #9375 #패션왕 #신해빈
- dfs #bfs #트리구조 #이진트리 #leetcode #python #파이썬
- exoplayer #mediaplayer #엑소플레이어 #안드로이드 #android
- context #android #getApplicationContext #activity #생명주기 #lifecycle
- 백준 #파이썬 #bfs #백트래킹 #1697 #숨바꼭질
- dfs #leetcode #python
- 다익스트라 #dijkstra #leetcode #파이썬 #python #algorithm #787
- 리트코드 #팰린드롬 #파이썬
- 다익스트라 #알고리즘 #bfs #그리디 #다이나믹프로그래밍 #leetcode #python
- dfs #bfs #이진트리 #파이썬 #리트코드
- dfs #bfs #트리구조 #이진트리 #leetcode #파이썬 #python
- 해시테이블 #heapq #파이썬 #리트코드 #알고리즘
- gcd #최대공약수 #백준 #2981 #검문
- dfs #이진트리 #트리구조 #직렬화 #역직렬화 #파이썬 #리트코드 #leetcode #python
- 파이썬 #zip
- AsyncTask #doinbackground #스레드 #thread #android #안드로이드
- dfs #bfs #leetcode #python
- 2004 #조합 0의 개수 #백준
- dfs #python #leetcode
- dfs #leetcode #python #graph #그래프
- 코틀린 #Do it #깡샘 #안드로이드
- Python #leetcode #dfs #그래프 #백트래킹
- final #java #자바 #안드로이드
- handler #looper #thread #runnable #핸들러 #루퍼 #스레드 #러너블
- Today
- Total
멋진 개발자가 되고 싶다
[LeetCode] 561. 배열 파티션 I(Array Partition I) 본문
n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.
Input: nums = [1,4,3,2]
Output: 4
Explanation:
All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
1. 내가 직접 푼 코드
|
1
2
3
4
5
6
7
8
|
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
result = 0
nums.sort()
print(nums)
for i in range(len(nums)//2):
result += min(nums[-(2*i+1)],nums[-(2*i+2)])
return result
|
cs |
해설:
nums를 정렬하고 값을 차례대로 min에 집어넣어 주면 되는 단순한 문제이다.
이해가 안되면 직접 넣어봐라!
사실 배열의 맨 앞부터 차례대로 min에 넣어도 되는데
입력값이 2의 배수로 들어온다는 것을 못 봐서 맨 뒤에부터 시작하도록 했다.
시험장에서는 문제의 세세한 조건까지도 따져보고 코드를 작성하자.
면접관이 왜 문제 자세히 안 봤냐고 뭐라 할 수도 있으니까.
** 깔끔한 답안 **
2. 오름차순 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
pair = []
nums.sort()
for n in nums:
# 앞에서부터 오름차순으로 페어를 만들어서 합 계산
pair.append(n)
if len(pair)==2:
sum += min(pair)
pair = []
return sum
|
cs |
해설:
pair라는 리스트를 만들어서 그 안에 2개가 차면 min을 구하는 식으로 진행했다.
나랑 결이 같은 코드지만 깔끔하다.
for문에 nums를 저런 식으로 이용하는 것을 생활화하자.
3. 짝수 번째 값 계산
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
sum = 0
nums.sort()
for i,n in enumerate(nums):
# 짝수 번째 값의 합 계산
if i % 2 == 0:
sum += n
return sum
|
cs |
해설:
아이디어를 생각해내면 훨씬 더 단순해지는 것 같다.
사실문제에서 min을 쓰라는 느낌을 받아서 이 방식은 생각 못했을 것 같다.
코드는 간결한데 런타임 자체는 위와 비슷하다.
4. 파이썬다운 방식
|
1
2
3
|
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])
|
cs |
해설:
결국엔 짝수를 더하는 거니까
정렬을 한 다음 슬라이싱으로 2칸씩 건너뛰면서 더하면 된다.
출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]
'Algorithm Study > leetcode' 카테고리의 다른 글
| [LeetCode] 121. 주식을 사고팔기 좋은 시점(Best Time to Buy and Sell Stock (0) | 2021.06.29 |
|---|---|
| [LeetCode] 238. 자신을 제외한 배열의 곱(Product of Array Except Self) (0) | 2021.06.29 |
| [LeetCode] 15. 세 수의 합(3Sum) (0) | 2021.06.27 |
| [LeetCode] 42. 빗물 트래핑(Trapping Rain Water) (0) | 2021.06.27 |
| [LeetCode] 1.두 수의 합(Two Sum) (0) | 2021.06.27 |
