import heapq
import sys
input = sys.stdin.readline
N = int(input())

times = []
for _ in range(N):
    input_tuple = tuple(map(int,input().split()))
    heapq.heappush(times,input_tuple)

end_time_list = []
answer = 0
while times:
    start_time,end_time = heapq.heappop(times)
    if not end_time_list:
        answer += 1
        heapq.heappush(end_time_list,end_time)
    else:
        if end_time_list[0] > start_time:
            heapq.heappush(end_time_list,end_time)
            answer += 1
        else:
            heapq.heappop(end_time_list)
            heapq.heappush(end_time_list,end_time)
            
        
print(answer)

우선순위 힙을 응용한 문제이다. 먼저 (시작시간,종료시간)이 입력을 들어왔을때, 하나의 리스트에 저장을 해준다.

그리고 그것을 시작시간을 기준으로 정렬을 해준다.

그리고 하나씩 꺼내면서 판단을 해주면 된다.

end_time_list가 비워져있으면, 종료시간을 그냥 넣어준다.

end_time_list의 첫번째 값 즉. 가장 먼저 강의가 종료되는 시간보다, 현재 강의의 시작시간이 더 빠르면(작으면) 강의실을 여러개 구해야한다.

그러므로 answer를 +1 해주고, end_time_list에 현재 강의의 종료시간을 넣어준다.

그렇지 않을시에는, 강의실을 추가로 빌린필요가 없으므로, 가장 첫번째 값을 없애고, 현재 강의 종료시간을 end_time_list에 저장을 시켜준다.

end_time_list의 가장 첫번째 값은 가장 작은 값으로 유지되어야하므로, 우선순위 큐인 heapq를 사용했다.

import heapq
import sys
input = sys.stdin.readline

N = int(input())
class_list = []
for _ in range(N):
    start_time,end_time = map(int,input().split())
    class_list.append((start_time,end_time))

class_list.sort()
end_time_list = []
for start_time,end_time in class_list:
    if end_time_list:
        if end_time_list[0] <= start_time:
            heapq.heappop(end_time_list)
        heapq.heappush(end_time_list,end_time)
    else:
        heapq.heappush(end_time_list,end_time)

print(len(end_time_list))

좀 더 깔끔한 방식으로 푼 코드이다. 강의의 전체 정보를 저장하는 리스트는 굳이, 우선순위 힙을 쓸필요가 없으므로, 일반리스트로 쓰면서 정렬을 해줬다.

그리고 다른 변수로 answer를 저장하던걸 어차피, end_time_list의 길이와 답이 일치하므로, end_time_list의 길이로 답을 출력해주었다.

import heapq
import sys
input = sys.stdin.readline
def dijkstra(start_list,flag):
    global V,mac,star,INF,limit_x,limit_y,home_info
    distance = [INF]*(V+1)
    node_list = []
    limited = limit_x
    if flag:
        limited = limit_y
    for ind in start_list:
        distance[ind] = 0 
        heapq.heappush(node_list,(0,ind))

    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > limited:
            break
        if current_distance > distance[node]:
            continue
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    for ind in home:
        if limited >= distance[ind]:
            home_info[ind][int(flag)] = distance[ind]
    

V,E = map(int,input().split())
INF = float('inf')
graph = [{} for _ in range(V+1)]

for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u][v] = w
    graph[v][u] = w
mac_cnt,limit_x = map(int,input().split())
mac = set(map(int,input().split())) 
star_cnt,limit_y = map(int,input().split())
star = set(map(int,input().split()))

home = set(range(1,V+1))- mac - star
home_info = [[INF,INF] for _ in range(V+1)]

dijkstra(mac,False)
dijkstra(star,True)
min_sum = INF
for home_ind in home:
    if sum(home_info[home_ind]) < min_sum:
        min_sum = sum(home_info[home_ind]) 

if min_sum != INF:
    print(min_sum)
else:
    print(-1)

  다익스트라를 응용한문제이다. 처음에 집을 기준으로 하니 시간초과가 떴다.

그래서 역으로 맥도날드와 스타벅스를 각각을 기준으로 해서 다익스트라를 했다.

맥도날드를 각각의 시작점으로해서 집들하고 가장 짧은 거리를 갱신을 해주면된다. 그리고 이걸 저장할 때 x를 넘지 않는 경우에만 home_info 라는 리스트에 저장을 해줬다.

