모의고사2

문제1
- 구현

def solution(command):
    x_y=[0,0]
    angle=0
    x_factor=[0,1,0,-1]
    y_factor=[1,0,-1,0]

    for order in command:
        if order=="R":
            angle+=90
            angle%=360
        elif order=="L":
            angle-=90
            angle%=360
        else:
            factor_index=(angle//90)
            if order=="G":
                x_y[0]+=x_factor[factor_index]
                x_y[1]+=y_factor[factor_index]
            if order=="B":
                x_y[0]+=-x_factor[factor_index]
                x_y[1]+=-y_factor[factor_index]
    return x_y

문제2
- 정렬(힙)

from heapq import heapify,heappop,heappush
def solution(ability, number):
    #항상 제일 작은 사원 두명을 교육시켜야한다.
    heapify(ability)

    for i in range(number):
        next_ability=heappop(ability)+heappop(ability)
        heappush(ability,next_ability)
        heappush(ability,next_ability)

    return sum(ability)

문제3
- 구현(동기적 작업순서)

from collections import deque
def solution(menu, order, k):
    guest_list=deque()
    order=deque(order)
    current_time=0
    max_guest=0
    #끝나는 시간을 인지해야 현재 몇명이 있는지를 파악
    while len(order)>0 or len(guest_list)>0:
        #현재시간 이전에 끝난 주문들은 모두 제거
        while len(guest_list)>0 and guest_list[0]<=current_time:
            guest_list.popleft()
        #주문자가 남아있다면
        if len(order)>0:
            #새로운 주문의 걸리는 시간
            new_order_time=menu[order.popleft()]
            #아직 만들어야하는 주문자가 남으면 마지막 주문자 기준으로 새로운 주문의 끝나는 시간을 저장
            if len(guest_list)>0:
                guest_list.append(guest_list[-1]+new_order_time)
            else:
            #만들어야하는 주문자가 없다면 지금시간 기준으로 새로운 주문의 끝나는 시간을 저장
                guest_list.append(current_time+new_order_time)
        # print("order_list:",guest_list)
        # print("current_time:",current_time)
        max_guest=max(max_guest,len(guest_list))
        current_time+=k

    return max_guest

문제4
- BFS

from collections import deque
def solution(n, m, hole):
    maps=[[1 for _ in range(n)] for _ in range(m)]

    #장애물은 0,일반 길은 1으로 변환
    for x,y in hole:
        maps[y-1][x-1]=0
    #visited[1][2][0]->좌표 1,2에서 신발을 신지 않았을 떄의 방문기록
    #visited[1][2][1]->좌표 1,2에서 신발을 신었을 때의 방문 기록
    visited=[[[False,False] for _ in range(n)] for _ in range(m)]
    x_offset=[-1,1,0,0]
    y_offset=[0,0,-1,1]
    #(x좌표,y좌표,신발사용여부,지나온 거리)
    to_do_list=deque([(0,0,0,0)])
    length=0
    while len(to_do_list)>0:
        x,y,shoes_used,dis=to_do_list.popleft()
        indexes=[(x+x_offset[i],y+y_offset[i]) for i in range(4)]
        for nx,ny in indexes:
            #신발을 사용한 애들은 신발을 사용한 맵의 방문 기록에서,사용안한 애들은 사용안한 맵의 방문 기록에서 확인
            if (0<=nx and nx<m) and (0<=ny and ny<n) and visited[nx][ny][shoes_used]==False and maps[nx][ny]!=0:
                if nx==m-1 and ny==n-1:
                        return dis+1
                visited[nx][ny][shoes_used]=True
                to_do_list.append((nx,ny,shoes_used,dis+1))
            if shoes_used==0:
                jump_nx=nx+(nx-x)
                jump_ny=ny+(ny-y)
                if (0<=jump_nx and jump_nx<m) and (0<=jump_ny and jump_ny<n) and maps[jump_nx][jump_ny]!=0 and visited[jump_nx][jump_ny][1]==False:
                    if jump_nx==m-1 and jump_ny==n-1:
                        return dis+1
                    visited[jump_nx][jump_ny][1]=True
                    to_do_list.append((jump_nx,jump_ny,1,dis+1))
    return -1