Coding 공부

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    skill_board = [[0 for i in range(M+2)] for _ in range(N+2)]
    cnt = 0
    for sk in skill:
        sk_type, r1,c1,r2,c2 ,degree = sk
        if sk_type == 1:
            degree = -degree
        r1 +=1; r2+=1; c1+=1; c2+=1
        skill_board[r1][c1] += degree
        skill_board[r1][c2+1] -= degree
        skill_board[r2+1][c1] -= degree
        skill_board[r2+1][c2+1] += degree
    for x in range(1,N+1):
        for y in range(1,M+1):
            skill_board[x][y] = skill_board[x][y] + skill_board[x-1][y] + skill_board[x][y-1] - skill_board[x-1][y-1]
    for x in range(N):
        for y in range(M):
            if board[x][y] +skill_board[x+1][y+1] >0:
                answer += 1
    return answer

이 문제도 실전에서 풀지 못했던 문제였다.

7번 문제에 너무 힘을 쏟은 나머지, 마지막 20분동안 풀다가 범위 측정을 제대로 못해서, 풀지 못한 문제였다.

평소 2차원 누적합을 잘 다루지 않다보니, 범위를 구하는데 실수를 했고, 그 범위의 누적합을 구하는데 연산을 실후 했다.

이 문제에서 중요한 것은 폭발 범위에 맞춰서 누적합을 할 수 있게, 숫자들을 정리해 놓고, 누적합을 구하면 되는 문제이다.

폭발이 시작하는 r1,c1에는 +degree을 해주고,

폭발이 끝나는 위치인 r2+1,c1 , r1,c2+1에는 -degree을 해준다.

그리고 중요한 것은 r2+1, c2+1 에서는 +degree를 해주는 것이다.

이 누적합을 마킹해놓은 상태에서 가로로 1번 누적합 세로로 1번 누적합을 진행을 한다고 생각을 해보면, 왜 그 위치에서 마킹을 해줘야하는지 이해할 수 있다.

이 문제는 누적합이라는 접근까지 했지만, 디버깅 할 시간이 부족해 풀지 못했던 아쉬웠던 문제였다..

2차원 누적합은 매번 풀때마다, 햇갈려하는 유형이기 때문에 좀 더 연습해야겠다.

dx = [-1,0,1,0]
dy = [0,1,0,-1]
N,M =0,0
def B_turn(curboard,A,B,turn):
    x,y = B 
    if curboard[x][y] == 0:
        return (-1,turn)
    flag = False
    winner = []
    loser = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if curboard[nx][ny] == 1:
                new_board = [row[:] for row in curboard]
                new_board[x][y] = 0
                iswin,new_turn = A_turn(new_board,A,(nx,ny),turn+1)
                if iswin == -1:
                    winner.append(new_turn)
                else:
                    loser.append(new_turn)
                flag = True
    if flag:
        if winner:
            return (1,min(winner))
        else:
            return (-1,max(loser))
    else:
        return (-1,turn)
def A_turn(curboard,A,B,turn):
    x,y = A 
    if curboard[x][y] == 0:
        return (-1,turn)
    flag = False
    winner = []
    loser = []
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<M:
            if curboard[nx][ny] == 1:
                new_board = [row[:] for row in curboard]
                new_board[x][y] = 0
                iswin,new_turn = B_turn(new_board,(nx,ny),B,turn+1)
                if iswin == -1:
                    winner.append(new_turn)
                else:
                    loser.append(new_turn)
                flag = True
    if flag:
        if winner:
            return (1,min(winner))
        else:
            return (-1,max(loser))
    else:
        return (-1,turn)

def solution(board, aloc, bloc):
    global N,M
    N = len(board)
    M = len(board[0])


    return A_turn(board,aloc,bloc,0)[1]

 작년 카카오 마지막 문제로, 풀지 못했던 문제였다.

비슷하게 접근을 했지만, 원하는 정답을 구하지 못했고,

문제가 나오자마자 풀었다.