스타벅스도 동일하게 해주었다.

그리고 난뒤 마지막에 최저합을 구해서 출력을 해주었다.

N = int(input())


arr = list(map(int,input().split()))

start = 0
end = N-1
index_list = (arr[start],arr[end])
result = arr[end]+arr[start]

while start<end:
    temp = arr[end]+arr[start]
    if abs(result) > abs(temp):
        result = temp
        index_list = (arr[start],arr[end])
        if result == 0:
            break
    if temp >= 0:
        end -= 1
    else:
        start += 1


print(*index_list)

두 용액 문제하고 동일하다. 투 포인터를 이용해서 풀어주면 된다.

3일차

1. 비교 연산자

1.1 비교 연산자

• 비교 연산자는 불린형을 반환한다.

• 문자열을 비교할때, 유니코드 순으로 비교를 하고, 뒤쪽의 문자열 일수록 크다고 생각한다.

• 각 위치별로 비교를 하고, 한쪽이 크면 큰 곳의 값을 반환하고, 종료한다.

• 만약 비교가 종료되었는데도, 동일하고 한쪽 문자열의 길이가 더 길다면, 긴 문자열이 더 크다고 결론 낸다.

  alert('B'>'C') //false
  alert('BEE'>'BE') //true

• 만약 다른형을 가진 값끼리 비교를 했을 때에는, 이 값들을 숫자형으로 변환 뒤 비교를 한다.

  alert('2'>1) //true
  alert('0'==0) // true
  alert(true == 0) //false

• 문자열 '0'은 Boolean으로 판단시 false가 나오지만, 비교연산자로 0과 비교시 true를 반환한다.

  • 그 이유는 위의 설명과 같이 문자열을 숫자형으로 바꿔서 비교했기 때문이다.

1.2 일치 연산자

• 비교연산자 중 비교 연산자는 0과 false를 구분하지 못하므로, 좀더 엄격하게 비교를 할때에는 일치 연산자 를 사용하여, 값을 비교한다.
• 일치연산자나 불일치연산자(!==)를 사용하면, 형변환 없이 값을 비교할 수 있으므로, 좀 더 엄격하게 비교할때 사용이 된다.

1.3 null과 undefined

• null과 undefined를 일치연산자를 하면, 자료형이 달라서 false를 반환하지만, 동등연산자인 ==를 하면 true를 반환한다.

alert(null == undefined)  // true
alert(null === undefined )//false

• 그러나, 비교연산자를 이용해 null은 0으로 변환, undefined는 NaN으로 변환된다.
• null과 undefined는 동등연산자 ==일때는 형변환을 하지 않고, 비교연산자인 >= ,>일때는 형변환을 한다.

alert( undefined > 0 ); // false (1)
alert( undefined < 0 ); // false (2)
alert( undefined == 0 ); // false (3)

• undefined와 null은 동등연산자에서 null이나 undefined가 아니면 false를 반환한다.

2. if와 '?'를 사용한 조건 처리

2.1 if문

• if문은 괄호안의 조건을 평가해, 그 결과가 true라면 코드 블록을 실행한다.
• if문은 괄호안의 조건을 불린값을 변환한다.
  • 0,"",null,undefined,NaN 값은 false로 변환, 그 외의 값은 true로 반환한다.
• if문의 코드블록은 단 한줄이더라도 {}중괄호롤 감싸는걸 추천한다.

2.2 else 문

• else문은 if문 안의 조건이 false일 때 실행된다.

2.3 else if 로 복수 조건 처리하기

• 다수의 조건을 처리할 때, if문 뒤에 else if문을 더 붙여 조건을 판단한다.

2.4 조건부 연산자 ?

• 조건부 연산자는 if문을 좀 더 간결하게 표현가능하다.

  let result = condition ? value1 ? value2
  // condition이 참이면, value1을 반환, 거짓이면 value2를 반환

2.5 다중 ?

let result = (condition1) ? value1 : 
(condition2) ? value2 : 
(condition3) ? value3 :
value4;

• 위의 예시의 같은 경우 codition1이 참이면 value1, 거짓이면 두번째 condition2로 간다.
• condition2가 참이면 value2를 거짓이면 condition3로 간다.
• condition3이 참이면 value3 거짓이면 value4를 반환한다.

