본문 바로가기

전체 글

 (171)
[프로그래머스][Python] 이중우선순위큐 문제를 정리해보자. l 숫자 => 큐에 숫자 삽입 D 1 => 큐에서 최댓값 삭제 D -1 => 큐에서 최솟값 삭제 단, 큐가 비어있는 상태에서 D 명령이 들어오면 무시한다. 최종 결과는 큐가 비어있다면 [0, 0]으로 아니라면, [최댓값, 최솟값]으로 출력한다. 리스트에 값을 넣을 때마다 정렬하는 방법을 선택했다. from collections import deque def solution(operations): li = [] for string in operations: alpha, num = string.split() if alpha == "I": # 삽입 li.append(int(num)) li = deque(sorted(li)) elif li: if alpha == "D" and num == "..
[프로그래머스][Python] H-Index 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 문제를 잘 이해해보자. 1) h번 이상 인용된 논문이 h편 이상이다. 2) 나머지 논문은 h번 이하 인용한다. 1), 2)를 만족하는 h의 최댓값을 구하여라 위 예시처럼, 먼저 배열을 오름차순으로 정렬한다. 정렬하면 n - index는 해당 값의 편 수가 된다. ( 물론 내림차순으로 하고 index + 1을 편 수로 잡아도 된다. ) 이때 각 값의 h값은 value와 n - index 중 더 작은 값이 된다. 예를 들어, 9번 이상은 4편이 있다. 여기서 h값으로 최대는 4이다. 그리고 2)는 고려할 필요가 없다. 무조건 만족하기 때문이다. 추..
[정렬] 병합 정렬 [Merge Sort] 병합 또는 합병 정렬에 대해 알아보자. 이는 분할 정복 방법을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 퀵 정렬과 함께 빠른 정렬에 해당한다. 예를 들어보자. [6, 5, 3, 1, 8, 7, 2, 4] 숫자 1 ~ 8까지 들어있는 배열이 있다. 먼저 하나의 배열을 두 개로 쪼갠다. [6, 5, 3, 1] [8, 7, 2, 4] 그리고 다시 각 배열을 두 개로 쪼갠다. [6, 5] [3, 1] [8, 7] [2, 4] 또다시 각 배열을 두 개로 쪼갠다. [6] [5] [3] [1] [8] [7] [2] [4] 이제 더 이상 배열을 쪼갤 수 없다. 이제 두 개의 배열씩 합친다. 합칠 때는 둘 중에 값이 더..

티스토리툴바