Coding 공부

백준 골드1을 달성했다.

매일 1문제 이상씩 알고문제를 풀고 있는데 아직 블로그에 올리지 못한 문제들이 많다..

빨리 올려야겠다.

import sys


input = sys.stdin.readline
def roll(A,B):
    if A[0] >= B[0] and A[1] < B[1]:
        dx = A[0]-B[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]+dx)
    elif A[0] >= B[0] and A[1] >= B[1]:
        dx = A[0] - B[0]
        dy = A[1] - B[1]
        return (B[0]-dy,B[1]+dx)
    elif A[0] < B[0] and A[1] < B[1]:
        dx = B[0]-A[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]-dx)
    else:
        dx = B[0]-A[0]
        dy = A[1]-B[1]
        return (B[0]-dy,B[1]-dx)



def dragon(cur_gener,total_gener):
    global dragon_list
    if cur_gener == total_gener:
        return

    tail_position = dragon_list[-1]
    dragon_length = len(dragon_list)
    for ind in range(dragon_length-2,-1,-1):
        dragon_list.append(roll(dragon_list[ind],tail_position))
    dragon(cur_gener+1,total_gener)




N = int(input())
# x,y 시작점 d는 시작 방향 g는 세대 

dx = [1,0,-1,0]
dy = [0,-1,0,1]
arr = [[0]*101 for i in range(101)]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    dragon_list = [(x,y),(x+dx[dire],y+dy[dire])]
    if gener:
        dragon(0,gener)
    for position in dragon_list:
        arr[position[1]][position[0]] = 1

result = 0



for y in range(100):
    for x in range(100):
        if arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x][y+1] == 4:
            result += 1

print(result)

이 드래곤 커브는 끝에 있는 점을 기준으로 현재까지 온 경로들을 전부 시계 방향으로 90도 회전을 해주는 것을 계속 반복한다.

처음 풀었던 방식은 어렵게 생각해서 푼 문제이다.

드래곤 커브의 각 점들의 위치를 한 리스트에 넣어준다. 그러면 끝점을 찾아주고, 그 끝점을 기준으로 끝점을 제외한 나머지 점들의 위치를 파악해서, 옮겨주는 작업을 해주었다. 

좌표계로 그려보면 알겠지만, 끝점을 원점으로 생각해서, 그 점을 기준으로 1,2,3,4 사분면에 있을때 회전하는 위치를 계산해주었다.

1사분면에 있으면 1사분면의 y축 값은 x축값이 되고, x축의 값은 +y축값이 된다. 

2사분면에 있으면 2사분면의 x축값은 +y축값이 되고, y축값은 -x축 값이 된다.

이런식으로 구분을 해서, 각 끝점을 기준으로 움직인 위치를 찾아서 드래곤 커브 리스트에 넣어준다.

여기서 주의 해야할 점은 두가지인데, 문제에 주어진 xy좌표축은 수직방향으로 위로 올라갈수록 y축 값이 줄어드는 것이다.

그리고 두번째는 끝점을 기준으로 뒤에서부터 판별을해야 한다는 것이다.

이렇게 모든 세대를 돌리고 난뒤에 101*101 행렬에 점을 찍어주면 된다. 그리고 마지막으로 네 귀퉁이에 전부 1인 경우에를 세어서 결과로 출력하면 된다.

import sys

input = sys.stdin.readline

N = int(input())

arr = [[0]*101 for _ in range(101)]
dx = [1,0,-1,0]
dy = [0,-1,0,1]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    # dire 0 ->1
    # 1->2
    # 2->3
    # 3->0
    move_list = [dire]
    arr[y][x] = 1
    for _ in range(gener):
        temp = []
        for i in range(len(move_list)-1,-1,-1):
            temp.append((move_list[i]+1)%4)
        move_list.extend(temp)
    for i in move_list:
        nx = x + dx[i]
        ny = y + dy[i]
        arr[ny][nx] = 1
        x,y  = nx,ny
result = 0
for y in range(100):
    for x in range(100):
        if arr[y][x] + arr[y+1][x] + arr[y][x+1] + arr[y+1][x+1] == 4:
            result += 1