비슷한 느낌의 문제는 https://www.acmicpc.net/problem/16571

위의 문제이고,

이 문제에서도, 완전탐색을 통해, 자신이 지는지, 이기는지를 판별을 하고,

자신이 이길 가능성이 있으면, 이길때의 최소 턴을 return 해주고,

전부 질때에는 최대 turn을 반환을 해주면 되는 것이다.

이 문제에서 지는 조건은 총 2가지로,

4방향으로 움직이고자할때, 움직이지 못하면, 지는 것이고,

두번째는 움직이고자할때, 내가 밟고 있는 발판이 사라진 상태이면 지는 것이다.

이 문제를 풀때,

예를 들어 현재 사용자(A)가 진다고 생각했을때 나는 -1과 turn을 반환을 해주었다.

그러면 상대방(B) 입장에서는 이 값을 return 되었을때 -1이 오게 되면, 자신이 이기게 되는 것이다.

그러므로, winner라는 리스트에 턴 값을 저장을 해주었다.

결국에는 두 사용자는 하나는 패배하게 될것이고, 한 사용자는 이기게 될것이다.

그래서 이기게 된 사용자는 1을 반환을 하게 만들었고,

이 값을 받은 입장에서는 자신의 패배가 되는 것이다.

그러면 X라는 턴에서 한 사용자가 모든 경우를 다 탐색하게 되면, 1 또는 -1을 받게 되어, 자신이 이기게 될지, 지게 될지를 알게 될것이다.

문제에서 우리는 두 사용자는 이기게 되도록 수를 둔다고 했으니, 받는 값 중에서 이기게 되는 경우가 단 1번이라도 있게 되면,

1 과 이길수 있는 경우 중에 최소 턴을 반환한다.

그러나 모든 경우에도 자신이 지게 되는게 확정적이라 생각되면, 최대 turn을 반환해주면 된다.

그래서 -1과 지는 경우 중에서 최대 턴을 반환해주도록 하도록 함수를 짜주면 된다.

이렇게 함수를 짜놓고, 재귀를 돌리게 되면, 문제를 해결 할 수 있는 문제였다.

실전에서 문제를 푸는데 틀린 이유 중 하나는, 현재 위치에서 지는 경우에 대해서 탐색을 하고, return을 해줘야하는데, 

최선의 수를 두지 않는, 미래의 수를 계산을 해서 return을 해줘서 틀렸던 문제였다.

실전에서 이 문제에 시간을 오래 소비해서 결국 6번도 풀지 못한거 보면, 문제를 해결할 때, 시간 분배를 잘해야겠다.

import sys

sys.setrecursionlimit(20000)

