바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

문제 개요

- 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 함

- 말이 최대한 몇 칸을 지날 수 있는지 (첫 번째 칸도 포함)

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

나의 코드

R, C = list(map(int, input().split()))
inputs = []
for _ in range(R):
    inputs.append(list(input()))

from collections import deque

def solution(R,C,inputs):
    max = 1
    # cand = deque([((0,0),inputs[0][0])])
    cand = set()
    cand.add(((0,0),inputs[0][0]))

    dx = [-1,0,0,1]
    dy = [0,-1,1,0]
    
    while cand:
        (x,y), a = cand.pop()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>R-1 or cy<0 or cy>C-1:
                continue
            else:
                if inputs[cx][cy] not in a:
                    cand.add(((cx,cy), a+inputs[cx][cy]))
                    if len(a+inputs[cx][cy]) > max:
                        max = len(a+inputs[cx][cy])                 
                    
    return max

print(solution(R,C,inputs))

우여곡절

- 구현은 크게 어렵지 않았으나, 그놈의 효율성 문제... ㅎ

- BFS에 deque가 사용된다면 안 된다니! :D set 자료형을 사용해야 했다

why? 중복 이슈

deque의 시간복잡도는 O(1)이 맞음. 그러나 deque를 사용한 코드를 보면 중복값에 대해서도 모두 O(1)의 연산을 하니, 아무리 O(1)이지만 중복값이 수없이 많다면... 효율성 문제 발생. set 자료구조자체가 중복을 허용하지 않기때문에 훨씬 효율적으로 처리하며, 아마 deque에도 중복체크 넣으면 효율적으로 개선될 것.

=>같은 위치에 같은 문자열을 가진 상황을 중복해서 확인할 필요없으니, 같은 값은 같은 객체로 취급하는 집합 자료형을 사용

이라는데...... 이 문제에서 어떤 경우에 중복이 발생하는지 아직 이해하지 못했다.

그냥 visted에서 deque와 set 모두 구현해보고 시간이 더 빠른 걸 택한다는...분도 계셨다.

더 알아봐야겠다.

참고: https://www.acmicpc.net/board/view/81429

- 한번도 방문한 적 없은 알파벳만을 선택한다는 조건(a) 자체가 → visit한 원소는 아예 제외한다는 조건(b)을 포함한다

: 즉, a가 구현되면 b를 별도로 구현할 필요가 없다

: 즉, 방문한 알파벳에 대한 리스트(a)만 체크하면, 이미 방문한 원소에 대한 리스트(visited)를 따로 생성할 필요가 없다

- 참, 저기서 add할 때 a.append(inputs[cx][cy])로 하면 안 된다. for문 전체에 global하게 해당되는 a가 변형되기 때문이다. 슬라이싱 통해 temp로 복제하는 방법도 있지만, 그보다는 그냥 마지막에 cand에 add할 때 '+' 를 사용해주는 게 best!

새로 배운 것

1. 문자열(string)은 자기들끼리 덧셈 연산이 된다.

print('a'+'b') #ab

2. set 자료형

- append가 불가능한 대신 add로!

- pop을 할 경우 임의의 원소가 반환되므로, remove를 사용해야 한다 (나는 여기서... 대강 pop으로 때려맞혀서 이건 수정해야 한답)

https://blockdmask.tistory.com/451

3. time 모듈로 코드 실행시간(시간복잡도) 측정

import time

#코드 하단에 추가
t0 = time.time()
print(time.time() - t0)

4. deque..

Deque(데크)는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조

https://excelsior-cjh.tistory.com/entry/collections-%EB%AA%A8%EB%93%88-deque

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

나의 코드

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1

    cand = deque()
    visited = [[[0,0] for _ in range(M)] for _ in range(N)] #3차원의 visited array
    cand.append(((0,0),0))
    visited[0][0][0] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0 and visited[cx][cy][i]==0:
                    if cx == N-1 and cy == M-1:
                        return visited[x][y][i] + 1
                    cand.append(((cx,cy),i))
                    visited[cx][cy][i] = visited[x][y][i] + 1

                elif inputs[cx][cy] == 1 and i==0:
                    cand.append(((cx,cy),1))
                    visited[cx][cy][1] = visited[x][y][0] + 1

    return -1

print(solution(N,M,inputs))

1. BFS + Depth !!를 효율적으로 구현

 visited[cx][cy][i] = visited[x][y][i] + 1