print(result)

좀 더 쉬운 풀이는 다음과 같다.

진행방향만 넣어주는 것이다.

90도 시계방향을 회전하면 다음 진행반향은 현재 진행방향의 +1 의 modulo 4 연산을 해주면 된다.

이렇게 move_list에 넣어주고, 위에서처럼 끝점부터 해서 넣어주면 된다.

그리고 모든 세대를 지난뒤에, 처음시작점에서 진행방향에 맞춰서 점을 찍어주면 된다.

import sys

input = sys.stdin.readline

N = int(input())

arr =[ list(map(int,input().split())) for _ in range(N)]

max_arr = [[0]*3 for _ in range(2)]
min_arr = [[0]*3 for _ in range(2)]

max_arr[0][0] = min_arr[0][0] = arr[0][0]
max_arr[0][1] = min_arr[0][1] = arr[0][1]
max_arr[0][2] = min_arr[0][2] = arr[0][2]

for i in range(1,N):
    max_arr[1][0] = arr[i][0] + max(max_arr[0][0],max_arr[0][1])
    max_arr[1][1] = arr[i][1] + max(max_arr[0][0],max_arr[0][1],max_arr[0][2])
    max_arr[1][2] = arr[i][2] + max(max_arr[0][1],max_arr[0][2])
    min_arr[1][0] = arr[i][0] + min(min_arr[0][0],min_arr[0][1])
    min_arr[1][1] = arr[i][1] + min(min_arr[0][0],min_arr[0][1],min_arr[0][2])
    min_arr[1][2] = arr[i][2] + min(min_arr[0][1],min_arr[0][2])

    for y in range(3):
        max_arr[0][y] = max_arr[1][y]
        min_arr[0][y] = min_arr[1][y]

print(max(max_arr[0]),min(min_arr[0]))

처음 풀어본 슬라이딩 윈도우 관련 문제이다. 들어오는 N의 최대값이 10만이므로, 그대로 전체에 대해서 행렬을 만들경우, 메모리 초과가 날 수 있다.

그럴때 사용하는 알고리즘인 것 같다.

슬라이딩 윈도우에 관련된 설명은 blog.fakecoding.com/archives/algorithm-slidingwindow/ 에서 공부했다.

이 문제도 슬라이딩 윈도우를 통해, 최대값과 최소값을 갱신해주면 되는 문제이다.

일단 한 행에는 3개의 인수가 나와있고, 그 행에서 최대값을 얻을 수 있는 경우는

첫번째 열은 첫번째 열과 값과 그전 행의 첫번째 열과 두번째 열 중 더 큰 값을 더하는 경우이고,

두번째 열은 두번째 열의 값과 그전 행의 첫번째, 두번째, 세번째 열 중  가장 큰 값과 더해주는 것이다.

세번째 열은 세번째 열의 값과 그전 행의 두번쨰,세번째 열 중 가장 큰 값과 더해주는 것이다.

구해진 값들은 현재 행의 각 열에서의 최대값을 구한것이다. 그러면 이 다음행은 이 전전 행 현재행의 그전 행의 값의 유무는 상관이 없다. 현재행의 값들만 알고 있으면 위의 로직을 다음행에서 진행할때에는 전전행은 필요가 없으므로, 현재행에서 구한 값들의 위치를 이전행으로 옮겨주는 과정을 하면 된다.

최소값은 max에서 min으로 바꿔주기만 하면 된다.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [{} for i in range(N)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if a != b:
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c

INF = float('inf')
distance = [INF]*N
visited = [False] *N
distance[0] = 0
node_list = []
heapq.heappush(node_list,(0,0))
result = 0
while node_list:
    dis, node = heapq.heappop(node_list)
    if visited[node]:
        continue
    result += dis
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))

print(result)

최소 스패닝 트리 문제이다. 프림알고리즘과 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘에 아직 익숙하지 않아, 프림 알고리즘으로 구현했다.

heapq를 이용해서 구현했기 때문에, distance가 갱신될때에만 heapq.heappush를 해주는 것만 주의해주면 풀 수 있는 문제이다.

import heapq
import sys
input = sys.stdin.readline
N,M = map(int,input().split())

