ABC 344 E번 복기 - 원소에 바로 접근할 수 있는 연결리스트 구현하는 법

E - Insert or Erase (atcoder.jp)

E - Insert or Erase

 

 

수열 A의 원소들이 모두 서로 다른 원소이며, 삽입하는 연산과 삭제하는 연산을 수행한다.

 

연산을 수행할 때마다 A의 원소들은 모두 서로 다르다는 것이 보장된다.

 

연산은 2가지이다.

 

x 원소 바로 뒤에 y를 삽입하는 연산

 

x를 삭제하는 연산

 

연결리스트로 접근해야지 생각하긴 했는데... x를 어떻게 바로 찾아야 하나 고민하다가 실패했다..

 

연결리스트는 접근하는데 O(N)이라서.. 분명히 시간초과일텐데

 

하지만 모든 원소들이 항상 서로 다르다는것이 핵심 포인트이다.

 

그래서 굳이 인덱스로 x를 찾아야지라고 생각하는게 아니라..

 

그냥 x로 바로 찾으면 되잖아

 

원소들이 매번 서로 다르기 때문에 원소들 자체가 고유값이라서

 

양방향 연결리스트로 구현하자

 

오른쪽으로 진행하는 방향(next), 왼쪽으로 진행하는 방향(prev) 2개의 hash를 사용

 

어차피 오른쪽에다가 삽입하고, 원소를 삭제하기만 할텐데 왼쪽으로 진행하는 방향을 해야하나?

 

왼쪽 방향을 하지 않으면 head를 알기 어려워서, 마지막에 A를 출력하기가 어렵다

 

그림을 머릿속으로 생각해보고 그대로 구현하면 된다

 

 

 

기본적으로 X옆에 Y를 삽입할려고 한다면...

 

X로 접근하면 X의 오른쪽 X > K를 찾고

 

X의 오른쪽에 Y를 삽입하므로 X > Y > K, X < Y < K

 

right[X] = Y, right[Y] = K, left[Y] = X, left[K] = Y  

 

문제는 X가 꼬리 부분일 수 있다는 점이다. 이 경우 X의 오른쪽이 존재하지 않는다.

 

그러면 right[X] = Y, left[Y] = X만 하면 된다 

 

---------------------------------------------------------------------------------------------------------------------------------

 

삭제 연산은 어떻게 해야할까

 

X의 오른쪽과 왼쪽을 바로 알 수 있는데 X > K, Z < X

 

여기서 X를 삭제하면?

 

 

 

 

right[Z] = K, left[K] =Z로 하면 된다. 그리고 X의 오른쪽, 왼쪽 연결을 삭제

 

삭제 연산은 X가 머리부분, 꼬리부분일 때 주의해야한다.

 

머리부분일 경우 왼쪽이 없고 꼬리부분일 경우 오른쪽이 없다.

 

-1 < X > < Y 형태로 되어 있는데 X를 삭제한다면 Y가 머리부분이 된다. 

 

그러면 X의 오른쪽 부분 Y를 찾은 다음 X의 연결을 삭제하고 Y의 왼쪽을 -1로 연결시킨다.

 

Z > < Y > < X 형태로 되어 있는데 X를 삭제한다면 Y가 꼬리부분이 된다.

 

X의 왼쪽부분 Y를 찾고, X의 연결을 삭제한다음 Y의 오른쪽을 -1로 연결시키면 된다.

 

구현은 생각하면서 하면 쉽게 할 수 있다..

 

핵심은 인덱스로 구현하는게 아니라 모든 원소가 서로 다른 원소이기 때문에 원소로 해당 위치에 접근하게 한다면...

 

모든 연산을 O(1)에 수행할 수 있다는 점

 

#서로 다른 모든 원소에 대하여
#x의 오른쪽에 y를 삽입하고 x를 삭제하는 연산을 수행하는 연결리스트
n = int(input())

A = list(map(int,input().split()))

right = {} #오른쪽 방향
left = {} #왼쪽 방향

for i in range(n-1):
    
    right[A[i]] = A[i+1]

right[A[n-1]] = -1 #꼬리의 오른쪽은 -1
 
for i in range(n-1,0,-1):

    left[A[i]] = A[i-1]

left[A[0]] = -1 #head의 왼쪽은 -1

q = int(input())

for _ in range(q):
    
    query = list(map(int,input().split()))

    if query[0] == 1: #x의 오른쪽에 y를 삽입
        
        x,y = query[1],query[2]

        if right[x] == -1: #x가 꼬리인 경우
            
            #x의 오른쪽을 y로 하고, y의 왼쪽을 x, y의 오른쪽을 -1
            right[x] = y 
            left[y] = x
            right[y] = -1
        
        else: #x가 꼬리가 아닌 경우 x > y > k, x < y < k가 되어야한다.
        
            k = right[x]
            right[x] = y
            right[y] = k #x > y > k
            left[y] = x
            left[k] = y
    
    else:

        x = query[1] #x를 삭제하는 연산

        if right[x] == -1: #x가 꼬리인 경우
            
            y = left[x] #x의 왼쪽을 찾고

            del right[x]
            del left[x]

            right[y] = -1 #x의 왼쪽인 y의 오른쪽을 -1로
        
        elif left[x] == -1: #x가 head인 경우
            
            y = right[x] #x의 오른쪽을 찾고

            del right[x]
            del left[x]

            left[y] = -1 #y의 왼쪽을 -1로 연결시켜
        
        else: #a > x > b, a < x < b 형태인 경우
            
            a = left[x]
            b = right[x] #a > x > b

            del right[x]
            del left[x]
            
            #x의 연결을 삭제하고 a > b, a < b로 연결
            right[a] = b
            left[b] = a

#head를 찾는 과정
#왼쪽이 -1인 원소가 head이다
for k,v in left.items():
    
    if v == -1:
        
        break

A = [k] #head부터 시작해서, 오른쪽이 -1인 원소(꼬리)를 찾을때까지 반복

while 1:
    
    k = right[k]

    if k == -1:
        
        break
    
    A.append(k)

print(*A)