처음 코드

def solution(n, k, cmds):
    stack=[]
    for cmd in cmds:
        if cmd[0]=="U":
            count=int(cmd.split()[1])
            while count>0:
                k-=1
                if k not in stack:
                    count-=1
        elif cmd[0]=="D":
            count=int(cmd.split()[1])
            while count>0:
                k+=1
                if k not in stack:
                    count-=1
        elif cmd[0]=="C":
            # 삭제
            stack.append(k)  
            # 삭제한 후 바로 아래 행 선택
            while k in stack: # is not 이랑 not in이랑 계속 헷갈림!
                k+=1
            # 근데 그 아래행이 범위를 벗어났음 => 그러면 쭈욱 위로 올리셈
            if k==n:
                k-=1
                while k in stack:
                    k-=1
            
        elif cmd[0]=="Z":
            stack.pop()
            
                    
    # 현재 stack에는 삭제된 행의 번호만 있음
    
    answer = ""
    for idx in range(n):
        if idx in stack:
            answer+="X"
        else:
            answer+="O"
    return answer

먼저, is not이랑 not in을 헷갈려서 시간 많이 소비

그리고 stack에 없는거를 찾아야하는데 stack에 있는거로 조건 달아서 틀림

⇒ 이건 뭐 논리적으로 잡을 수 있었더거 같음.

근데 시간 초과가 남

200,000 * 1e6 = 2e11 이라 시간초과 날거를 예상했어야함.

개선가능한 이유 : 아래 코드가 선형탐색이라 O(N)임 → O(1)으로 개선가능

선형탐색 → 연결리스트

while k in stack: 
      k+=1

모범 코드 :

def solution(N, K, cmds):
    
    prev=[idx-1 for idx in range(N)]
    next=[idx+1 for idx in range(N)]
    next[N-1]=-1
    
    removed=[]
    cur=K
    
    for cmd in cmds:
        if cmd[0]=="U":
            x=int(cmd.split()[1])
            for _ in range(x):
                cur=prev[cur]
        elif cmd[0]=="D":
            x=int(cmd.split()[1])
            for _ in range(x):
                cur=next[cur]
        elif cmd[0]=="C":
            removed.append((prev[cur],cur,next[cur]))
            
            if prev[cur]!=-1:
                next[prev[cur]]=next[cur]
            if next[cur]!=-1:
                prev[next[cur]]=prev[cur]
                
            if next[cur]!=-1:
                cur=next[cur]
            else:
                cur=prev[cur]
    
        elif cmd[0]=="Z":
            p,c,n=removed.pop()
            if p!=-1:
                next[p]=c
            if n!=-1:
                prev[n]=c
            
    
    answer = ['O']*N
    for _,c,_ in removed:
        answer[c]="X"
    return "".join(answer)