arr = [list(map(int,list(input().strip()))) for _ in range(M)]

node_list = []
heapq.heappush(node_list,(0,0,0))
INF = float('inf')
dp = [[INF]*N for _ in range(M)]
dx = [-1,1,0,0]
dy = [0,0,1,-1]
dp[0][0] = 0
while node_list:
    dis,x,y = heapq.heappop(node_list)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<M and 0<=ny<N:
            if dp[nx][ny] > dp[x][y] + arr[nx][ny]:
                dp[nx][ny] = dp[x][y] + arr[nx][ny]
                heapq.heappush(node_list,(dp[nx][ny],nx,ny))

print(dp[M-1][N-1])

BFS를 이용해서 푸는 방법도 있을것 같은데, 다익스트라로 풀었다. 기본적으로 하는 BFS와 동일하다. 대신 2차원으로 바뀌었기 때문에, 4방향을 탐색하면, 현재 dp값이 줄어드는 경우에만 heapq에 push를 해주고, 여기서는 거리대신 해당 arr에 있는 벽의 유무로 판별해주었다.

import sys

input = sys.stdin.readline
n = int(input())
INF = float('inf')
graph = [[INF if i !=j else 0 for j in range(n)] for i in range(n)]
m = int(input())

for _ in range(m):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = min(graph[A-1][B-1],C)
for k in range(n):
    for start in range(n):
        for end in range(n):
            if graph[start][end] > graph[start][k] + graph[k][end]:
                graph[start][end] = graph[start][k] + graph[k][end]



for row in graph:
    print(*[j if j != INF else 0 for j in row])

플로이드 와샬을 이용한 문제였다.

2차원 배열을 자기자신을 가는 경우를 제외한 나머지 경우를 INF로 초기화 시켜주고, 들어오는 input에서도 같은 경로를 여러번 들어오는 경우가 있으므로, 최소값으로 넣어주었다.

그리고 플로이드 와샬을 3중 for문으로 구현해줬다.

출력은 if else문을 이용해 INF가 그대로인 곳은 갈수 없는 곳이므로 0으로 출력해주었다.

from itertools import permutations
from collections import deque
def outOfrange(x,y):
    if 0 > x or x >3 or y<0 or y>3:
        return True
    return False

def dfs(start,end,copy_board):
    dp = [[-1]*4 for _ in range(4)]
    dp[start[0]][start[1]] = 0
    stack = deque()
    stack.append((start[0],start[1]))
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            repeat = 0
            while True:
                nx = x + dx[i]*repeat
                ny = y + dy[i]*repeat
                if outOfrange(nx+dx[i],ny+dy[i]) or (repeat!=0 and copy_board[nx][ny]):
                    break
                repeat += 1
            for re in (1,repeat):
                nx = x + dx[i] * re
                ny = y + dy[i] * re
                if outOfrange(nx,ny):
                    continue
                if dp[nx][ny] == -1:
                    dp[nx][ny] = dp[x][y] + 1
                    stack.append((nx,ny))
                    if dp[end[0]][end[1]] != -1:
                        return dp[end[0]][end[1]]
    return dp[end[0]][end[1]]



def find_command(x,y,find_card,copy_board):
    dis1 = dfs((x,y),find_card[0],copy_board)
    dis2 = dfs(find_card[0],find_card[1],copy_board)
    return dis1+dis2




def solution(board, r, c):
    answer = float('inf')
    card_list = [[] for _ in range(7)]
    card_numbers = set()
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_list[board[x][y]].append((x,y))
                card_numbers.add(board[x][y])

    card_cnt = len(card_numbers)
    for combi in permutations(card_numbers):
        predict_dict = {}
        for k in range(1<<card_cnt):
            distance = 0
            mouse_cursor_x = r
            mouse_cursor_y = c
            copy_board = [row[:] for row in board]
            temp = ''
            for ind,num in enumerate(combi):
                start = int(bool((k&1<<(ind))))
                end = (start+1)%2
                temp += str(start)
                find_card = [card_list[num][start],card_list[num][end]]
                if not predict_dict.get(temp):
                    distance += find_command(mouse_cursor_x,mouse_cursor_y,find_card,copy_board)
                    predict_dict[temp] = distance
                else:
                    distance = predict_dict[temp]
                mouse_cursor_x = card_list[num][end][0]
                mouse_cursor_y = card_list[num][end][1]
                copy_board[card_list[num][start][0]][card_list[num][start][1]] = 0
                copy_board[card_list[num][end][0]][card_list[num][end][1]] = 0
                if distance > answer:
                    break
            if answer > distance:
                answer = distance
    return answer+2*card_cnt