2. visited를 두 유형으로 나누어야 한다(visited array를 3차원으로 표현) → 벽을 부수기 전 & 벽을 부순 후.

- 이유:

결국 방문배열이란 것은, bfs에서 '모든 경우'를 살펴보며 진행할 때, 같은 행위를 두번하면 비효율적이니 그걸 막기 위해 사용합니다.

따라서 방문배열은 '모든 경우'를 나타낼 수 있어야 합니다. 일반적인 bfs 문제에서 모든 경우는 결국 '이 위치에 이미 왔었다' 입니다.

따라서 그냥 2차원 방문배열로 나타내면 되는거구요.

이 문제에서 모든 경우는 말로 설명하자면 '해당 위치에 벽을 부순 상태로 이미 왔었거나, 해당 위치에 아직 벽을 부수지 않은 상태로 이미 왔었다.' 정도가 되겠습니다.

따라서 이걸 표현하기 위해 3차원 배열로 나타낸거구요.

이런식으로 모든 경우를 나타낼 수 있는 방문배열을 만들지 않을 경우 다음과 같은 문제가 발생합니다.

출처: https://www.acmicpc.net/board/view/67446

 - 추가 설명:

모든 작업을 한 번의 BFS 탐색을 통해 처리해야했기 때문에, 최적의 벽을 '탐색'하는 것보다는 '기록'하는 방식이 필요했다.

그리고 3차원 배열을 통해서 이 문제를 해결할 수 있었다.

visited에는 이미 우리에게 친숙한 2차원 배열의 각 인덱스 [x][y]뿐 아니라 w라는 값을 하나 더 만들어서 (x, y)까지 오는 과정에서 벽을 뚫은 경우와 그렇지 않고 온 경우를 모두 기록해준다. (각각 1번 인덱스와 0번 인덱스에 기록)

다시 말해, visited[x][y][0]에 (x, y)까지 벽을 뚫지 않고 왔을 때 걸린 거리(시간)을 기록해준다.

반대로, visited[x][y][1]에는 (x, y)까지 오는 데 벽을 한 번이라도 뚫고 온 경우 걸린 거리(시간)을 기록해준다.

출처: https://seongonion.tistory.com/107

추가: https://nahwasa.com/entry/BFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-%EB%B0%B0%EC%97%B4-BFS-%EA%B7%B8%EB%9E%98%ED%94%84-BFS

3. 이하 코드는 항상 요긴하게 씁사..

        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue

- 배운 점: BFS문제 다 똑같지 않다. 변형 테크닉이 어렵고, 익숙해지면 아이디에이션 생각보다 간단하다.

나의 방황 기록

초기 코드1: Depth를 2 type으로 구분하지 않고 1 type으로 몰아갔다..

→ 당연히 틀림 (초반에는 경로가 비효율적이더라도 벽을 아직 부수지 않아서 최종 목적지까지 다다를 수 있는 경로가 배제됨)

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):

    cand = deque()
    cand.append(((0,0),0))
    inputs[0][0] = 1

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0:
                    inputs[cx][cy] = inputs[x][y]+1
                    if cx == N-1 and cy == M-1:
                        return inputs[cx][cy]
                    cand.append(((cx,cy),i))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        inputs[cx][cy] = inputs[x][y]+1
                        cand.append(((cx,cy),1))
    
    return -1

print(solution(N,M,inputs))

초기 코드2: visited 내역을 queue의 각 원소마다 포함해줬다

→ 예상한 대로 시간초과... 애초에 이렇게 풀 수 있는 문제 거의 없음

→ 조건 추가된 depth 계산은, 무조건 이 방식 말고 다른 방식을 떠올려야 함

(ex. visited array를 별도로 생성하여 0->1->2.. 이런 식의 표현을 베이스로 깔거나(이후 변형) / 조건 잘 따져서 global queue(set)을 생성하거나 등등. )

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1
    
    cand = deque()
    cand.append(((0,0),0,[(0,0)]))

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    while cand:
        ((x,y),i,visit) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if (cx<0 or cx>N-1 or cy<0 or cy>M-1) or ((cx, cy) in visit):
                continue
            else:
                if inputs[cx][cy] == 0:
                    if cx == N-1 and cy == M-1:
                        return len(visit) + 1
                    cand.append(((cx,cy),i, visit+[(cx,cy)]))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        cand.append(((cx,cy),1,visit+[(cx,cy)]))
    
    return -1

