Pori_IT

오늘의 학습 키워드:  리스트

문제: 카드 뭉치

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

풀이

goal의 단어들을 순차적으로 돌리면서 그때마다 값이 카드 뭉치들의 처음에 있는지 확인하면 된다.

def solution(cards1, cards2, goal):
    for i in goal:
        if cards1 and i == cards1[0]:
            cards1 = cards1[1:]
        elif cards2 and i == cards2[0]:
            cards2 = cards2[1:]
        else:
            return "No"
    return "Yes"

오늘의 학습 키워드:  힙

문제: 이중우선순위큐

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

풀이

조건 중에 최댓값을 빼야 하는 경우에만 힙을 뒤집어주는 연산을 수행했다.

효율성이나 다른 테스트에서 그렇게까지 시간을 잡아먹는 케이스가 없다고 판단. 마지막 최대 최솟값 추출은 max, min함수를 사용했다.

from heapq import heapify, heappop, heappush
def solution(operations):
    answer = []
    h = []
    
    for o in operations:
        operation, value = o.split(" ")
        value = int(value)
        if operation == 'I':
            heappush(h,value)
        else:
            if value > 0:
                try:
                    h = [-1*i for i in h]
                    heapify(h)
                    heappop(h)
                    h = [-1*i for i in h]
                    heapify(h)
                except:
                    pass
            else:
                try:
                    heappop(h)
                except:
                    pass
    if len(h)==0:
        return [0,0]
    else:
        return [max(h),min(h)]

뒤집는 방법의 수행은 모든 요소에 -1을 곱하는 O(n)과 힙의 재구성인 O(n)의 시간이 걸리기 때문에

O(n)의 시간복잡도를 갖습니다.

회고

정리를 하다 보니 놓친 부분들을 다시 보게 되는 것 같습니다.

내일 학습할 것.

SQL, Python, 독서

문제

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

[문제 포인트 짚기]

스킬의 코드는 2진수로 표현했을 때 각 bit로 구분될 수 있도록 2의 제곱수로 구성되어 있습니다.
예를 들어 어떤 개발자의 SKILL_CODE가 400 (=b'110010000')이라면,
이는 SKILLCODES 테이블에서 CODE가 256 (=b'100000000'), 128 (=b'10000000'),
16 (=b'10000')에 해당하는 스킬을 가졌다는 것을 의미합니다.

Front End 스킬을 가진 개발자의 정보를 조회 => AND 연산을 수행해야 한다!

풀이

AND 연산 수행하기

왜 AND연산인가? 둘 모두 참인 경우에만 결과도 참으로 나오기 때문이다.

이를 활용하여 위의 예를 다시 살펴보면 400 코드에 256이 어떻게 들어있는지 판별이 가능하다.

400 & 256을 수행해서 256이 나온다면 256은 400안에 들어있다는 의미가 된다.

이를 활용해 코드에 적용하면 된다.

SELECT DISTINCT(d.ID), d.EMAIL, d.FIRST_NAME, d.LAST_NAME
FROM DEVELOPERS d LEFT JOIN SKILLCODES s
    ON (d.SKILL_CODE & s.CODE <>0)
WHERE s.CATEGORY = 'Front End'
ORDER BY 1

카테고리가 Front End인 값들만 가져와서 JOIN을 이용해 값이 들어있는지 비교한 코드이다.

오늘의 학습 키워드:  힙

문제: 더 맵게

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

풀이

종료조건만 다르게 생각해서 두 방식으로 풀이했다.

구현 자체는 간단하나 시간 복잡도를 생각해야 하고, 이를 위해 heap 구조를 채용했다.

왜 Heap을 채용해야하는지 heap이 무엇인지 간단하게 알아보겠다.
Heap은 특정한 규칙을 만족하는 이진트리 자료구조이다. (특정 규칙: 최대, 최소)
특징: 완전 이진트리, 삽입&삭제 시 O(log N)의 시간복잡도 -> 배열이나 연결 리스트에 비해 매우 효율적이다.

1. 예외처리 방식

heappop이 실패하는 경우에 인덱스 에러를 반환합니다.

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        try:
            answer += 1
            made = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
            heapq.heappush(scoville, made)
        except IndexError:
            return -1  
    return answer

2. 명시적 조건 검사 & 무한 루프 방지

scoville의 길이가 짧은 경우 (1개 이하) 계산이 안 되는 경우를 탐지 & 값이 더 이상 변하지 않는 경우를 탐지하여 조건을 검사했습니다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) < 2:
            return -1
        answer += 1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        made = first + second * 2
        if made == first and made == second:
            return -1
        heapq.heappush(scoville, made)
    
    return answer

회고

오늘은 이외에도 독서 정리 및 SQL 정리를 진행했습니다.

프로그래머스에서 SQL문제를 실은 다 풀어서 이제는 정리 위주로 진행하며 복습할 계획입니다.

내일 학습할 것.

SQL, Python, 독서