if (condition1) {
    result = value1
} else if (condition2){
    result = value2
} else if (condition3) {
    result = value3
} else{
    result = value4
}

• 위의 다중 ?은 다음과 같이 나타낼수 있다.

Appendix

• 조건부 연산자 ?를 남용하지 말고, 조건에 따라 다른 반환값을 할당해야할때만 쓰는 것을 추천한다.

3. 논리 연산자

• 논리연산자에는 `||`(OR),`&&`(AND),`!`(NOT)이 있다.

• `OR`와 `AND`는 파이썬과 같은 단축평가를 한다.

• `OR`연산자는 가장 첫번째 `truthly`인 피연산자를 반환하고, 만약 전부 `false`일시에는 마지막 피연산자를 반환한다.

alert(""||0||5) //5
alert(""||5||0) //5

• `AND`연산자는 `OR`과 반대로 첫번쨰 `falsy`인 피연산자를 찾는다. 첫번쨰 `falsy`인 피연산자를 반환하고, 만약 전부 `true`일 시에는 마지막 피연산자를 반환한다.

alert(5&&0&&3) // 0
alert(5&&4&&2) //2

• `AND` 연산자가 `OR` 연산자보다 우선순위가 높다.

• `Not`연산자는 느낌표인 `!`을 쓰는데, 먼저 피연산자를 불린형으로 변환후 이에 반대되는 값을 반환해준다.

• 위와 같은 특징을 이용하면, `!!` 와 같이 `Not`연산자를 두개 연속으로 쓸시에는 `Boolean` 함수를 쓴것과 동일한 효과를 나타낸다.

• `Not`은 논리연산자 중 가장 높은 우선순위에 있다.

4. null 병합 연산자

• 병합연산자인 ``??``를 사용하면, 짧은 문법으로 그 값이 **확정되어있는** 변수를 찾을수 있다.

  x = a ?? b
  x = (a !== null && a!== undefined) ? a : b;

• 위의 두 로직이 같다고 할 수 있다.

• `??`와 `||`(OR)와 비슷하다고 생각할 수 있지만, `||`는 첫번쨰 `truthy` 값을 반환하는데 반해 `??`은 **정의된** 값을 반환하는게 다르다.

alert(0 || 100) // 100
alert(0 ?? 100) // 0

• `OR`연산자는 숫자 0 은 `false`이므로, 100을 반환해주고, `??`은 연산자는 0이라는 정의되므로, 0을 반환해준다.

• `??`연산자는 `||`와 `&&`연산자와 동시에 사용하는것을 금지한다! 함께 사용시 문법에러가 발생한다.

3일차 소감

• 잘 모르던 null 병합연산자와, `?`을 이용한 다중 조건 처리

• 일치 연산자에서 `null`과 `undefined`의 동작방식에 대해 잘 알 수 있었다.

출처 : 모던 자바스크립트 튜토리얼

def dfs(W,H):
    if W == 0:
        return 1
    if dp[W][H]:
        return dp[W][H]
    dp[W][H] = dfs(W-1,H+1)
    if H>0:
        dp[W][H] += dfs(W,H-1)
    return dp[W][H]



while True:
    N = int(input())

    if not N:
        break
    dp = [[0]*31 for _ in range(N+1)]

    print(dfs(N,0))

재귀적으로 푸는 방식이다.

한알로 먹는 먹을수 있는 개수를 W, 반알로 먹을 수 있는 개수를 H로 두고 재귀적으로 풀면 된다.

원래 들어온 W,H에서 기본적으로 W가 남아있으면, 한알을 꺼내먹을수 있기에 W-1,H+1로 함수를 실행시켜준다.

그리고 만약 H가 있다면, 반알을 먹을수도 있으므로, W,H-1로 함수를 실행시켜준다.

그러다가 한알짜리 알약이 전부 떨어지면, 남은경우는 반알을 전부 먹는것이므로 return 1을 해주며, 중단해준다.

이렇게 해서 전체 날짜에서 먹을수 있는 날짜를 구하면 된다.

dp = 31*[0]
dp[1] = 1
dp[0] = 1


for n in range(2,31):
    for i in range(n):
        dp[n] += dp[i]*dp[n-i-1]

