Coding 공부

import sys
input = sys.stdin.readline
while True:
    N,M = map(int,input().split())
    if not N+M:
        break

    arr = [list(map(int,input().split())) for _ in range(N)]
    maze = [[0 for _ in range(M)] for _ in range(N)]
    for y in range(M):
        maze[0][y] = arr[0][y]
    for x in range(1,N):
        for y in range(M):
            if arr[x][y]:
                maze[x][y] = maze[x-1][y] + arr[x][y]

    result = 0

    for x in range(N):
        col_idx = 0
        stack = []
        while col_idx<M:
            if stack:
                if stack[-1] <= maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                    col_idx += 1
                else:
                    size_stack = len(stack)
                    min_value = stack[-1]
                    cu_idx = -1
                    for i in range(size_stack):
                        result = max(result,min_value*(i+1))
                        cu_idx -= 1
                        if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                            min_value = stack[cu_idx]
                    

                    if maze[x][col_idx]:
                        stack.append(maze[x][col_idx])
                    else:
                        stack.clear()
                    col_idx += 1

            else:
                if maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                col_idx += 1
        if stack:
            size_stack = len(stack)
            min_value = stack[-1]
            cu_idx = -1
            for i in range(size_stack):
                result = max(result,min_value*(i+1))
                cu_idx -= 1
                if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                    min_value = stack[cu_idx]

    print(result)

        

import sys
input = sys.stdin.readline

while True:
    N,M = map(int,input().split())

    arr = [[0] + list(map(int,input().split())) + [0] for i in range(N)]
    if N+M == 0:
        break
    for i in range(1,N):
        for j in range(1,M+1):
            if arr[i][j]:
                arr[i][j] = arr[i-1][j] + 1
    result = 0
    for i in range(N):
        stack = [0]
        for j in range(1,M+2):
            while stack and  arr[i][j] < arr[i][stack[-1]]:
                height = arr[i][stack[-1]]
                stack.pop()
                width = j-stack[-1] - 1
                result = max(result,height*width)
            stack.append(j)
    print(result)

import sys
input = sys.stdin.readline
def union_find(x,y):
    a = find_parent(x)
    b = find_parent(y)
    if a != b:
        make_set[b] = a
        friend_cnt[a] += friend_cnt[b]

    return a

def find_parent(A):
    if make_set[A] == A:
        return A
    make_set[A] = find_parent(make_set[A])
    return make_set[A]


T = int(input())

for tc in range(T):
    F = int(input())
    person_dict = {}
    cnt = 1
    make_set = [k for k in range(F*2+1)]
    friend_cnt = [1 for k in range(F*2+1)]
    for _ in range(F):
        x,y = input().split()
        if x not in person_dict:
            person_dict[x] = cnt
            friend_cnt[person_dict[x]] = 1
            cnt += 1
        if person_dict.get(y) == None:
            person_dict[y] = cnt
            friend_cnt[person_dict[y]] = 1
            cnt += 1
        x_num = person_dict[x]
        y_num = person_dict[y]
        k = union_find(x_num,y_num)
        print(friend_cnt[k])

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1

def go():
    global command_index,string_index,pointer
    if commands[command_index] == '-':
        arr[pointer] = arr[pointer]-1
        if arr[pointer]<0:
            arr[pointer] = 255
    elif commands[command_index] == '+':
        arr[pointer] = arr[pointer] + 1
        if arr[pointer] > 255:
            arr[pointer] = 0
    elif commands[command_index] == '<':
        pointer -= 1
        if pointer < 0:
            pointer = memorysize -1
    elif commands[command_index] == '>':
        pointer += 1
        if pointer == memorysize:
            pointer = 0
    elif commands[command_index] == '[':
        if arr[pointer] == 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == ']':
        if arr[pointer] != 0:
            command_index = bracket_couple[command_index]
    elif commands[command_index] == '.':
        pass
    else:
        if string_index == inputsize:
            arr[pointer] = 255
        else:
            arr[pointer] = ord(strings[string_index])
            string_index += 1
    command_index += 1