a = solution([[1,0,2,0],[6,2,4,0],[0,0,1,0],[6,0,0,4]],1,0)
print(a)

문제 자체는 BFS+순열+조합으로 간단해보였지만, 구현하는데 난이도가 컸던 문제였다.

기본 풀이 자체는 다음과 같다.

카드번호 1,2,3이 있다고 하면

1,2,3을 순열로 먼저 없앨 카드별 순서를 정해준다.

그리고 각 카드는 2장씩 있으므로, A,B 가 있다고 치면

1A->1B

1B->1A는 다를 것이다.

이 모든 경우를 돌려서 결과를 얻는 것이다.

그래서 먼저 나는 card_numbers에 이 보드에 있는 카드번호들을 저장해두고 permutations 모듈을 사용해서 순열을 만들었다 그리고 난뒤, 카드의 앞뒷면을 정해주기 위해 조합을 만들었다.

만약 우리가 카드가 3장이 있다고 하면 이 카드의 앞뒷면을 만들수 있는 가짓수는

000

001

010

011

100

101

110

111

이런식으로 총 8가지가 있을수 있다. 위의 가지수를 각비트로 봐보면 0~7까지인걸 알수 있다. 그러므로 저는 카드의 개수가 N이라고 하면, 2**N 만큼 range를 돌리고, 각 permutations으로 나오는 각각의 카드 index와 비트연산을 해서, 해당 카드의 앞뒷면의 순서를 결정해주었다.

이렇게 한뒤 현재 커서위치 -> 먼저 찾을 카드위치 -> 나중 찾을 카드위치 순으로, bfs를 돌렸다.

bfs를 돌릴때, ctrl 이동과 일반적인 한칸이동을 동시에 시행했다. 범위 밖을 나가던지, 아니면 카드가 있는 위치이던지, 그 위치까지의 길이를 기억해놓은뒤, 그 만큼을 dp라는 visited를 담당하는 행렬에 저장을해주었다. 그리고 우리가 찾는 목적지에 도착하면, return 해주는 방식으로 했다.

이렇게 bfs를 전부 돌린뒤에는 copy한 board에서 우리가 현재 뒤집은 카드들의 정보를 0으로 바꿔주고, 마우스 커서위치는 마지막 카드위치로 바꿔주는 작업을 해준다.

위 풀이 방식은 아슬아슬하게 시간을 통과한지라 여러부분에서 시간을 줄여주었다. 위에서 했듯이 bfs에서 매번 도착지점을 판별해주는 것이 첫번째 방법이었고, distance가 저장된 answer 보다 커지면 탐색을 중단해주는것도 그 방안이었다.

이렇게 구한 answer에 현재 카드의 종류의 2배만큼 더해서 출력해주면된다.