while True:
    N = int(input())
    if not N:
        break
    print(dp[N])

 위와 같은 형태의 문제를 카탈란 수라고 한다. 자세한 설명은 아래의 사이트에서 읽어보면 된다.

   카탈란 수 설명 출처 : suhak.tistory.com/77

카탈란 수의 점화식을 이용해서 쉽게 푸는 방법도 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))
    visited = set()
    visited.add((N,M))
    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                if nodes not in visited:
                    visited.add(nodes)
                    stack.append(nodes)
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

 처음으로 풀어본 영어로 된 문제이다. 영어로 되어있는 것을 제외하고는 그렇게 어렵지 않은 문제이고, python으로 통과한 사람들이 적다보니 통과시간에 걸릴까 걱정했는데 처음에는 아슬아슬하게 통과했다.

제한시간 2초인데 1.9초가 떴었다.

문제를 봐보면 일반적인 방탈출 게임 같아보인다. 하지만 여기서는 상하좌우로 움직이던 일반적인 bfs가 아닌 현재 내가 밟은 위치에 있는 값에 따라 움직일 수 있는 위치가 달라진다.

그 방법은 현재 내가 밟고있는 index에 위치한 값의 약수 쌍의 좌표로만 옮겨갈수 있다

예를 들면 

3 10 8 14

1 11 12 12

6 2 3 9

문제에 있는 3*4 배열을 봐보면

처음 시작 위치는 (1,1)이다. 그 위치에 있는 값은 3이므로, 3의 약수는 (1,3) (3,1)로 갈 수 있다.

그러면 다음 위치는 (1,3) 이나 (3,1)이 될수 있는데

만약 (1,3)이라한다면 (1,3)에 있는 값은 8 이다. 8의 약수는 (1,8) (2,4),(4,2),(8,1)이 존재할 수 있는데,

(4,2),(8,1),(1,8)은 범위를 넘어가므로, 갈 수 없다.

그러므로 (2,4)로 갈 수 있다.

이런식으로 jump를 해서 우측 최하단에 도착하는 게임이다.

도착이 가능하면 yes 불가능하면 no를 출력해주면 된다.

처음에는 약수를 구하는 생각을 해봤는데, 주어진 행렬의 최대가 1000*1000이다. 거기에 주어지는 최대값은 100만이다.

100만에 대한 모든 약수를 구하다보면  10억번 정도의 연산이 필요로 할 것 같아서, 폐기했다.

그 다음으로 생각한 방법이 위의 풀이이다.

역으로 올라가보자는 것이다.

우리가 (N,M)에 도착하기 위해서 무조건 배열 내에 N*M인 값이 존재해야한다.

1. N*M을 가지고 있는 위치를 찾아간다.

2. 그 위치에 도달할 수 있는 값을 찾아서 또 이동한다.

위와 같은 로직을 생각했다.

즉, 위의 예제로 설명하면

(3,4)에 도착하기 위해서는 12의 값이 필요한데, 이 12를 가진 발판의 위치는 (2,3),(2,4)이다.

(2,3)에 도착하기 위해서는 6의 값이 필요한데 6이 존재하는 위치는 (3,1)이다.

(2,4)에 도착하기 위해서는 8의 값이 필요한데 8이 존재하는 위치는 (1,3)이다.

(3,1),(1,3)에 도착하기 위해서는 3의 값이 필요한데 3이 존재하는 위치는 (1,1) 아니면 (3,3)이다.

이렇게 해서 풀 수 있다.

from collections import deque
def bfs():
    global N,M
    stack = deque()
    stack.append((N,M))

    while stack:
        x,y = stack.pop()
        if x == 1 and y == 1:
            return 'yes'
        if dict_array.get(x*y):
            for nodes in dict_array[x*y]:
                stack.append(nodes)
            del dict_array[x*y]
    return 'no'

N = int(input())
M = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dict_array = {}
for x in range(N):
    for y in range(M):
        if dict_array.get(arr[x][y]):
            dict_array[arr[x][y]].append((x+1,y+1))
        else:
            dict_array[arr[x][y]] = [(x+1,y+1)]

if dict_array.get(N*M):
    print(bfs())
else:
    print('no')

이 코드는 위의걸 개선한 코드이다. 방문표시를 하기위해서 visited를 쓰는대신 한번 방문한 곳은 전부 지워버렸다.