T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_cnt <= MAX_NUMBER and command_index < codesize:
        command_cnt += 1
        go()
    if command_index == codesize:
        print('Terminates')
    else:
        while command_cnt >=0:
            command_cnt -= 1
            go()
            loop_idx = min(command_index,loop_idx)
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')

def find_brackt():
    for ind,command in enumerate(commands):
        if command == '[':
            bracket.append((ind,1))
        elif command == ']':
            bracket.append((ind,-1))
    brind = 0
    temp = []
    while brind < len(bracket): 
        if bracket[brind][1] == 1:
            temp.append(bracket[brind][0])
        else:
            open_bracket = temp.pop()
            bracket_couple[bracket[brind][0]] = open_bracket
            bracket_couple[open_bracket] = bracket[brind][0]
        brind += 1



T = int(input())
MAX_NUMBER = 50000000
for tc in range(T):
    memorysize,codesize,inputsize = map(int,input().split())
    pointer = 0 # 포인터가 가리키는 index
    arr = [0]*memorysize
    command_cnt = 0  # 명령 횟수
    commands = list(input())
    strings = list(input())
    command_index = 0  # 명령어의 위치
    string_index = 0
    result = 'Terminates'
    bracket = []
    bracket_couple = {}
    find_brackt()
    loop_flag = False
    loop_idx = float('inf')
    while command_index < codesize:
        if commands[command_index] == '-':
            arr[pointer] = (arr[pointer]-1)%(2**8)
        elif commands[command_index] == '+':
            arr[pointer] = (arr[pointer]+1)%(2**8)
        elif commands[command_index] == '<':
            pointer -= 1
            if pointer < 0:
                pointer = memorysize -1
        elif commands[command_index] == '>':
            pointer += 1
            if pointer == memorysize:
                pointer = 0
        elif commands[command_index] == '[':
            if arr[pointer] == 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == ']':
            if arr[pointer] != 0:
                command_index = bracket_couple[command_index]
        elif commands[command_index] == '.':
            pass
        else:
            if string_index == inputsize:
                arr[pointer] = 255
            else:
                arr[pointer] = ord(strings[string_index])
                string_index += 1
        command_index += 1
        command_cnt += 1
        if command_cnt > MAX_NUMBER:
            loop_idx = min(loop_idx,command_index)
        if command_cnt > MAX_NUMBER*2:
            loop_flag = True
            break
    
    if loop_flag:
        print(f'Loops {loop_idx-1} {bracket_couple[loop_idx-1]}')
    else:
        print('Terminates')

import sys
import heapq

input = sys.stdin.readline


N, K = map(int,input().split())

visited = [False]*K
jewel = []
for _ in range(N):
    m,v = map(int,input().split())
    heapq.heappush(jewel,(m,v))

bags = []
for _ in range(K):
    bags.append(int(input()))

bags.sort()
result = 0
possible_jewel = []
for bag in bags:
    while jewel and jewel[0][0] <= bag:
        m,v = heapq.heappop(jewel)
        heapq.heappush(possible_jewel,-v)
    
    if possible_jewel:
        result -= heapq.heappop(possible_jewel)
        
    

print(result)

N,K = map(int,input().split())

number =list(input())


result = [number[0]]
idx = 1
while K and idx <N:
    while result and K and number[idx] > result[-1]:
        result.pop()
        K -= 1
    result.append(number[idx])
    idx += 1
for _ in range(K):
    result.pop()
result = result + number[idx:]
print(''.join(result))

기본적인 원리는 다음과 같다.

반복문을 돌리면서 result에 마지막수보다 새로들어온 값이 클시에는 그 값들을 하나씩 빼준다. 그리고 난뒤 append를 해준다.

이렇게 끝까지 갔는데도, K가 남아있을시에는 남은 K만큼 pop을 해준다.

