프로그래머스 - 이중우선순위큐 (연결리스트)

이번 포스팅에서는 프로그래머스의 이중우선순위큐 (연결리스트) 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

문제 풀이

먼저 명령어가 “I 숫자” 일 경우를 만듭니다. 입력의 첫번째 글자를 확인하여 ‘I’라면 문자열의 세번째 자리부터 숫자임으로 [2:] 를 이용하여 숫자를 따로 추출 합니다.

from collections import deque

def solution(operations):
    nums = deque()
    for op in operations:
        if op[0] == 'I':
            nums.append(int(op[2:]))
    print(nums)

solution(["I 7","I 5","I -5","D -1"])

deque([7, 5, -5])

숫자가 추출 될때 nums라는 이름의 deque() 리스트에 저장합니다. 리스트의 값과 비교하여 숫자의 배열이 최소 부터 최대가 되도록 합니다.

from collections import deque

def solution(operations):
    nums = deque()
    for op in operations:
        if op[0] == 'I':  # 입력이 숫자일 경우
            num = int(op[2:])
            index = -1
            for i in range(len(nums)):
                if nums[i] >= num:
                    index = i
                    break
            if index != -1:  # nums 리스트에 입력보다 더 큰 숫자가 있을경우
                nums.insert(index, num)
            else:  # 비교할 nums 리스트에 값이 없거나 입력보다 큰 숫자가 없을 경우
                nums.append(num)
    print(nums)
    
solution(["I 7","I 5","I -5","D -1"])

deque([-5, 5, 7])

입력이 연산자일 경우를 추가 합니다. nums 값이 없을경우에는 해당 연산을 무시하고 값일 있을 경우 ‘1’일때는 pop()을 통해 최대값을 삭제하고 ‘-1’일 경우에는 popleft()를 통해 최소값을 삭제 합니다.

루프가 종료되면 마지막으로 리스트의 최대 값과 최소 값을 반환하며 리스트의 값이 없을때에는 [0,0]을 반환 합니다.

입력 예제를 추가하여 확인해 보면 아래와 같습니다.

from collections import deque

def solution(operations):
    nums = deque()
    for op in operations:
        if op[0] == 'I':  # 입력이 숫자일 경우
            num = int(op[2:])
            index = -1
            for i in range(len(nums)):
                if nums[i] >= num:
                    index = i
                    break
            if index != -1:  # nums 리스트에 입력보다 더 큰 숫자가 있을경우
                nums.insert(index, num)
            else:  # 비교할 nums 리스트에 값이 없거나 입력보다 큰 숫자가 없을 경우
                nums.append(num)
        else:  # 입력이 연산자일 경우
            if not nums:  # 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시
                continue
            if op[2:] == '1':  # 큐에서 최대값을 삭제
                nums.pop()
            else:  # 큐에서 최소값을 삭제 ('-1'일 경우)
                nums.popleft()
    if nums:
        return [nums[-1], nums[0]]
    else:
        return [0,0]

print(solution(["I 7","I 5","I -5","D -1"]))
print(solution(["I 16","D 1"]))
print(solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]))
print(solution(["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]))

[7, 5]
[0, 0]
[0, 0]
[333, -45]

결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.