2일차 자바스크립트 스터디

1. alert,prompt,confirm을 이용한 상호작용

1.1 alert

• alert 창은 작은 모달창을 띄우고, 사용자가 모달창 내의 버튼을 누르기 전까지 나머지 부분과 상호작용이 불가능하다.

1.2 prompt

prompt(title,[default])

• prompt는 사용자에게서 입력을 받을 수 있는 창을 띄우고, 사용자가 입력을 하기도 하며, 취소를 누를수도 있다.
• 만약 사용자가 입력할시 문자열을 반환 해주고, 취소할시에는 null 값을 반환한다.
• defalut는 초기값을 뜻하며, 필수요소는 아니다.

1.3 confirm

confirm(question)

• confirm은 매개변수로 받은 question에 대한 확인 취소 버튼이 있는 모달창을 보여준다.
• 확인 버튼은 true 그외의 행동은 false를 반환한다.

1.4 요약

• 모달 창의 위치는 브라우저가 결정하고, 대개 브라우저의 중앙에 위치한다.
• 그리고 위 모달창을 떠 있는 시간 동안은 스크립트의 실행이 일시 중단되고, 사용자가 창을 닫기 전까지는 나머지 페이지와 상호작용이 안된다.
• 모달 창의 모양은 브라우저마다 다르고, 개발자가 모달창의 모양을 수정할 수 없다.

2. 형 변환

함수와 연산자에 전달되는 값은 적절한 자료형으로 자동 변환된다. 이런 과정을 형변환 이라고 한다.

형변환은 전달받은 값을 의도를 갖고 원하는 타입으로 변환을 할때에도 해당된다.

2.1 문자형으로 변환

let value = 123
value = String(value)
alert(typeof value)

• 문자형은 대부분 예측 가능한 방식으로 일어난다.

2.2 숫자형으로 변환

let str = '123'
alert(typeof str) // string
let num = Number(str)
alert(typeof num) // number

• 숫자형으로 형변환시, 숫자 이외의 글자가 들어있는 문자열을 숫자형으로 변환시 NaN이 된다.
• undefined -> NaN
• null -> 0
• true,false ->0,1
• string -> 양 끝의 공백을 제거 후 공백제거 후 남아있는 문자열이 없으면 0 문자열내에 숫자를 제외한 문자가 있으면 NaN이 반환된다.

2.3 불린형으로 변환

alert(Boolean(1)) //true
alert(Boolean(0)) //false

• 숫자 0, 빈 문자열 ,null,undefined,NaN과 같은 값들은 false가 된다
• 문자열 "0"과 " " 은 false가 아닌 true가 반환된다.

3. 기본 연산자와 수학

• 피연산자를 하나만 받는 연산자는 단항 연산자
• 두개의 피 연산자를 받는 연산자는 이항 연산자

3.1 수학 연산자

• *,(곱셈)

• +(덧셈)

• -(뺄셈)

• /(나눗셈),

• %(나머지연산자)

• **(거듭제곱)

3.2 이항 연산자 +와 문자열 연결

• 덧셈 연산자는 피연산자로 문자열이 전달되면 덧셈연산자는 덧셈이 아닌 문자열을 병합을 한다.
• 두개의 피연산자 중 하나가 문자열이면, 다른 하나도 자동으로 문자열로 형 변환을 해서, 병합을 한다.

alert(2+2+'1') // 4+'1'이 되어 '41'이 출력된다.

• +가 아닌 다른 수학연산자는 피연산자를 숫자형으로 변환시키고 계산하는 것과 대조적이다.

3.3 단항 연산자 +와 숫자형으로의 변환

• 덧셈 연산자는 단항 연산자로 쓰인다.
• 단항연산자로 쓰일때에는 문자열인 숫자를 숫자형으로 변환을 해준다. Number와 동일한 일을 해준다.

Appendix

• 연산자 우선순위 표 를 보면, 각 연산자마다 우선순위가 있고, 우선순위가 높은것부터 적용된다.

3.4 할당연산자

• =도 할당 연산자이기 때문에 x = value라 하면, x에 value를 할당하고, 그 값인 value를 반환한다.

• 위와 같은 특징을 이용해 다음과 같은 예제도 가능하다.

  let a = 1;
  let b = 2;
  
  let c = 3 - (a = b + 1);
  
  alert( a ); // 3
  alert( c ); // 0