그리고, 만약 끝까지 가지 않았는데도, K만큼의 수를 이미 뺐다하면, 나머지 값들을 뒤에 붙여주면 된다.

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의 길이로 답을 출력해주었다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
apples = set(tuple(map(int,input().split())) for _ in range(K))
command_cnt = int(input())
# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
flag = True
next_time = commands[0][0]
break_flag = False
while True:
    if flag:
        next_time = commands[ind][0]


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if (next_x,next_y) not in snakes:
            if (next_x,next_y) in apples:
                snakes.appendleft((next_x,next_y))
                apples.remove((next_x,next_y))
            else:
                snakes.pop()
                snakes.appendleft((next_x,next_y))
        else:
            break_flag = True
    else:
        break_flag = True
    if break_flag:
        break



    if snake_times == next_time:
        snake_direction = (snake_direction + commands[ind][1])%4
        ind += 1
        if ind == command_cnt:
            flag = False
print(snake_times)

이 문제는 큐와 스택같은 자료구조에 대해서 알면 쉽게 풀 수 있는 문제이다.

물론 나는 오래걸렸다.

먼저 여기서는 방향 전환이 왼쪽, 오른쪽 밖에 없다. 만약에 동남서북(0,1,2,3) 형태로 방향을 저장해놓은 상태라면, 왼쪽일때는 -1을 해주고 오른쪽일때는 +1 을 해주고, 4로 나눈 나머지를 구해주면 된다.

기본적인 방법은 다음과 같다. snake는 기본적으로 deque 형태로 저장을 해준다.

먼저 snake_head를 기준으로 탐색해야한다. 나는 deque에서 왼쪽 즉 처음 들어온부분이 head로 가정했기 때문에, snake[0]을 가져온다. 그리고 snake의 방향에 맞게 진행을 해준다. 만약 범위를 벗어나거나 이미 snake에 있는 위치로 갈시, 예외처리를 해주고, 즉각적으로 멈출수 있게 break_flag를 해주었다.

그리고 둘 중 하나인데 만약에 뱀의 머리가 움직인 위치에 사과가 있을때에는, 뱀의 길이가 늘어난 것이기 때문에 새로운 head의 위치를 snake에 추가해주고, apple를 없애준다.

만약에 사과가 없을때에는 꼬리부분을 없애주고, 새로운 머리부분을 추가해준다.

매 타임마다 위와 같이 진행을 해주면 되는데, 여기서 명령어가 주어진다. 여기서 주의할 점은 시간이 끝난뒤 시행되는 것이기 때문에 time을 늘려주는 로직을 이 명령어를 조작하는 부분보다 상위에 두어야한다.

뱀이 움직이 시간이 끝난 시간과 명령어에 들어온 시간이 같으면 명령어 대로 방향을 바꿔준다.

그리고 이 명령어의 길이가 3일때, 만약에 3번째 명령까지 반영해서 방향을 바꿔주었으면 마지막 방향대로 계속 진행을 해야하기 때문에 flag를 통해 예외 처리를 해주었다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
board = [[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    x,y = map(int,input().split())
    board[x][y] = 1

command_cnt = int(input())

# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
board[1][1] = 2
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
next_time,next_direction = commands[0]
break_flag = True
while True:


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if board[next_x][next_y] != 2:
            if board[next_x][next_y] == 1:
                snakes.appendleft((next_x,next_y))
                board[next_x][next_y] = 2
            else:
                board[next_x][next_y] = 2
                tail_x,tail_y = snakes.pop()
                board[tail_x][tail_y] = 0
                snakes.appendleft((next_x,next_y))
            break_flag = False
    if break_flag:
        break
    break_flag = True



    if snake_times == next_time:
        snake_direction = (snake_direction + next_direction)%4
        if ind < command_cnt-1:
            ind += 1
            next_time,next_direction = commands[ind]

print(snake_times)

위의 내가 했던 부분과 거의 동일하다. 대신 board라는 2차원 리스트에 뱀의 위치와 사과의 위치를 표시해주었다 이렇게 하면, 첫번째 코드에서 썼던 not in snakes와 같은 logN이 걸리는 시간이 좀 더 줄어드는 장점이 있다.