Pori_IT

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

문제: H-Index

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

풀이

H인덱스에 대한 개념을 이해하는 게 가장 어려웠던 문제다.

주어진 citations 은 각 논문의 인용 횟수를 말한다.

어떤 과학자가 발표한 논문 n편 중,

h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면

h의 최댓값이 이 과학자의 H-Index입니다.

일단 그럼 n번 인용된 논문을 파악해 본다. 이해를 위해 정렬을 우선 수행한다. [0,1,3,5,6]

1번 인덱스의 인용 횟수: 0회 / 0회 이상 인용된 논문의 수 5개 / 5편 이상 인용된 논문이 5편 이상이다.
=> 1,3 은 5편 이하로 인용되었다. => false

2번 인덱스의 인용 횟수: 1회 / 1회 이상 인용된 논문의 수 4개 / 4편 이상 인용된 논문이 4편 이상이다
=> 1,3은 4편 이하로 인용되었다. => false

코드의 동작 예시

 i = [1,3]

j = [0,1,3,5,6]

# 1인 경우

j>=i => 1,3,4,6 => count =4  1회 이상 인용된 논문의 수 4개

i>=count 등호가 들어가있기 때문에 우선 자기 자신부터 인용된 논문의 수와 같아야 한다.

# 3인경우

j>=i => 3,4,6 => count =3  1회 이상 인용된 논문의 수 3개

i>=count 등호가 들어가 있기 때문에 우선 자기 자신부터 인용된 논문의 수와 같아야 한다. => 그런데 같다. 그럼 후보에 올릴 수 있다.

마지막은 후보들 중에서 최댓값 h를 찾아주면 된다.

def solution(citations):
    new_cit = []
    for i in citations:
        if i == 0:
            pass
        else:
            count = 0
            for j in citations:
                if j>=i:
                    count+=1
            if i>=count:
                new_cit.append([i,count])
    new_cit.sort(key = lambda x:x[1],reverse=True)
    
    if new_cit:
        return new_cit[0][1]
    else:
        return 0

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

문제: 카드 뭉치

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/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, 독서