글 읽기 - 7662 질문드립니다.

odh0112 2년 전 0

안녕하세요. 다른 분들은 heap을 이용해서 해결했지만 저는 deque을 이용해서 해결해 보았습니다.

하지만 결과가 틀렸다고 나오는데, 예제들과 질문하기에 있는 반례들을 넣어봤을 때 틀리는게 없습니다ㅠㅠㅠ

혹시 지적할 부분이 있다면 따끔하게 지적 부탁드리겠습니다!! 감사합니다 :))

from collections import deque
import sys
input = sys.stdin.readline

def check(flag, n):
    global queue
    if flag == 'I':
        if len(queue) == 0:
            queue.append(int(n))
        elif queue[-1] < int(n):
            queue.append(int(n))
        else:
            queue.appendleft(int(n))
    else:
        n = list(map(str, n)) # 부호 나눠주기
        if len(queue) == 0:
            return
        elif n[0] == '-': # 최솟값 삭제
            queue.popleft()
        else: # 최댓값 삭제
            queue.pop()

T = int(input())

for i in range(T):
    K = int(input())
    queue = deque()

    for j in range(K):
        flag, n = list(map(str, input().split()))
        check(flag, n)

    if len(queue) == 0:
        print('EMPTY')
    else:
        print(max(queue), min(queue))    

minkc01 2년 전 1

I 10

I -10

I -5

D -1

오답: 10 -10

정답: 10 -5

I 10, I -10, I -5에서 -> 10 -10 -5

D -1에서 최솟값 삭제 -> 10 -5

연산처리 후 최댓값 = 10, 최솟값 = -5

odh0112 2년 전 0

답글 감사합니다 :))

최솟값 처리 안되는 부분을 어떻게 처리해야 될 지 몰라서 set으로 변경해서 코드 작성 했습니다.

하지만 이 코드는 시간초과가 발생하는데 피드백 주실 수 있으실까요?

import sys
input = sys.stdin.readline

def check(flag, n):
    global queue
    if flag == 'I':
        if len(queue) == 0: # 값이 비어 있으면 그냥 추가
            queue.add(int(n))
        else: # 최솟값이면 왼쪽에 배치
            queue.add(int(n))
    else:
        n = list(map(str, n)) # 부호 나눠주기
        if len(queue) == 0:
            return
        elif n[0] == '-': # 최솟값 삭제
            queue.remove(min(queue))
        else: # 최댓값 삭제
            queue.remove(max(queue))

T = int(input())

for i in range(T):
    K = int(input())
    queue = set()

    for j in range(K):
        flag, n = list(map(str, input().split()))
        check(flag, n)

    if len(queue) == 0:
        print('EMPTY')
    else:
        print(max(queue), min(queue))

minkc01 2년 전 1

min max 시간복잡도가 O(n)일거 같은데 그럼 전체 시간복잡도가 O(n^2)이 됩니다.

또 문제에서 같은 정수가 여러번 추가될 수 있다고 되어있네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7662 질문드립니다.

odh0112 2년 전 0

minkc01 2년 전 1

odh0112 2년 전 0

minkc01 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말