print(solution(N,M,inputs))

https://school.programmers.co.kr/learn/courses/30/lessons/43238

문제 요약

목표: 총 심사 시간 최소화.

Input

n: 입국 심사 기다리는 사람 수 (엄~~~~청 큼.)

Times: ‘각 심사관이 한 명을 심사하는 데 걸리는 시간’이 담긴 배열 (각 시간이 엄청 큼) (사람 수는 10만.)

e.g) 6, [7,10]

Return

심사 총 시간.

e.g) 28

한 심사대 - 한 명

가장 앞에 있는 사람: 비어 있는 심사대에서 심사 받기.

더 빨리 끝나는 심사대 있으면: 기다렸다가 그곳에서 심사 받기.

*20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

예제

(7) 끝난 사람 1

(10) 끝난 사람 2

(14) 끝난 사람 3

(20) 끝난 사람 4

(21) 끝난 사람 5

(28) 끝난 사람 6

(30) 끝난 사람 6

정답은 각 시간의 배수 중 하나.

• 7 (<=7*1, 10*0) : 1
• 14 (<=7*2, 10*1) : 3
• 21 (<=7*3, 10*2): 5
• 28 (<=7*4, 10*2): 6

• 10 (<=10*1, 7*1) : 2
• 20 (<=10*2, 7*2) : 4
• 30 (<=10*3, 7*4) : 7 (6)
• 40 (<=10*4, 7*5) : 9 (6)

times의 각 원소의 배수들을 모두 나열.

각 배수를 우측의 부등호처럼 표현하고 곱한 수의 합이 n이상인 경우 중

가장 작은 배수값을 찾아냄.

이때 합이 n이상이면 max(합, n)으로 간주.

28 // 7 = 4

28 // 10 = 2

내 코드