• b+1이 a에 할당되고, 할당된 값 3이 그대로 반환되어 3-3을 연산하여, c에 0이 할당된다.

• 할당 연산자 체이닝

  • let a, b, c;
    
    a = b = c = 2 + 2;
    
    alert( a ); // 4
    alert( b ); // 4
    alert( c ); // 4

  • 위의 특징을 이용해서, 할당 연산자 체이닝이 가능하지만, 가독성이 좋지 않으므로, 추천하지 않는 방식이다.

3.5 복합 할당 연산자

• 복합할당 연산자는 짧은 문법으로 연산을 하고 싶을때 쓰인다.
• +=,/=,*= 등을 쓸 수 있다.
• 복합할당 연산자의 우선순위는 할당 연산자와 동일 하므로, 다른 연산자가 실행된 후 복합할당 연산자가 실행된다.

let n = 2;

n *= 3 + 5;

alert( n ); // 16  (*=의 우측이 먼저 평가되므로, 위 식은 n *= 8과 동일합니다.)

3.6 증가 감소 연산자

• 증가/ 감소연산자는 변수에만 쓸 수 있다.

• 숫자를 하나 늘리거나 줄이는 것에 자주 사용되는 연산자.

• 종류에는 후위, 전위 연산자가 있는데, 위치에 따라 반환되는 값이 다르다.

• 기본적으로 같은 연산을 하지만 전위 연산자 같은 경우, 먼저 증가/감소 연산을 한뒤, 그 값을 반환을 해준다.

• 후위 연산자같은 경우, 원래의 값을 반환을 한뒤, 증가/감소 연산을 해준다.

  let counter = 1;
  let a = ++counter; // (*)
  
  alert(a); // 2
  
  let counter = 1;
  let a = counter++; // (*) ++counter를 counter++로 바꿈
  
  alert(a); // 1

3.7 비트 연산자

• 32비트 정수로 변환하여, 이진 연산을 수행하는 연산자이다.
• AND &
• OR |
• XOR ^
• NOT ~
• 왼쪽 쉬프트 <<
• 오른쪽 쉬프트 >>
• 부호 없는 오른쪽 시프트 >>>

3.8 쉼표 연산자

• 쉼표 연산자는 자주 쓰이지는 않지만, 알아두면 좋은 연산자.
• 기본적으로 할당 연산자 인 =보다 낮으므로, 연산을 할때 주의해야한다.
• 왼쪽부터, 오른쪽으로 점차 평가하면서, 가장 오른쪽에 있는 값을 반환해준다.

2일차 소감

• 오랜만의 공부이면서, 가장 기초적인 것을 복습하는 느낌이다.
• 보통 감으로 예측했던 이항연산자에서의 +의 작동방식이나, 이항연산자에서 +을 제외한 나머지 연산자의 작동방식에 대해서 다시 공부한 느낌이다.
• 일단 이번주 목표는 6-11까지 끝내는게 목표이다. 좀 더 속도를 높여야겠다.

출처 : 모던 자바스크립트 튜토리얼

from collections import deque
import bisect
import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    stack = deque()
    stack_dict = dict()
    for _ in range(int(input())):
        command,val = input().split()
        val = int(val)
        if command == 'I':
            if stack_dict.get(val):
                stack_dict[val] += 1
            else:
                bisect.insort_left(stack,val)
                stack_dict[val] = 1
        else:
            if val == 1:
                if stack:
                    last_number = stack[-1]
                    if stack_dict[last_number] == 1:
                        stack_dict.pop(last_number)
                        stack.pop()
                    else: 
                        stack_dict[last_number] -= 1
            else:
                if stack:
                    first_number = stack[0]
                    if stack_dict[first_number] == 1:
                        stack_dict.pop(first_number)
                        stack.popleft()
                    else:
                        stack_dict[first_number] -= 1
    if stack:
        print(stack[-1],stack[0])
    else:
        print('EMPTY')

정렬된 행렬일때 쓸 수 있는 bisect 라이브러리를 이용해서, 이진탐색 후, deque에 넣어주었다.

뺄때 매번 insert, pop을 하면 연산시간이 오래걸리므로, dictionary로 개수를 세주었고, dictionary가 0이 될때 pop을 해주었다.