[알고리즘 스터디] 8월 4주차 문제 Add Two Numbers, Maximum Number of Groups Entering a Competition

이번주 알고리즘 문제는

[Maximum Number of Groups Entering a Competition]

https://leetcode.com/problems/maximum-number-of-groups-entering-a-competition/

Maximum Number of Groups Entering a Competition - LeetCode

You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions:

• The sum of the grades of students in the ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last).
• The total number of students in the ith group is less than the total number of students in the (i + 1)th group, for all groups (except the last).

Return the maximum number of groups that can be formed.

 

Example 1:

Input: grades = [10,6,12,7,3,5]
Output: 3
Explanation: The following is a possible way to form 3 groups of students:
- 1st group has the students with grades = [12]. Sum of grades: 12. Student count: 1
- 2nd group has the students with grades = [6,7]. Sum of grades: 6 + 7 = 13. Student count: 2
- 3rd group has the students with grades = [10,3,5]. Sum of grades: 10 + 3 + 5 = 18. Student count: 3
It can be shown that it is not possible to form more than 3 groups.

Example 2:

Input: grades = [8,8]
Output: 1
Explanation: We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.

 

Constraints:

• 1 <= grades.length <= 105
• 1 <= grades[i] <= 105

[풀이 계획]

1. 오름차순으로 정렬한다.
2. N을 1부터 N+1만큼의 그룹으로 나누고 나머지를 저장하는 것을 반복한다.
3. 더 나뉘지 않으면 그룹이 나뉜 count만큼 return 시킨다.

class Solution(object):
    def maximumGroups(self, grades):
        N = len(grades)
        CNT = 0
        TOTAL = 0
        """
        1. 오름차순으로 정렬한다.
        2. N을 1부터 N+1만큼의 그룹으로 나누고 나머지를 저장하는 것을 반복한다.
        3. 더 나뉘지 않으면 그룹이 나뉜 count만큼 return 시킨다.
        """
        if N == 1:
            return 1
        for i in range(1, N+1) :
            TOTAL += i
            if TOTAL <= N:
                CNT+=1
            else :
                return CNT

 

[Add Two Numbers]

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

 

난이도 : Medium

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

[풀이 계획]

1. 리스트에 담긴 노드들을 pop하여 끝 노드부터 변수에 담는다
2. 이때 해당 노드를 N이라 칭하면 N이 위치한 길이만큼 *10을 통해 저장하고, 다음 노드부터 기존 노드에 값을 더한다.
3. 두개의 리스트 노드를 합연산한다.
4. 합연산된 결과를 리스트로 형변환시켜 revese 시킨다.

 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        1. 리스트에 담긴 노드들을 pop하여 끝 노드부터 변수에 담는다
        2. 이때 해당 노드를 N이라 칭하면 N이 위치한 길이만큼 *10을 통해 저장하고, 다음 노드부터 기존 노드에 값을 더한다.
        3. 두개의 리스트 노드를 합연산한다.
        4. 합연산된 결과를 리스트로 형변환시켜 revese 시킨다.
        """
        NUM1 = []
        NUM2 = []
        while l1 is not None:
            NUM1.append(str(l1.val))
            l1 = l1.next
        while l2 is not None:
            NUM2.append(str(l2.val))
            l2 = l2.next
        NUM1.reverse()
        NUM2.reverse()
        tempStr1 = ''.join(NUM1)
        tempStr2 = ''.join(NUM2)
        CAL = int(tempStr1) + int(tempStr2)
        result = list(map(int,str(CAL)))
        result.reverse()
        #연결 리스트로 변환
        head = ListNode(result[0])
        tail = head
        e = 1
        while e < len(result):
          tail.next = ListNode(result[e])
          tail = tail.next
          e+=1
        return head