3주차 스터디(23.11.24)

슬슬 논문 작성과 학회 발표 준비에 바빠지다보니 포스팅이 조금 빈약해진 느낌.

 

3주차 스터디는 다음과 같은 문제들을 구현해보았다.

 

1. 연속부분 수열 합의 갯수

https://school.programmers.co.kr/learn/courses/30/lessons/131701

def solution(elements):
    ans = []
    for i in range (0,len(elements)):
        ans.append(elements[i])
    for i in range (0,len(elements)):
        ans.append(elements[i])
    summary = []
    for i in range (0,len(elements)): #길이를 indicate
        for j in range (1,len(elements)+1): #시작index 저장
            a = sum(ans[i:i+j])
            summary.append(a)
    summary = list(set(summary))
    answer = len(summary)
    
    return answer

 

2. 이진 변환 반복하기

https://school.programmers.co.kr/learn/courses/30/lessons/70129

def solution(s):
    removal,ope = 0,0
    while s != "1":
        comp = []
        cnt = 0
        for i in range (0,len(s)):
            if s[i] != "0":
                cnt += 1 #counting을 통해 마지막에 cnt를 2진으로 변환
            else:
                removal += 1 #제거하는 0의 갯수를 counting
        cnt = format(int(cnt), 'b')
        s = cnt
        ope += 1
    return ope,removal

 

3. Frequency of the Most Frequency Element

https://leetcode.com/problems/frequency-of-the-most-frequent-element/

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        N = len(nums)
        if N == 1:
            return 1
        else:
            nums.sort()
            start,end = 0,0
            result = 0
            summary = 0
            while end < N:
                summary += nums[end]
                while nums[end] * (end - start + 1) > summary + k:
                    summary-= nums[start]
                    start += 1
                result = max(result,end - start + 1)
                end += 1
            return result

 

4. 3Sum closest

https://leetcode.com/problems/3sum-closest/

class Solution:
    import math
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        max_diff = 20001
        ans = 0
        for i in range (0,N):
            start = i + 1
            end = N - 1
            while start < end:
                summary = nums[i] + nums[start] + nums[end]
                c = int(math.fabs(summary - target))
                if summary == target:
                    return target
                else:
                    if c < max_diff:
                        max_diff = c
                        ans = summary
                    if summary < target:
                        start += 1
                    else:
                        end -= 1
        return ans

 

5. Reduction Operations to Make the Array elements equal

https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal/

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[0]
        dict = {}
        for i in range (0,len(nums)):
            if nums[i] in dict:
                dict[nums[i]] += 1
            else:
                dict[nums[i]] = 1
        new_nums = list(dict.values())
        if len(new_nums) == 1:
            return 0
        else:
            cnt = 0
            for i in range (1,len(new_nums)):
                cnt += i * new_nums[i]
            return cnt

 

6. 2 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12900

def solution(n):
    def f(m):
        if m == 1:
            return 1
        elif m == 2:
            return 2
        else:
            dp = [0 for _ in range (m+1)]
            dp[1],dp[2] = 1,2
            for i in range (3,m+1):
                dp[i] = (dp[i-1] + dp[i-2]) % 1_000_000_007
            return dp[-1]
    answer = f(n) % 1_000_000_007
    return answer

 

7. H-index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

def solution(citations):
    answer = 0
    M = max(citations)
    for i in range (M,-1,-1):
        cnt = 0
        for j in range (0,len(citations)):
            if citations[j] >= i:
                cnt += 1
        if cnt >= i:
            return i
    return answer

 

8. n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

def solution(n, left, right):
    answer = []
    cnt = -1
    a,b = left // n, left % n
    c,d = right// n , right % n
    cnt = -1 + a * n
    for i in range (a,c+1):
        for j in range (0,n):
            cnt += 1
            if left <= cnt <= right:
                answer.append(max(j+1,i+1))       
            if cnt == right:
                break
    return answer

 

 

9. Kth Largest element in an array

https://leetcode.com/problems/kth-largest-element-in-an-array/

class Solution:
    import heapq
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for i in range (0,len(nums)):
            heapq.heappush(heap,-nums[i])
        for i in range (0,k-1):
            heapq.heappop(heap)
        a = -heapq.heappop(heap)
        return a

 

10. Ugly Number

https://leetcode.com/problems/ugly-number/

class Solution:
    import heapq
    def nthUglyNumber(self, n: int) -> int:
        answer = [1]
        heap = [2,3,5]
        dict = {}
        while len(answer) < n:
            b = heapq.heappop(heap)
            answer.append(b)
            if 2 * b not in dict:
                heapq.heappush(heap,2 * b)
                dict[2*b] = 1
            if 3 * b not in dict:
                heapq.heappush(heap,3 * b)
                dict[3*b] = 1
            if 5 * b not in dict:
                heapq.heappush(heap,5 * b)
                dict[5*b] = 1
        return answer[-1]

 

11. Kth Smallest Element in a Sorted matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

class Solution:
    import heapq
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = []
        for i in range (0,len(matrix)):
            for j in range (0,len(matrix[0])):
                heapq.heappush(heap,matrix[i][j])
        for i in range (0,k-1):
            heapq.heappop(heap)
        a = heapq.heappop(heap)
        return a

 

 

12. 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

import heapq
def solution(operations):
    answer = []
    heap1 = [] #최소힙
    heap2 = [] #최대힙으로 사용할 예정
    cnt = 0
    for i in range (0,len(operations)):
        if cnt == 0:
            heap1 = []
            heap2 = []
        a = operations[i][0]
        b = operations[i][2:]
        if a == "I":
            cnt += 1
            heapq.heappush(heap1,int(b))
            heapq.heappush(heap2,-int(b))
        if a == "D":
            #카운트가 하나 이상일 때 진행하겠다
            cnt -= 1
            if cnt < 0:
                cnt = 0
            else:
                #최댓값 저장되어있는 힙에서 제거하기
                if b == "1":
                    heapq.heappop(heap2)
                #최솟값 저장되어있는 힙에서 제거하기
                else:
                    heapq.heappop(heap1)
    list2 = []
    answer = []
    set1 = set(heap1)
    for i in range (0,len(heap2)):
        list2.append(-heap2[i])
    for i in range (0,len(list2)):
        if list2[i] in set1:
            answer.append(list2[i])
    if answer == []:
        return [0,0]
    else:
        return [max(answer),min(answer)]

 

13. 문자열 폭발

https://www.acmicpc.net/problem/9935

import sys
input = sys.stdin.readline
S = input().rstrip()
M = input().rstrip()
n = len(S)
m = len(M)
com = []
for i in range (0,m):
    com.append(M[i])
result = []
if n >= m:
    for s in S:
        result.append(s)
        if result[-m:] == com:
            for i in range (0,m):
                result.pop(-1)
    u = "".join(t for t in result)
else:
    for s in S:
        result.append(s)
    u = "".join(t for t in result)

if u == "":
    print("FRULA")
else:
    print(u)