from collections import deque
import functools
def solution(board,r,c):
    card_dict = [[] for i in range(7)]
    card_tuple = set() 
    for x in range(4):
        for y in range(4):
            if board[x][y]:
                card_dict[board[x][y]].append((x,y))
                card_tuple.add(board[x][y])
    card_tuple = tuple(card_tuple)

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    def outOfrange(x,y):
        if 0 > x or x >3 or y<0 or y>3:
            return True
        return False

    @functools.lru_cache(maxsize=None)
    def bfs(s,t,cards):
        if s == t:
            return 0
        stack = deque()
        stack.append((s[0],s[1],0))
        visited = set()
        while stack:
            x,y,cnt = stack.popleft()
            for i in range(4):
                repeat = 0
                while True:
                    nx = x + dx[i]*repeat
                    ny = y + dy[i]*repeat
                    if outOfrange(nx+dx[i],ny+dy[i]) or (repeat != 0 and board[nx][ny] in cards):
                        break
                    repeat += 1
                for re in [1,repeat]:
                    nx = x + dx[i]*re
                    ny = y + dy[i]*re
                    if outOfrange(nx,ny):
                        continue
                    if (nx,ny) == t:
                        return cnt + 1
                    if (nx,ny) not in visited:
                        visited.add((nx,ny))
                        stack.append((nx,ny,cnt+1))

    @functools.lru_cache(maxsize=None)
    def find_card_short_count(cur_position,cards):
        if len(cards) == 0:
            return 0
        min_distance = float('inf')
        for pick_card in cards:
            position1,position2 = card_dict[pick_card]
            remain_cards = tuple(card for card in cards if card != pick_card)
            direction1 = bfs(cur_position,position1,cards) + bfs(position1,position2,cards) + find_card_short_count(position2,remain_cards)
            direction2 = bfs(cur_position,position2,cards) + bfs(position2,position1,cards) + find_card_short_count(position1,remain_cards)
            min_distance = min(min_distance,direction1,direction2)
        return min_distance

    answer = len(card_tuple)*2 + find_card_short_count((r,c),card_tuple)
    return answer


a = solution([[1, 0, 0, 3], [2, 0, 0, 0], [0, 0, 0, 2], [3, 0, 1, 0]], 1, 0)
print(a)

위의 풀이 대신 이 풀이는 프로그래머스의 다른사람풀이를 보고 공부하면서 쓴 풀이다.

자세한 설명은 http://www.teferi.net/ps/problems/programmers/72415 이 링크를 참조하길 바란다.

기본적인 풀이는 비슷하다. 대신 이 풀이는 위에서 복잡하게 비트연산을 통해 결정하는 것이 아닌, 재귀함수를 통해, 순열과 조합을 구현했고, functools.lru_cache를 통해 메모라이즈를 해주었다.

이 두 방식을 통해 시간이 획기적으로 줄어들었다.

이 풀이는 크게 2가지의 함수로 나뉠수 있다. find_card_short_count라는 함수와 bfs 함수이다.

bfs는 A->B까지 가는 최소 명령어를 찾아주는 것이다. 여기서 카드의 위치를 판단하는것은 cards라는 tuple을 통해, 있는지 판별을 해준다.

여기서 중요한것은 find_card_short_count라는 함수이다. 이 함수의 역할은 재귀를 통해 순열을 만드는 것이다.

cur_position은 현재 커서의 위치이고, cards는 현재 남아있는 카드들의 번호들이다.

이 cards를 반복문을 돌리면서 그 카드를 제거할 카드라 생각하고, cards에서 현재 선택한 card를 제외한 나머지 카드들을 remain_cards로 남겨준다.

위에서 설명했던 것처럼 한 카드에서도 먼저 제거할 카드를 선택을 해야한다. 그 방법으로 direction1과 direction2로 나뉘어서 해주었다.

한 카드에서 position1 과 position2가 있다고 하면 제거할 수 있는 방법은 두가지이다.

현재 커서위치 -> position1까지의 거리를 구해주고 position1 -> position2 까지의 거리를 구해준다.
그러면 마지막 커서의 위치는 position2가 되고 position2와 remain_cards를 가지고 find_card_short_count를 해주면 된다.

이런 방식으로 현재 커서 위치 -> position2 -> position1도 똑같이 해준다.

direction1 = bfs(cur\_position,position1,cards) + bfs(position1,position2,cards) + find\_card\_short\_count(position2,remain\_cards)

direction2 = bfs(cur\_position,position2,cards) + bfs(position2,position1,cards) + find\_card\_short\_count(position1,remain\_cards)

이 식들이 위에서 설명해준것을 구현한 것이다.

여기서 중요한 역할을 하는 것은 functools.lru_cache 라는 데코레이터이다.

이 데코레이터의 역할은 함수의 호출을 기억해주는 것이다. 똑같은 입력값이 들어온 함수들을 기억해서, 다음번에 호출이 되는 경우 함수를 한번더 실행하는 것이 아닌, 기억한 결과값을 그대로 주는 것이다.