def solution(k, num, links):
    left = sum(num)//k
    right = sum(num)
    N = len(num)
    degrees = [0 for _ in range(N)]
    for ind in range(N):
        if links[ind][0] != -1:
            degrees[links[ind][0]] += 1
        if links[ind][1] != -1:
            degrees[links[ind][1]] += 1
    root = -1
    for ind in range(N):
        if not degrees[ind]:
            root = ind
            break
    INF = float('inf')
    def check(node):
        nonlocal links,INF,dp,mid
        if links[node][0] == -1 and links[node][1] == -1:
            if num[node]<=mid:
                dp[node][0] = num[node]
                dp[node][1] = 1
            else:
                dp[node][0] = 0
                dp[node][1] = INF
        else:
            for ind in range(2):
                if links[node][ind] != -1:
                    check(links[node][ind])
            left_node = links[node][0]
            right_node = links[node][1] 
            if dp[left_node][0] + dp[right_node][0] + num[node] <= mid:
                dp[node][0] = dp[left_node][0] + dp[right_node][0] + num[node]
                dp[node][1] = dp[left_node][1] + dp[right_node][1] -1
                return
            if right_node == -1:
                if num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            else:
                if num[node] + min(dp[right_node][0],dp[left_node][0])<= mid:
                    dp[node][0] = num[node] + min(dp[right_node][0],dp[left_node][0])
                    dp[node][1] = dp[right_node][1] + dp[left_node][1]
                elif num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + dp[right_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF

            



    while left+1<right:
        mid = (left+right)//2
        dp = [[0,1] for _ in range(N+1)]
        check(root)
        if dp[root][1]<=k:
            right = mid
        else:
            left = mid
    return right

풀기 힘들었던 문제이다.

이 문제는 트리 DP와 파라메트릭 서치를 활용한 문제로

k개의 그룹으로 나눌 수 있는 최소 값을 찾는것이다.

카카오 해설에서도 알수 있듯이 이분탐색으로 찾으면 되고,

이 이분 탐색의 중간값인 mid가 의미하는 것은 이 트리를 나눌 최대의 인원을 의미한다.

한 그룹의 인원이 mid가 넘어가지 않게 해주면 된다.

즉 mid의 값이 크면 k는 적게 나올것이고, mid의 값이 작으면 k보다 많게 나올 것이다.

우리는 left+1<right일때 끝나고

left일때 false이므로,

우리가 구하고자 하는 값은 right임을 알 수 있다.

문제에 들어가면,

가장 밑 노드에서부터 해주면 된다.

먼저 dp 테이블은 N*2의 크기로 해주었고,

dp[x][0] 은 x 노드에서의 최소 그룹인원의 수

dp[x][1] 은 x 노드에서의 그룹의 개수를 의미한다.

각 노드는 처음에 하나의 그룹이므로, dp[x][0]은 0으로 dp[x][1]은 1로 초기화를 해주었다.

총 4가지 경우가 있을것이다.

1. 자식노드 2개에 누적된 그룹인원과 현재노드의 인원과  더해도 mid보다 작거나 같다.

    그러면 dp[parent][0] = num[parent] + dp[left_node][0] + dp[right_node][1]이 될것이다.

    그리고 그룹의 수는 자식노드의 그룹의 수를 더해준 것에서 -1을 해준다.

    이러는 이유는 우리가 각 노드를 하나의 그룹으로 생각했기 때문에, 처음에 1로 전부 초기화 되어 있어서 그런다.

   자식노드와 현재그룹을 더해서 한개의 그룹이 된 것이므로 - 1을 해준다.

2. 자식노드 둘 중 1개 그룹인원과  현재 노드의 인원과 더하면 mid보다 작거나 같다.

   이럴때에는 그룹인원이 많은쪽의 간선을 끊는것과 마찬가지 이므로

   dp[parent][0] = num[parent] + min(dp[left_node][0], dp[right_node][1])

  을 해주고, 그룹은 두 자식노드의 그룹인원을 더해주면 된다.

3. 현재 그룹인원의 mid보다 작거나 같고, 자식노드들의 인원을 더하면 mid보다 크다.

   이럴 경우는 간선을 전부 끝는 것이다.

   그래서 dp[parent][0] = num[parent]를 해주고,

   그룹의 수는 1개를 더 더해주면 된다.

4. 현재 그룹의 인원의 mid보다 크다.

   이럴때에는 어떤 방도로도 mid보다 작거나 같은 그룹으로 나눌수 없으므로, 그룹인원의 수를 0으로 초기화 해주고, 그룹의 수를 INF로 해준다.

이 문제는 평소 코에서 나오지 않는 트리dp 문제인데다가, 이분탐색까지 활용해야되서 어려웠던 문제였다.

dp 테이블을 설계하는 것부터, 그룹의수가 k이면서 최소의 그룹인원 수를 어떻게 찾아하는지 생각하기 어려운 문제였다.

이 문제는 카카오 시험이 끝난뒤, 알고리즘 고수분들을 이야기를 통해, 어떻게 풀어야할지 감을 잡았고,

문제가 나오고 실제로 푸는데에도 시간이 오래걸린 문제였다.

이 문제가 다시 나오면 풀수 있다는 확신은 없지만, 한번 경험해봤으니 이러한 문제도 있다라는 것을 배운점에 만족했다.

import heapq

def solution(n, start, end, roads, traps):
    answer = 0
    INF = float('inf')
    dp = [[INF for _ in range(n+1)] for _ in range(1<<len(traps))]
    traps_index ={value:ind  for ind,value in enumerate(traps) }
    node_list = []
    graph =[[] for _ in range(n+1)]

    for road in roads:
        x,y,pay = road
        graph[x].append([y,pay,0])
        graph[y].append([x,pay,1])

    heapq.heappush(node_list,(0,start,0))
    dp[0][start] = 0
    while node_list:
        cur_time,cur_node,state = heapq.heappop(node_list)
        if end == cur_node:
            answer = cur_time
            break
        if dp[state][cur_node] < cur_time:
            continue
        for next_node,pay,flag in graph[cur_node]:
            next_state = state
            if cur_node in traps:
                if next_node in traps:
                    cur_flag = ((1&(state>>traps_index[cur_node])) + 
                    (1&(state>>traps_index[next_node])))%2
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = (1&(state>>traps_index[cur_node]))
            else:
                if next_node in traps:
                    cur_flag =  (1&(state>>traps_index[next_node]))
                    next_state = state^(1<<traps_index[next_node])
                else:
                    cur_flag = 0
            
            if cur_flag == flag:
                if dp[next_state][next_node] > cur_time + pay:
                    dp[next_state][next_node] = cur_time + pay
                    if next_node in traps:
                        heapq.heappush(node_list,(dp[next_state][next_node], next_node,next_state ))
                    else:
                        heapq.heappush(node_list,(dp[next_state][next_node],next_node,next_state))

    return answer

이 문제를 핵심은 트랩을 밟았을 때의 상태를 어떻게 저장할 것인가.

저장한 그 상태를 통해 현재 길의 상태를 어떻게 알 수 있을가인가.

이 문제는 총 4가지 경우가 있다고 볼 수 있다.

트랩이 아닌  곳 -> 트랩이 아닌곳

트랩이 아닌 곳 -> 트랩인 곳

트랩인 곳 - > 트랩이 아닌곳

트랩인 곳 -> 트랩인 곳

이렇게 총 4가지 경우가 있을거고, 각각의 상태를 구분해서, 하면 된다.

우리는 먼저 주어진 경로들을 2가지 형태로 저장해놔야한다.

원래 주어진 정방향과, 이게 뒤집혔을때 가는 역방향이다. 이걸 나는 (다음노드, 시간, 상태) 로 넣어놨다.

0이면 정방향

1이면 역방향을 의미하는 식으로 넣어놨다.

트랩은 최대10개 밖에 없고, 트랩의 상태는 비트마스킹을 통해 나타낼수있다.

그렇게 하기 위해 각각의 trap들의 index로 각자의 위치를 매핑시켜줬다.

그러면 인제부터 각위치의 비트가 1이면 해당 위치의 트랩이 활성화 된 상황이고, 비활성화일때는 0이다.

그리고 우리는 각 상태에서 다익스트라를 돌리는 것이기 때문에 최대 (2**10) * N개의 distance 테이블을 만들어놓고 탐색을 하면 된다.

원래의 다익스트라와 비슷하게 하지만, 우리는 state를 통해 현재 길을 이용할 수 있는지 없는지 판별을 해줘야한다.

한 그래프에 정방향, 역방향을 전부 넣어놨기 때문에, state를 통해서 해당 길을 이용할 수 있는지 찾아야한다.

먼저 가장 쉬운

현재 노드가 트랩이 아닐때이다.

만약 다음 노드가 트랩이 아니라면, 이 길은 항상 정방향이다. 그러므로 저장해놓길 0으로 저장해놓은 길들만 이용이 가능하다.

만약 다음 노드가 트랩이라면, state를 통해 해당 트랩이 활성화 되어있는지 판별을 하면 된다.

판별하는 방법은 현재 state를 해당 트랩의 index만큼 >> 오른쪽으로 비트 이동을 시킨다. 그리고 1과 & 연산을 하면 된다.

이게 1이면 활성화가 된 상태이고, 아니면 비활성화 상태이다.

다음은 현재노드가 트랩일때이다.

현재노드가 트랩이고, 다음노드가 트랩이 아닐때에는 위와 동일하므로 넘어가겠다.

가장 많이 고민했던, 현재노드와 다음노드가 전부 트랩일때이다.

이때는 총 4가지 경우가 생긴다.

1. 현재노드 비활성화 다음노드 비활성화

2 .현재노드 활성화 다음노드 비활성화

3. 현재노드 비활성화 다음노드 활성화

4. 현재노드 활성화 다음노드 활성화

총 4가지 경우가 생긴다.

1번의 경우는 둘다 활성화가 안되어있기 때문에 정방향인 길들만 가면된다.

2,3번은 동일하고, 한쪽만 활성화 되어있으면, 그 길은 한번 뒤집힌거기 때문에 역방향인 길들만 가면 된다.

4번은 현재노드 다음노드 전부 활성화 되어있을때이다.

이때는 이 길이 2번 뒤집힌거기 때문에, 정방향인 길들만 가면된다.

그래서 나는 

(    ( 1 & (state>>traps_index[cur_node]) ) + ( 1&( state>>traps_index[next_node]) ) )%2

2개의 상태를 더해서 2로 나눈 나머지로 해서 정방향, 역방향을 구분을 해줬다. 이 외에도 xor 연산을 해도 된다.

우리는 이렇게 해서 해당 길이 갈 수 있는 길인지 아닌지 판별을 했다.

나머지는 다익스트라와 동일하게 하면되는데, 

그리고 현재의 상태와 비교하는게 아니라, 다음의 상태와 비교를 해서 판별을 해주었다.

만약 다음 노드가 트랩이라 한다면, 그 트랩은 활성화가 된 상태인거고, 그때 최소값으로 들어가야한다고 생각했다

그래서 각 현재 시간과 다음노드까지 걸리는 시간은 현재 state가 아닌, 만약 다음노드가 트랩이라면, 트랩의 상태에 따라, 변화된 state로 비교를 해서 구현을 했다.

import heapq
def solution(n, k, cmds):
    answer = ''
    def inverse(num):
        return -num
    max_heap = list(map(inverse,range(k)))
    min_heap = list(range(k,n))
    deleted = ['O' for _ in range(n)]
    deleted_stack = []
    heapq.heapify(max_heap)
    heapq.heapify(min_heap)
    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = command[1]
            command = command[0]
            num = int(num)
            if command == 'D':
                for _ in range(num):
                    heapq.heappush(max_heap,-heapq.heappop(min_heap))
            else:
                for _ in range(num):
                    heapq.heappush(min_heap,-heapq.heappop(max_heap))
        else:
            command = command[0]
            if command == 'C':
                delete_num = heapq.heappop(min_heap)
                deleted_stack.append(delete_num)
                deleted[delete_num] = 'X'
                if len(min_heap) == 0:
                    heapq.heappush(min_heap,-heapq.heappop(max_heap))
            else:
                restore_num = deleted_stack.pop()
                deleted[restore_num] = 'O'
                if min_heap[0] > restore_num:
                    heapq.heappush(max_heap,-restore_num)
                else:
                    heapq.heappush(min_heap,restore_num)
    answer = ''.join(deleted)
    return answer

2021 카카오 채용연계형 인턴십에서 나왔던 3번 문제인 표 편집을 다시 풀어보았다.

그때는 효율성에서 통과 못했던 문제였던지라, 문제가 공개되자마자 푼 문제이다.

시험이 끝난 후 생각했던 풀이를 옮기는 작업으로 많이 걸리지 않았지만, 바보같이 python2로 제출을 해서 오래걸렸다.

첫 풀이는

https://www.acmicpc.net/problem/1655

백준의 가운데를 말해요 와

https://www.acmicpc.net/problem/21944

 문제 추천 시스템 version2에서 풀었던 풀이를 이용했다.

가운데를 말해요에서 처럼 가운데에 유지해야할 인수를 선택된 행으로 해주면 된다.

나는 그걸 min_heap의 최저값으로 유지를 해줬다.

max_heap과 min_heap 2개로 나뉜 상태에서 문제에서 주어진 k보다 크거나 같은 수는 min_heap에 그대로 넣어줘서, 저장을 해줬고, k보다 작은 수는 max_heap에 -를 곱해서 넣어줬다.

heap을 넣었다 뺐다하면, 시간이 오래걸리니 heapq의 heapify 메소드를 이용해 한번에 바꿔주었다.

이 상태에서 min_heap의 최저값이 우리가 선택한 인덱스가 유지해주게 되면 된다.

U 명령어와 같은경우엔 우리가 선택한 인덱스가 줄어들어야한다.

그래서 max_heap에서 인수를 꺼내서 -1을 곱한뒤 min_heap에 넣어준다.

그와 반대로 D 명령어는 우리가 선택한 인덱스가 늘어나야하므로,

min_heap에서 인수를 꺼내서 -1을 곱한뒤 max_heap에 넣어준다.

다음으로 지우는 명령어인 C가 주의해야한다.

먼저 C를 시행하는 방법은 우리가 봤던 index를 없애는 것이므로, min_heap에서 빼준뒤, 그 값을 스택에 넣어주고,

상태를 변화를 해준다.

이대로 그대로 하면 min_heap이 아무것도 안남는경우가 생길것이다. 즉 길이가 5인데 만약에 k가 4인 상태에서

C명령어를 수행하면 min_heap이 전부 비워지게 된다. 그러면 가리키는 인덱스가 없어지는 것이므로, 

max_heap에서 하나를 꺼내와서 min_heap에 넣어주는 작업을 해주면 된다.

Z 명령어는 간단하다.

우리가 삭제한 변수들을 저장한 스택에서 pop을 한뒤 그 인자가

현재 우리가 가리키는 인덱스 보다 작으면  max_heap에 넣어주고 크면 min_heap에 넣어주면 된다.

이렇게 한뒤 마지막으로 상태를 join을 한뒤 돌려주면 된다.

class Node():
    def __init__(self,data):
        self.prev = None
        self.next = None
        self.data = data
        

def solution(n,k,cmds):
    node_list = [Node(0)]
    deleted_stack = []
    deleted_state = ['O' for _ in range(n)]
    for num in range(1,n):
        prev_num = node_list[num-1]
        cur_num = Node(num)
        prev_num.next = cur_num
        cur_num.prev = prev_num
        node_list.append(cur_num)
    
    cur_node = node_list[k]

    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = int(command[1])
            command = command[0]
            if command =='D':
                for _ in range(num):
                    cur_node = cur_node.next
            else:
                for _ in range(num):
                    cur_node = cur_node.prev
        else:
            command = command[0]
            if command == 'C':
                prev_num = cur_node.prev
                next_num = cur_node.next
                if next_num == None:
                    prev_num.next = None
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = prev_num
                elif prev_num == None:
                    next_num.prev = None
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = next_num
                else:
                    prev_num.next = next_num
                    next_num.prev = prev_num
                    deleted_stack.append(cur_node)
                    deleted_state[cur_node.data] = 'X'
                    cur_node = next_num
            else:
                restore_node = deleted_stack.pop()
                prev_num = restore_node.prev
                next_num = restore_node.next
                if prev_num != None:
                    prev_num.next = restore_node
                if next_num != None:
                    next_num.prev = restore_node
                deleted_state[restore_node.data] = 'O'
    answer = ''.join(deleted_state)
    return answer

두번째는 해설에도 나온 링크드리스트를 활용해서 풀면된다.

여기서 주의해야할 점은 prev나 next가 None일때 예외 처리르 어떻게 해주는지 이다. 그 외에는 일반적으로 하면 된다.

좀 더 개선한 코드는 

class Node():
    def __init__(self,data):
        self.prev = None
        self.next = None
        self.data = data
        

def solution(n,k,cmds):
    node_list = [Node(0)]
    deleted_stack = []
    deleted_state = ['O' for _ in range(n)]
    for num in range(1,n):
        prev_num = node_list[num-1]
        cur_num = Node(num)
        prev_num.next = cur_num
        cur_num.prev = prev_num
        node_list.append(cur_num)
    
    cur_node = node_list[k]

    for cmd in cmds:
        command = cmd.split()
        if len(command)>1:
            num = int(command[1])
            command = command[0]
            if command =='D':
                for _ in range(num):
                    cur_node = cur_node.next
            else:
                for _ in range(num):
                    cur_node = cur_node.prev
        else:
            command = command[0]
            if command == 'C':
                prev_num = cur_node.prev
                next_num = cur_node.next
                deleted_stack.append(cur_node)
                deleted_state[cur_node.data] = 'X'
                if next_num != None:
                    next_num.prev = prev_num
                if prev_num != None:
                    prev_num.next = next_num
                if next_num != None:
                    cur_node = next_num
                else:
                    cur_node = prev_num
            else:
                restore_node = deleted_stack.pop()
                prev_num = restore_node.prev
                next_num = restore_node.next
                if prev_num != None:
                    prev_num.next = restore_node
                if next_num != None:
                    next_num.prev = restore_node
                deleted_state[restore_node.data] = 'O'
    answer = ''.join(deleted_state)
    return answer

이 코드이다.

정확한 해설은 이보다 https://tech.kakao.com/2021/07/08/2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%9D%B8%ED%84%B4%EC%8B%AD-for-tech-developers-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%B4%EC%84%A4/

여기가 잘 설명되어있다.

def solution(n, lost, reserve):
    answer = 0
    student = [0]*(n+1)
    for k in lost:
        student[k] = -1
    for k in reserve:
        student[k] += 1

    for i in range(1,n+1):
        if student[i] > 0:
            for new_student in [i-1,i+1]:
                if 1<=new_student <=n:
                    if student[new_student] == -1:
                        student[i] -= 1
                        student[new_student] += 1
                        break
    for i in range(1,n+1):
        if student[i] >=0:
            answer += 1
    return answer

단순하게 풀었다.

stduent 만큼의 배열을 만들어 준 다음 index가 벗어나지 않게 앞에서부터 차근차근 나눠주는걸로했다.

그리고 답은 0 이상의 개수를 구해서 출력해주었다.

def solution(n, lost, reserve):
    answer = 0
    student = [0]*(n+1)
    for k in lost:
        student[k] = -1
    for k in reserve:
        student[k] += 1
    
    for i in range(1,n+1):
        if student[i] > 0:
            for new_student in [i-1,i+1]:
                if 1<=new_student <=n:
                    if student[new_student] == -1:
                        student[i] -= 1
                        student[new_student] += 1
                        break
                        
    answer = student.count(0) + student.count(1) -1
    return answer

 이런식으로 카운트 method를 써주어도 된다.

def solution(answers):
    ans = []
    person3 = [3,3,1,1,2,2,4,4,5,5]
    person2 = [2,1,2,3,2,4,2,5]
    result = [0,0,0]
    for ind,answer in enumerate(answers):
        if answer == (ind)%5+1:
            result[0] += 1
        if answer == person2[ind%len(person2)]:
            result[1] += 1
        if answer == person3[ind%len(person3)]:
            result[2] += 1

    max_result = max(result)
    for k in range(3):
        if result[k] == max_result:
            ans.append(k+1)
    return ans

반복되는 수들을 list로 만들어준다음 modulo 계산을 통해 해당위치의 값과 비교를 해주면 된다.

import collections
def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer)[0]

Couter를 이용해 쉽게 풀 수 있다.