내일은 알고리즘

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

완전탐색(브루트포스)유형의 연습 문제입니다. 

찍는 방식을 매칭하는 방법은 여러개가 있을텐데 이번 문제에선 간단한 형태여서 List로 하드코딩하고, 그 길이로 index를 나눠서 맞추는 식으로 구현했습니다.

최고점수를 받은 수험자들을 출력하는 부분은 어차피 정렬되어 있으므로 정렬은 신경쓰지 않고, max 함수로 간단하게 최고 점수를 구한다음 그 최고점수와 같은 점수를 가진 수험자들을 넣어주는 식으로 풀이했습니다.

def solution(answers):
    pick = [[1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    grade = [0, 0, 0]
    answer = []

    for i in range(len(answers)):
        if answers[i] == pick[0][i % 5]:
            grade[0] += 1
        if answers[i] == pick[1][i % 8]:
            grade[1] += 1
        if answers[i] == pick[2][i % 10]:
            grade[2] += 1

    max_grade = max(grade[0], max(grade[1], grade[2]))

    for i in range(3):
        if grade[i] == max_grade:
            answer.append(i + 1)

    return answer

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

파이썬의 내장 메소드를 이용해 List를 자르고, 정렬해서 원하는 값을 출력했습니다.

def solution(array, commands):
    answer = []

    for command in commands:
        start = command[0]
        end = command[1]
        target = command[2]

        arr = array[start-1:end]
        arr.sort()
        answer.append(arr[target-1])

    return answer

print(solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]))

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

해쉬의 연습문제로 등록되어 있지만, Key값으로 쓸 이름이 숫자형태여서 그냥 boolean 배열로 관리해도 충분히 풀이할 수 있습니다.

폰켓몬을 가져갈수 있는 최대값(N/2)범위 이내에서 겹치지 않게 카운팅을 해주면 됩니다.

boolean 배열과 Dictionary 두가지 형태로 작성했습니다.

def solution(nums):
    answer = 0
    count = len(nums) // 2
    picked = [False for i in range(200_001)]
    
    index = 0
    while answer < count and index < len(nums):
        if not picked[nums[index]]:
            picked[nums[index]] = True
            answer += 1
            
        index += 1
    
    return answer


//딕셔너리 사용
def solution_with_dict(nums):
    answer = 0
    count = len(nums) // 2
    picked = {}
    
    index = 0
    while answer < count and index < len(nums):
        if not nums[index] in picked:
            picked[nums[index]] = 1
            answer += 1
        index += 1
    
    return answer

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

Heap, 또는 PriorityQueue로 알려진 우선순위 큐를 활용하는 문제입니다.

라이브러리 내의 heapq등의 완성된 자료구조를 사용해도 되지만 직접 구현해서 풀이했습니다.

아이디어는 간단합니다, 현재 시간에 요청이 들어온 작업들을 우선순위 큐에 넣고 작업이 끝났을때 시간을 기준으로 

끝난시간 - 요청시간 = 총 대기시간이 됩니다. 

작업이 끝나면 그 시간으로 시간을 진행시켜줍니다. 이 방법으로 모든 업무가 큐에 들어가고 큐가 빌때까지 진행해 주었습니다.

def solution(jobs):

    jobs.sort(key=lambda x: (x[0], x[1]))

    time = jobs[0][0]
    exec_time = 0
    index = 0
    heap = MinHeap()

    while True:
        while index < len(jobs):
            if jobs[index][0] <= time:
                heap.insert(jobs[index])
                index += 1
            elif len(heap.queue) == 0 and index < len(jobs):
                time = jobs[index][0]
            else:
                break

        task = heap.pop()
        if not task:
            break
        exec_time += time + task[1] - task[0]
        time += task[1]

    return int(exec_time / len(jobs))


