[240511] 코딩테스트 문제풀이

1. N번쨰 큰 수

• 우선순위 큐 안에 들어있는 원소의 개수가 N개 미만이라면 : 일단 집어넣기
•  우선순위 큐 안에 들어있는 원소의 개수가 N개라면
•  1) 우선순위 큐의 최솟값 보다 작으면 -> 무시
• 2) 우선순위 큐 최솟값 제거 -> 현재 확인하고 있는 숫자를 우선순위 큐에 삽입

 

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

import heapq
n = int(input())
heap = []
heapq.heapify(heap)

for i in range(n) :
    A = list(map(int, input().split(" ")))
    for j in range(len(A)) :
        if len(heap) < n :
            heapq.heappush(heap, A[j])

        elif heap[0] < A[j] :
            heapq.heappop(heap)
            heapq.heappush(heap, A[j])

print(heap[0])

 

---

2.  크리스마스 선물

• 문제 정확히 읽기
  • a -> a개의 숫자

import heapq
n = int(input())
heap = []

for i in range(n) :
    number = list(map(int,input().split()))

    if number[0] == 0 :
        if len(heap) == 0 :
            print(-1)

        else :
            print(-int(heapq.heappop(heap)))

    else :
        for j in range(number[0]) :
            heapq.heappush(heap,-number[j+1] )

 

---

3. 이중 우선순위 큐

https://hongcoding.tistory.com/91

[백준] 14235 크리스마스 선물 (Python 파이썬)

# 이중 우선순위 큐

import heapq
from heapq import heapify
def solution(operations):
    heap = []
    for i in range(len(operations)) :
        a,b = operations[i].split(" ")

        if a  == 'I' :
            heapq.heappush(heap,(int(b), -int(b)))

        elif a == 'D' and b == '-1' :# 최솟값 삭제
            if len(heap) != 0 :
                heapq.heappop(heap)

        elif a == 'D' and b == '1' :
            if len(heap) != 0 :
                heap = [ (j,i) for i,j in heap]
                heapify(heap)
                heapq.heappop(heap)
                heap = [(j, i) for i, j in heap]
                heapify(heap)


    if len(heap) == 0 :
        answer = [0,0]
    else :
        min_number = heapq.heappop(heap)[0]
        heap = [(j, i) for i, j in heap]
        heapify(heap)
        max_number = -heapq.heappop(heap)[0]
        answer = [max_number,min_number]


    return answer

 

---

4. 타깃넘버

• dfs 이용
  • +1
    • -1
      • +1
      • -1
    • +1
      • +1
      • -1
  • 이런식으로,, dfs가 사용됨..  나는 바보 !! 

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

프로그래머스

cnt = 0
def dfs(numbers, target, current, idx) :
    global cnt
    if idx == len(numbers) :   # 다돌면 멈춰야됨
        if current == target :
            cnt += 1
        return

    dfs(numbers, target, current + numbers[idx], idx + 1)
    dfs(numbers, target, current - numbers[idx], idx + 1)

def solution(numbers, target):
    dfs (numbers, target, 0,0)
    return cnt

 

---

5. 숫자판 점프

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

def dfs(i,j,number) :
    if len(number) == 6 :
        if number not in result :
            result.append(number)
        return

    dx = [1,-1,0,0]
    dy = [0,0,-1,1]

    for k in range(4) :
        x = i + dx[k]
        y = j + dy[k]

        if 0<=x<5 and 0<=y<5 :
            dfs(x,y, number + A[x][y])


# input 값 받기
A = list()
for i in range(5) :
    A.append(list(map(str, input().split())))

result = []
for i in range(5) :
    for j in range(5) :
        dfs (i,j, A[i][j])

print(len(result))

 

---