알고리즘 문제 풀이 과제
- leetcode 49. 그룹 애너그램 - https://leetcode.com/problems/group-anagrams/description/
- leetcode 5. 가장 긴 팰린드롬 부분 문자열 - https://leetcode.com/problems/longest-palindromic-substring/
- leetcode 15. 세 수의 합 - https://leetcode.com/problems/3sum/
- leetcode 561. 배열 파티션 - https://leetcode.com/problems/array-partition/
오늘 스터디에서 내가 발표를 진행한 과제는 4. leetcode 561. 배열 파티션 이다.
현재 내 알고리즘 풀이 경험도 적고, python의 문법도 익숙치 않다 보니 일부러 제일 쉬운 것을 선택했다.
결과적으로 미리 얘기하면, 4번도 문법을 찾아가며 풀고, 1번은 풀다가 어떤 걸로 써야 할지 몰라서 다른 사람이 푼 글을 봤다.
2번과 3번은 어렵기도 하고 문제조차 헷갈렸는데 제대로 문제를 이해했다고 해도 풀기는 어려웠을 것 같다.
앞으로 여러 문제를 풀고 경험하면서, python에 익숙해지고 알고리즘도 잘 풀 수 있게 되면 좋겠다.
561. Array Partition
from. leetcode
크롬에 내장된 영한 번역을 사용했다.
나의 풀이는 아래와 같다.
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
nums.sort()
answer = 0
for i in range(0, len(nums), 2):
# if i % 2 == 0:
answer += nums[i]
return answer문제는 2*n개의 수 중에서, 2개씩 짝 지어 n쌍을 만들었을 때 모두 더한 최솟값을 최대로 하는 값을 구하는 것이다.
이는 곧, (가장 작은 수 + 그 다음 작은 수)의 반복인데, 굳이 나눌 필요 없이 오름차순으로 정렬한 후, 인덱스가 0과 짝수인 값을 더하면 된다.
따라서, nums를 sort()로 오름차순으로 정렬해 준 뒤, 반복문을 이용해 짝수의 값을 더해주면 된다.
처음에는 if문을 이용하여 짝수를 구하려 했으나, python 반복문의 range() 함수는 범위 지정에서 증가값을 정하는 인자가 있어 대체했다.
if문보다 실행 횟수가 줄어드니 조금이나마 실행 시간이 줄어들 것이라고 생각한다.
다른 사람들은 어떻게 풀었을지 검색을 통해 블로그 글을 조금 찾아 봤다.
내가 푼 것과 비슷한 접근법으로 푼 답들이 있었는데 그외에 눈에 띈 풀이가 있어서 가져 왔다.
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
return sum(sorted(nums)[::2])깔끔하게 한 줄로 마무리한 코드이다.
새로 알게 된 재밌는 점이 세 가지 있었다.
1. sum() 함수 내장
내가 봤던 수많은 JS 강의들이 함수를 강의할 때 쓰는 코드가 있다.
function sum (a, b) = { a + b }그동안 이렇게 만들었던 sum이 내장 함수로 존재할 줄은 몰랐다.
물론 위 JS 코드와는 기능이 다른 부분이 있다.
sum(a), sum(a, b)
a는 리스트나 튜플이 들어 갈 수 있다. 해당 리스트 안의 모든 값을 더한 값이 출력된다.
또한 b 인자를 넣게 되면, b가 초기 값이 된다.
쉽게 생각하면 a 안의 모든 값을 더하고 b까지 더해주면 된다.
따라서 그냥 정수 a와 정수 b라면 a + b가 될 것이라 생각한다.
혹시 아니라면 이 글을 수정하러 오겠다.
2. sort() 함수와 sorted() 함수의 차이점
sort()의 경우, 리스트 전용 메소드로 list.sort()로 해당 리스트를 오름차순으로 정렬할 수 있다.
반환하는 값은 없으며, list라는 리스트 자체의 배열을 변환한다.
sorted()의 경우, 리스트뿐만 아니라 iterable 객체 전체를 인자로 받는다. sorted(str), sorted(list) etc.
대표적으로 list, tuple, str, dict, set 등이 있다.
또한, 해당 객체를 오름차순으로 정렬하여 '반환'한다. 따라서 할당해주는 것이 가능하다.
3. 슬라이싱 [::]
a[start_id : end : step] 이와 같은 형식으로 작성한다.
a라는 객체의 start_id 부분에 시작점 인덱스를 기입하고, end 미만 인덱스까지 출력되며(end 미포함), 인덱스가 step 만큼 증가한다(증감문?)
start_id나 end는 비울 경우, 해당 객체의 0번 인덱스에서 시작하거나 length값(len(a))이 입력된다고 생각할 수 있다.
처음 보는 연산자인데 아주 효율적으로 사용할 수 있는 훌륭한 연산자라고 생각한다.
# 위 세 가지를 공부한 후, 한 줄짜리 답변을 다시 확인하자.
nums를 sorted 해서 0부터 2 단위의 인덱스의 값을 더한 값을 리턴한다.이런 간결한 코드를 낼 수 있게끔 더 많은 문제를 풀고 경험하고 다양한 방면에서 생각하고 활용하도록 해보자.
p.s. 다른 세 문제가 더 어려웠는데, 여유가 생긴다면 추가로 기록해볼까 한다.