그렇기 때문에 이 데코레이터를 썼을 때, 메모라이즈를 해준것이기 때문에, 재귀함수를 쓰면서도 시간을 줄일 수 있다.

다음과 같이 시간을 100ms 이하로 줄일 수 있다.

functools.lru_cache를 쓰지 않으면 시간의 압박이 크다.

위의 풀이가 아닌 DP를 활용한 풀이를 보고 싶은 분들은 https://www.youtube.com/watch?v=FX9n1PFv2K4 해당 유튜브를 참조하길 바랍니다.

from itertools import combinations

def solution(info, query):
    answer = []
    languages = ['cpp','java','python','-']
    positions = ['backend','frontend','-']
    careers = ['junior','senior','-']
    soulfoods = ['chicken','pizza','-']
    total_dict = {language : {position : {career : {soulfood : [0]*100001 for soulfood in soulfoods} for career in careers}  for position in positions} for language in languages}
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        info_list = [language,position,career,soulfood]
        for i in range(1<<4):
            temp = []
            for j in range(4):
                if i&(1<<j):
                    temp.append(info_list[j])
                else:
                    temp.append('-')
            total_dict[temp[0]][temp[1]][temp[2]][temp[3]][score] += 1
    for language in total_dict.keys():
        for position in total_dict[language].keys():
            for career in total_dict[language][position].keys():
                for soulfood in total_dict[language][position][career].keys():
                    for score in range(1,100001):
                        total_dict[language][position][career][soulfood][score] += total_dict[language][position][career][soulfood][score-1]
    for query_string in query:
        language,position,career,last_query = map(str.strip,query_string.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        answer.append(total_dict[language][position][career][soulfood][100000] - total_dict[language][position][career][soulfood][score-1])
    return answer

처음 풀었던 방식이다. dictionary를 이용해서, 각 쿼리에 맞게 저장을 하는 방식이다. 각 쿼리를 저장할때 나올수 있는 겨우의 수는 16가지이다. 그걸 만들기 위해서 조합을 만드는 방식으로 중간에 비트마스크를 활용해서 각조합을 만들고, 저장을 해주었다.

그리고 각 score에 대해서 그 이상값을 추출하면 시간이 오래걸리므로, prefix_sum을 통해 저장을 해놓은 뒤, query가 들어왔을때, 최대값이 10만에서 찾고자 하는 값-1을 빼줘서 찾아줬다.

해당 코드의 효율성 통과 시간이다.

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[0]*100001 for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind][score] += 1
    for ind in range(108):
        for score in range(1,100001):
            store_query[ind][score] += store_query[ind][score-1]

    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        answer.append(store_query[ind][100000] - store_query[ind][score-1])
    

    return answer

두번째 코드는 www.youtube.com/watch?v=FX9n1PFv2K4 의 코드에서 차용해와서 푼 방식이다.

dicationry로 키를 만드니 너무 난잡해 보여서 2차원 배열로 만든 방식이다.

이 방식으로 했을때 시간이 좀 더 빨랐다.

import bisect

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[] for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind].append(score)
    for ind in range(108):
        store_query[ind].sort()
    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        cnt = len(store_query[ind]) - bisect.bisect_left(store_query[ind],score)
        answer.append(cnt)
    

    return answer

마지막은 구간합으로 하면  16*100000번의 계산이 필요하므로 실행시간이 오래걸린다. 그래서 해결한 방법중 하나가 bisect라는 라이브러리를 활용한것이다.

bisect에 있는 기능 중 bisect_left는 정렬된 리스트에서, 순서대로 정렬되는 것을 유지하고, 현재값이 들어갈수 있는 위치의 왼쪽좌표를 알려준다. 즉, 자기보다 작은 값의 위치를 알려주는 것이다. 이걸 이용해서 그 리스트의 길이에서 해당 index의 위치를 빼주면 이상을 구할 수 있게된다.

이걸로 했을때가 시간이 제일 빨랐다. bisect를 이용하지 않고, 이분탐색을 직접구현해도 된다.

해당 문제는 query로 나올수 있는 경우의 수를 모두 예상하고 저장해놓는게 힘들었다.