class MinHeap(object):

    def __init__(self) -> None:
        self.queue = []

    def insert(self, n) -> None:
        index = len(self.queue)
        self.queue.append(n)
        while 0 <= index:
            pIndex = self.parent((index))
            if 0 <= pIndex and self.queue[pIndex][1] > self.queue[index][1]:
                self.swap(index, pIndex)
                index = pIndex
            else:
                break

    def pop(self):
        if len(self.queue) == 0:
            return False

        last = len(self.queue) - 1
        self.swap(0, last)
        front = self.queue.pop()
        self.sort(0)
        return front

    def sort(self, index):
        left = self.leftChild(index)
        right = self.rightChild(index)
        smaller = index

        if left < len(self.queue) and self.queue[smaller][1] > self.queue[left][1]:
            smaller = left
        if right < len(self.queue) and self.queue[smaller][1] > self.queue[right][1]:
            smaller = right

        if index != smaller:
            self.swap(index, smaller)
            self.sort(smaller)

    def swap(self, a, b) -> None:
        temp = self.queue[a]
        self.queue[a] = self.queue[b]
        self.queue[b] = temp

    def parent(self, index) -> int:
        return (index - 1) // 2

    def leftChild(self, index) -> int:
        return index * 2 + 1

    def rightChild(self, index) -> int:
        return index * 2 + 2


print(solution([[1, 9], [0, 3], [2,8], [4,10], [2, 6],[150,1]]))

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

기본적인 DFS로 풀이가능한 문제입니다.

이 문제도 기본유형의 문제라 레벨이 높은 상태인것 같습니다.

아직 탐색하지 않은 computer를 만나면 DFS로 연결된 모든 컴퓨터들을 탐색하고, 방문처리해주면 됩니다.

DFS 한번에 연결된 컴퓨터들이 전부 방문되기 때문에 정답인 네트워크의 갯수는 DFS의 호출횟수와 같습니다.

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            findNetwork(i, computers, visited)
            answer += 1

    return answer


def findNetwork(now, computers, visited):
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and not visited[next]:
            visited[next] = True
            findNetwork(next, computers, visited)
            


print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

곱이 양의 정수가 되는 가장 긴 부분수열의 길이를 구하는 문제입니다.

고려해야할 조건은 다음과 같습니다.

1. 중간에 0이 들어가는 경우 어떻게 곱해도 0이 되기 때문에 양의 정수라는 조건을 충족시키지 못합니다. 그래서 부분수열은 0을 기준으로 끊어진 형태가 됩니다.

2. 부분수열 안에 음수가 짝수개 있으면 곱하면서 서로 상쇄되어 곱셈의 결과가 양의 정수가 됩니다.

3. 그럼 음수가 홀수개 있다면 어떨까요? 하나만 빼주면 짝수가 됩니다.

(음수가 1개 있어서 하나를 빼도 0개로 조건을 충족합니다.)

내 위치에서 가장 먼 음수를 빼고 그 다음부터 카운트 하는게 수열의 길이를 길게 만들겁니다.

그리고 내 위치에서 가장 먼 음수는 0 이후에 처음 나온 음수가 될겁니다.

코드로 구현하면 이렇습니다.

class Solution:
    def getMaxLen(self, nums: list) -> int:
        answer = -1
        zeroInedx = -1
        firstNegative = -1
        negativeCount = 0
        
        for i in range(0, len(nums)):
            if(nums[i] == 0):
                firstNegative = -1
                negativeCount = 0
                zeroInedx = i
            
            if(nums[i] < 0):
                negativeCount += 1 
                if(firstNegative == -1):
                    firstNegative = i
            
            if(negativeCount % 2 == 0):
                answer = max(answer, i - zeroInedx)
            else :
                answer = max(answer, i - firstNegative)
        
        return answer
    

input = [[1,-2,-3,4],[0,1,-2,-3,-4],[-1,-2,-3,0,1]]

for i in input:
    print(Solution().getMaxLen(i))

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

기본적인 BFS로 풀이가 가능한 문제입니다.

기본 문제라 Lv.3로 놓인거지 요즘 레벨로는 2레벨 중에서도 쉬운문제가 아닐까 싶습니다...