def solution(n, times):
    
    times.sort()
    start = times[0]
    end = times[0]*n
    cand = end #candidate: 정답 후보
    
    while start <= end: #이분탐색은 start, end를 지정해주어야 함
        mid = (start+end) // 2 #start, end를 바탕으로 mid 생성

        if sum([mid//i for i in times]) < n:
            start = mid + 1
        elif sum([mid//i for i in times]) > n:
            cand = mid
            end = mid - 1
        else:
            if start==end: #해당 조건 없으면 무한루프
                return start
            cand = mid
            end = mid
    
    #반복문 종료되었을 때, 반복문의 최종 candidate값으로 정답을 반환
    
    return cand

이분탐색의 사용 조건: 리스트에 원소가 이미 '잘 정렬되어 있을 때'

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정.

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

    return None

https://school.programmers.co.kr/learn/courses/30/lessons/81302

문제 개요

<Input>

Places: ‘자리에 앉아있는 응시자들의 정보와 대기실 구조’를 대기실별로 담은 2차원 문자열 배열.

*대기실은 5개이며, 각 대기실은 5x5 크기

*P(응시자가 앉아있는 자리),O(빈 테이블),X(파티션)로 이루어진 문자열

*Rule

1. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
2. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예: [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

<Output>

각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아.

예: [1, 0, 1, 1, 1]

내 코드

못생긴 코드ㅡ... 코드가 왜 이렇게 길지? ^__^

ㅎㅎ

모범코드 보면서 공부해야겠다..

from collections import deque
def solution(places):
    
    answer = [1 for _ in range(5)]

    next_i, next_j = [-1, 0, 0, 1], [0, -1, 1, 0]
    doub_i, doub_j = [-2, 0, 0, 2], [0, -2, 2, 0]
    cross_i, cross_j = [-1, -1, 1, 1], [-1, 1, -1, 1]

    cnt = -1
      
    for place in places:
        cnt += 1
        place = list(map(list, place))
        p_lst = deque() #각 대기실에서 P가 있는 좌표 리스트
        for i, row in enumerate(place):
            for j, col in enumerate(row):
                if place[i][j] == 'P':
                    p_lst.append((i,j))
                    
        loopbreak = False
        while p_lst and (loopbreak == False):
            (i,j) = p_lst.popleft() #현재 중심이 되는 좌표 (i,j)
            for k in range(4): #위반 케이스 1
                ci = i + next_i[k]
                cj = j + next_j[k]
                
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    answer[cnt] = 0
                    loopbreak = True
                    break
                
            if loopbreak == True: break
            for k in range(4): #위반 케이스 2
                ci = i + doub_i[k]
                cj = j + doub_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if place[i + next_i[k]][j + next_j[k]] == "O":
                        answer[cnt] = 0
                        loopbreak = True
                        break
            if loopbreak == True: break
            for k in range(4): #위반 케이스 3
                ci = i + cross_i[k]
                cj = j + cross_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if k == 0:
                        if place[i-1][j]=='X' and place[i][j-1]=='X': continue   
                    elif k == 1:
                        if place[i-1][j]=='X' and place[i][j+1]=='X': continue  
                    elif k == 2:
                        if place[i][j-1]=='X' and place[i+1][j]=='X': continue
                    elif k == 3:
                        if place[i][j+1]=='X' and place[i+1][j]=='X': continue
                    
                    answer[cnt] = 0
                    loopbreak = True
                    break

    return(answer)

• 테케 3, 8, 31번 오답의 반례 : 'POP'가 포함된 경우 '0'을 반환해야 한다
• answer의 default 원소로 1 채워놓고, 위반하는 경우=>  0으로 바꿈 & 다음 place로 바로 이동(기존 반복문 break)
• visited 리스트 이용해서 좀 더 효율적으로 구현했었는데 => 딱히 효과가 없다 ^__^ BFS 개념에 집착하지 말자,,

• 이중 반복문 빠져나오는 법: loopbreak과 같은 변수 사용,,
• 반복문 continue 개념

https://velog.io/@banana/break-continue%EB%A1%9C-%EB%B0%98%EB%B3%B5%EB%AC%B8-%EC%A0%9C%EC%96%B4%ED%95%98%EA%B8%B0

• 상하좌우 살피는 예쁜 코드 [-1,0,0,1] 등 사용해서 짰는데 (왜 전체 코드가 이리 장황할까?)

그래도 아래 코드는 유용하게 사용하쟈~

dx = [1,-1,0,0]
dy = [0,0,1,-1]

for k in range(4):
            cx = i + dx[k]
            cy = j + dy[k]
            if cx < 0 or cx >= N or cy < 0 or cy >= M:
                continue
            if arr[cx][cy] != 1:
                graph[i*M+j].append(cx*M+cy)

공부한 자료

https://daebaq27.tistory.com/82

https://veggie-garden.tistory.com/42

https://school.programmers.co.kr/learn/courses/30/lessons/43164#qna

풀이 코드

from collections import deque

def solution(tickets):
    # 주어진 항공권은 모두 사용
    # 주어진 공항수 꽤 많음
    tickets.sort()
    dic = {}
    for tic in tickets:
        if tuple(tic) not in dic.keys():
            dic[tuple(tic)] = 1
        else:
            dic[tuple(tic)] +=1

    for root in [x for x in tickets if x[0]=="ICN"]:
        deq = deque()
        deq.append([root]) #dic, visited list
        while deq:
            visited = deq.popleft() #현재 다루는 dic과 그것이 사용된 횟수
            for tic in tickets:
                if (visited[-1][1] == tic[0]) and (visited.count(tic) < dic[tuple(tic)]):
                    if len(visited)+1 == len(tickets):
                        mod = [x[1] for x in visited+[tic]]
                        mod.insert(0, visited[0][0])
                        # print(mod)
                        return mod
                    else:
                        deq.append(visited+[tic])


    return #방문하는 공항 경로 #알파벳 순서가 앞서는 경로

• 알파벳 정렬은, 처음부터 input 리스트 'tickets'을 sort시키고 시작하면 해결된다.
• DFS의 특이한 버전이었다. 
  
  - input에 동일한 티켓이 여러 장 포함될 가능성이 있다. 따라서 다음 탐색 노드를 추가할 때 visited 존재 여부로 결정해서는 안 된다. (이미 방문하여 visited에 존재하지만, 탐색 가능한 것이 여전히 남아 있을 수 있다)
     ✂︎ 미리 counter dictionary를 생성하고, visited가 포함하는 개수와 비교해야 한다:
          visited.count(tic) < dic[tuple(tic)]
  
  - 지금까지 경로 데이터를 모두 가지고 있어야 한다
     ✂︎ deque의 원소 자체를 visited 리스트로 저장
     ✂︎ deep 하게 for문 돌 때, 기존 visited에 현재 탐색 원소를 append하여 기존 visited의 몸뚱아리를 키우는 것이 아니다.
         별도의 리스트(visited + [tic])로 만들어 그것을 deque에 append한다.
         (효율성 괜찮나..? 싶었으나 더 간단한 방법이 떠오르지 않음)
  
  
• 리스트를 원소로 가지는 리스트의 처리는 Unhashable error에 주의해야 한다. 나는 dictionary 생성 및 count를 위해 각 리스트 원소를 tuple로 변환하였다.
  https://daewonyoon.tistory.com/363 

• 트리 형태로 시각화한 후 수도코드 짜는 게 훨씬 수월할 듯.

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

문제 개요

비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램.

입력한 키: 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표

'-' : 백스페이스 (커서 바로 앞에 있는 글자를 지움(글자가 있으면))

‘<‘: 커서를 왼쪽으로 1만큼 움직임 (움직일 수 있다면)

‘>’: 커서를 오른쪽으로 1만큼 움직임 (움직일 수 있다면)

나머지 문자는 비밀번호의 일부. (나중에 백스페이스를 통해서 지울 수 있음)

Input

첫째 줄에 테스트 케이스의 개수

각 테스트 케이스는 한줄로 & 입력한 순서대로 길이가 L인 문자열 (input이 매우 큼 => 효율성이 중요함)

<<BP<A>>Cd-

Output

비밀번호를 출력한다. (비밀번호의 길이는 항상 0보다 크다.)

문제 풀이

class Node:
    def __init__(self, x):
        self.item = x
        self.before = None
        self.next = None

class LinkedList:
    def __init__(self) -> None:
        dummy = Node(-1)
        self.head = dummy
        self.cursor = self.head
    
    def append(self, x):
        new = Node(x)
        new.next = self.cursor.next
        new.before = self.cursor # type: ignore
        if self.cursor.next != None:
            self.cursor.next.before = new
        self.cursor.next = new # type: ignore
        self.cursor = new
        
    def delete(self):
        if self.cursor == self.head: return
        self.cursor.before.next = self.cursor.next
        if self.cursor.next != None:
            self.cursor.next.before = self.cursor.before
        self.cursor = self.cursor.before
    
    def left(self):
        if self.cursor == self.head: return
        self.cursor = self.cursor.before
        
    def right(self):
        if self.cursor.next == None: return
        self.cursor = self.cursor.next
        
    
L = int(input())
inputs = []
for _ in range(L):
    inputs.append(input())

for cmd in inputs:
    link_lst = LinkedList()
    answer = []
    for i in range(len(cmd)):
        if cmd[i] == "-":
            link_lst.delete()
        elif cmd[i] == "<":
            link_lst.left()
        elif cmd[i] == ">":
            link_lst.right()
        else:
            link_lst.append(cmd[i])

    crt = link_lst.head
    while crt.next != None:
        crt = crt.next
        answer.append(crt.item)
    
    print(''.join(answer))

=> cursor의 위치를 정확히 정의해야 함!

https://school.programmers.co.kr/learn/courses/30/lessons/81303

양방향 Linked List에 구현 로직이 동일한 것 같은데

왜 내 코드는 효율성 테스트를 통과하지 못하는 거지..?

비교해서 효율성 개선 방법 찾아내야겠다 ㅠㅠ

효율성 통과 코드

class Node:
    def __init__(self,data=None,prev=None,next=None):
        self.prev= prev
        self.data= data
        self.next= next
class DoubleLinkedList:
    def __init__(self,data=None):
        # for easy calculate at end set two dummy head_dummy and tail_dummy
        self.head = Node()
        self.tail = Node()
        # link two dummy
        self.head.next = self.tail
        self.tail.prev = self.head
        self.current_ptr = self.head
        self.delete_array = []


    def init_insert(self,data):
        new_node = Node(data)
        # get tail-1 node
        node = self.tail.prev
        node.next = new_node
        
        new_node.prev = node
        new_node.next = self.tail
        
        self.tail.prev = new_node
    
    def set_current_ptr(self, num):
        for i in range(num+1):
            self.current_ptr = self.current_ptr.next

    
    def c_instruction(self):
        self.before_ptr = self.current_ptr
        self.current_ptr = self.current_ptr.next
        if(self.current_ptr == self.tail):
            self.current_ptr = self.current_ptr.prev
            self.current_ptr = self.current_ptr.prev
        # delete!!
        self.delete_array.append(self.before_ptr)
        # modify linked list
        self.before_ptr.prev.next = self.before_ptr.next
        self.before_ptr.next.prev = self.before_ptr.prev
        
    def u_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.prev
    
    def d_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.next
    
    def z_instruction(self):
        node_to_z = self.delete_array.pop(-1)
        node_to_z.prev.next = node_to_z
        node_to_z.next.prev = node_to_z
    def return_del_array(self):
        to_return = []
        for i in range(len(self.delete_array)):
            to_return.append(self.delete_array[i].data)
        return to_return

            
def solution(n,k,cmd):
    answer_string = ["O"]*n
    my_list = DoubleLinkedList()
    for i in list(range(n)):
        my_list.init_insert(i)
    my_list.set_current_ptr(k)
    for instruction in cmd: 
        if instruction[0] == "U":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.u_instruction(move_cnt)
        elif instruction[0] == "D":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.d_instruction(move_cnt)
        elif instruction[0] == "C":
            my_list.c_instruction()
        elif instruction[0] == "Z":
            my_list.z_instruction()
    deleted_element = my_list.return_del_array()
    for element in deleted_element:
        answer_string[element] = "X"
    return ''.join(answer_string)

효율성 통과하지 못하는 코드

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = [i for i in range(n)] #비효율의 원인
    link_lst = LinkedList()
    
    for i in answer:
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    final = ["O" if x not in del_lst else "X" for x in answer] #비효율의 가장 큰 원인: O(N)
    final = ''.join(final)
    # print(final)
    return final

• 양방향 LinkedList까지 로직 참 좋았다 ! 
• input의 크기가 무지막지하게 크다는 사실을 기억해야 한다
• input 처리에 대한 단순한 코드때문에 => 눈덩이처럼 커진 비효율이,,,!!!!!!!
• input의 value는 사실 중요하지 않다. 서로가 '중복되지 않음'만 확인되면 된다.
  나는 처음에 각 Node를 생성하고 해당 노드의 value(Node.item)가 저장된 answer 리스트를 따로 생성했었다.
  그러나, integer로 채워진 answer 리스트를 임의로 생성할 필요가 없었다. 생성하면 무조건 비효율 문제가 발생하게 된다
  => answer 생성: O(N) + final 생성: O(N) = 2*O(N)
  이미 각 Node들의 item 값은 서로 다르기때문에 '중복되지 않음'의 속성이 반영되어 있다.
• 초반에 append한 각 Node의 value 값과 idx 값이 동일함을 이용하여 answer 리스트의 원소로 미리 "O"를 넣어둔다
• 마지막에 del_lst의 item값을 answer의 idx값으로 이용하여 answer 리스트에서 해당 idx의 값을 "X"로 바꾸어준다
  => final 리스트 따로 생성하지 않음! answer 리스트 내에서 변형.
  => O(N) + O(len(del_lst))
  => 이때 N보다 del_lst가 작으므로, N이 무지막지한 크기인 본 문제에서 효율성을 크게 높일 수 있다..!!

최종 효율성 통과 코드

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = ["O" for _ in range(n)] #효율 개선
    link_lst = LinkedList()
    
    for i in range(len(answer)):
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    for x in del_lst[1:]: #주의
        answer[x] = "X" #효율 개선
        
    answer = ''.join(answer)
    print(answer)
    return answer

너무 잘 정리된 LinkedList 개념

https://wayhome25.github.io/cs/2017/04/17/cs-19/

표 편집 솔루션에 대한 좋은 레퍼런스

https://latte-is-horse.tistory.com/329

https://life318.tistory.com/2

유용한 링크

https://blockdmask.tistory.com/443

https://blockdmask.tistory.com/445

부모클래스의 생성자를 상속받으려면 => 자식클래스의 생성자 __init__ 아래 줄에 super 사용해야 함.

반면, 부모클래스의 메소드를 상속받으려면, 자식클래스 괄호 안에 부모클래스 언급만 하고, super 할 것  없음.

만약 메소드를 변형하고자 한다면 그게 곧 '오버라이딩' 한다는 거임.그때 def 하면 됨.

이외 자식클래스에만 별도로 추가로 함수 정의하고자 한다면 def 하고.

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

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

(버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.)

Tip & 풀이 핵심

1. '시간제한 1초' & '첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다.'

• (시간제한이 1초이면) input 길이가 10,000이 넘어가면 O(N**2)의 알고리즘으로 절대 풀 수 없음!!!
  => Bubble sort, Insertion sort, Selection sort: O(N**2)
  => Merge sort: O(N* logN) / Quick sort
  => Counting sort

2. Merge sort에서 swap하는 과정이 있더라!

   => "어떻게 하면 Merge sort 로직에 result 구하는 코드 구현?"

모범 코드

모범 코드 보면서 효율적이고 정확하게 코드 짜는 방법을 많이 배웠다.

import sys
input = sys.stdin.readline
result = 0 #최종 결과값

N = int(input())
A = list(map(int, input().split()))
A.insert(0,0) # 0 index에 0을 추가 # index 처리 쉽게 하기 위함
tmp = [0] *(N+1) # A배열의 크기를 맞춤 # A를 바로 처리하기 부담스러우므로 복제

def merge_sort(s, e):
    global result
    if e-s < 1: return
        
    else:
        m = (e+s) // 2
        merge_sort(s, m)
        merge_sort(m+1, e)
        
        for i in range(s, e+1):
            tmp[i] = A[i]
        
        # two pointers
        k = s #현재 바꾸어야 하는 A의 index
        index1 = s
        index2 = m+1
        while index1 <= m and index2 <=e:
            if tmp[index1] > tmp[index2]:
                A[k] = tmp[index2] #swap
                result += (index2-k)
                k += 1
                index2 += 1
                # A[index2] = tmp[index1]
            
            else:
                A[k] = tmp[index1]
                k += 1
                index1 += 1
         
        while index1 <= m:
             A[k] = tmp[index1]
             k += 1
             index1 += 1
        
        while index2 <= e:
            A[k] = tmp[index2]
            k += 1
            index2 += 1
        

merge_sort(1, N) # 1번째 idx부터 N번째 idx까지 merge_sort 진행
print(result)

• global 이해 필수: https://lets-hci-la-ai-withme.tistory.com/68
• A.insert(0,0) : idx 처리 편하도록 0번째에 0value 추가
• tmp 생성: input 리스트(A) for문으로 복제 (value 값 저장하여 안전하게)
• 재귀식에서 base condition 처리, return만: if e-s<1: return
• 함수에서 return이 없을 수 있다. 단 위 경우, 전역변수인 result에 계속 값을 저장.
• 특히, Merge_sort에서 return 없이, 시작 idx(s)와 끝 idx(e)만을 입력 파라미터로 이용하여 처리 가능.
• k는 현재 처리해야 하는 A에서의 idx. 따로 지정.

내가 작성한 시간 초과 코드:

def merge_sort(inputs):
    
    if len(inputs) < 2:
        return inputs, 0
    
    else:
        mid = len(inputs)//2
        left = inputs[:mid]
        right = inputs[mid:]
        left_ , l_count  = merge_sort(left)
        right_ , r_count = merge_sort(right)
        
        merged, count = merge(left_, right_, l_count, r_count)

        return merged, count

def merge(left_, right_, l_count, r_count):
    merged = []
    count = (l_count + r_count)
    l_ptr = 0
    r_ptr = 0
    
    while l_ptr < len(left_) and r_ptr < len(right_):
        if left_[l_ptr] > right_[r_ptr]:
            # left에서 right_[r_ptr]보다 큰 원소 중 최소인 것의 idx 찾기
            s, mid, e = 0, 0, len(left_)-1

            while s <= e:
                mid = (s + e)//2
                if right_[r_ptr] == left_[mid]:
                    break
                
                elif right_[r_ptr] < left_[mid]:
                    e = mid -1
                else:
                    s = mid+1
                        
            if left_[mid] <= right_[r_ptr] < left_[e]:
                count += len(left_) - (mid+1)

            elif right_[r_ptr] < left_[s]:
                count += len(left_) - s

            elif mid > 0 and mid <= len(left_)-2:
                idx = mid+1
                while right_[r_ptr] >= left_[idx]:
                    idx += 1
                count += len(left_) - idx
            else:
                print(-1)
            
            merged.append(right_[r_ptr])
            r_ptr += 1
        else:
            merged.append(left_[l_ptr])
            l_ptr +=1
    
    while r_ptr < len(right_):
        merged.append(right_[r_ptr])
        r_ptr += 1
        
    while l_ptr < len(left_):
        merged.append(left_[l_ptr])
        l_ptr +=1
    
    return merged, count

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))
        print(merge_sort(inputs)[1])