node의 갯수가 edge의 갯수보다 훨씬 많기 때문에 인접행렬 대신 인접리스트를 사용해 구현했습니다.

(node의 갯수가 2만개로 인접행렬로는 2만*2만 = 4억 사이즈가 됩니다.)

BFS를 이용해 시작점에서 부터의 거리가 한 칸씩 먼 노드들을 탐색했고, 매번 탐색한 노드의 갯수를 저장해서

더 탐색할 노드가 없는 경우엔 이전 턴에 탐색한 노드의 갯수를 리턴했습니다.

from collections import deque


def solution(n, edge):
    answer = 0
    adjList = [[] for i in range(n+1)]
    visited = [False]*(n+1)
    
    for i in edge:
        start = i[0]
        end = i[1]
        
        adjList[start].append(end)
        adjList[end].append(start)
    
    queue = deque()
    queue.append(1)
    visited[1] = True

    while(len(queue) != 0):
        answer = size = len(queue)
        
        for i in range(size):
            start = queue.popleft()
            
            for e in adjList[start]:
                if(not visited[e]):
                    visited[e] = True
                    queue.append(e)
    
    return answer


n = 6
vertexs = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

print(solution(n,vertexs))

https://leetcode.com/problems/maximum-sum-circular-subarray/

Maximum Subarray를 살짝 비튼 문제입니다.

처음엔 Maximum Subarray를 앞 뒤로 두번 구해서 겹치지 않도록 조각을 붙여가며 탐색할까 생각도 해봤지만 깔끔한 구현방법이 떠오르지 않아서 솔루션을 참고했습니다.

생각지도 못했던 아이디어가 있더라구요.

https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

자세한 설명은 위 링크에 있는데 핵심 아이디어는 이미지만 봐도 알 수 있으실것 같습니다.

자명하게도 최대합이 되는 부분수열은 두 경우중에 하나일겁니다.

원형으로 이어지지 않거나, 이어지거나.

이어지지 않는 경우는 기존의 Maximum Subarray문제의 풀이와 같습니다.

이어지는 경우는 위 그림처럼 전체 합에서 Minimum Subarray를 뺀 값이 됩니다.

다시 생각해보면 원형으로 이어진 이 Maximum Subarray는 아래의 array의 Maximum Subarray와 같습니다.

(왼쪽 부분을 똑 떼어서 붙였습니다.)

array를 두 부분으로 나누었을 때, 한쪽이 최대합이라면 반대쪽은 최소합이 됩니다.

totalSum - maxSum = minSum / totalSum - minSum = maxSum

만약 더 작은 음수의 다른 minSum이 존재한다면 maxSum도 더 큰 수가 생겨서 수식에 모순이 생기게 됩니다.

array의 모든 수가 양수여서 minSum이 없는 경우에는 배열의 전체 totalSum이 문제의 해답이 되고, 케이스 1에서 찾아낼 수 있습니다.

즉 array의 minSum을 찾아 totalSum에서 뺀다면 원형으로 이어진 maxSum을 알아낼 수 있습니다.

minSum을 찾는 메소드를 따로 작성해도 되지만 기존의 메소드를 이용하되 입력 배열의 부호를 바꿔주면 똑같이 구할 수 있습니다. 다만 모든 수가 음수인 경우(minSum == totalSum)에는 예외가 발생하므로 그 부분만 따로 처리해주시면 됩니다.

class Solution:
    def maxSubarraySumCircular(self, nums: list) -> int:
        nonCircularSum = self.maxSubArray(nums)
        circularSum = sum(nums)
        
        for i in range(0,len(nums)):
            nums[i] = -nums[i]
        
        circularSum += self.maxSubArray(nums)
        
        return max(nonCircularSum,circularSum) if(circularSum != 0) else nonCircularSum
    
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[1,-2,3,-2],[5,-3,5],[-3,-2,-3]]
for i in input:
    print(Solution().maxSubarraySumCircular(i))