[알고리즘_카카오] 표 편집_연결 리스트

[알고리즘_카카오] 표 편집_연결 리스트

 

이 문제는 linked list로 풀 수 있는 문제이다.

처음에는 dictionary로 풀려고 했는데 실패했다.

 

 

첫 번째 풀이 - 실패

구현 끝 단계까지 다 한다고 했는데, 결국 dic는 순서가 없어 dict에서 index로 검색하는 것이 불가능해 실패했다..

뒤 늦게 깨달아 버렸다..

 

 

def solution(n, k, cmd):
    answer = ''
    dict = {}
    stack = []
    for z in range(n):
        dict[z] = 1
    
    for x in cmd:
        print(x, k, dict)
        if len(x) == 1:
            if x == "C": # 제거인 경우    
                if k == len(dict)-1:
                    dict.pop(k)
                    stack.append(k) # 딕셔너리에서 k번째를 뺴주고 그 값을 stack에 넣음
                    k -= 1
                else:
                    dict.pop(k)
                    stack.append(k) # 딕셔너리에서 k번째를 뺴주고 그 값을 stack에 넣음 
            else: # x == "Z", 되돌릴 경우
                dict[stack.pop()] = 1 # stack에서 나온 값을 dict에 넣어주며 value는 0으로 다르게
        else:
            if x[0] == "U":
                k -= int(x[2])
            else: # x[0] == "D"
                k += int(x[2])
    
    for m in range(n):
        if m in dict.keys():
            answer += 'O'
        else:
            answer += 'X'
    return answer

 

두 번째 풀이

 

링크드 리스트를 파이썬으로 구현해내니 뭔가 새롭네.. C언어로 구현할 땐 넘나 고통스러웠는데

 

def solution(n, k, cmd):
    answer = ''
    
    linked_list = {i: [i-1,i+1] for i in range(1, n+1)}
    OX = ["O"] * (n+1)
    stack = []
    
    k += 1 # idx를 하나 올려줌
    
    for c in cmd:
        if c[0] == "U":
            for _ in range(int(c[2:])):
                k = linked_list[k][0]
        elif c[0] == "D":
            for _ in range(int(c[2:])):
                k = linked_list[k][1]
        elif c[0] == "C":
            prev, next = linked_list[k]
            stack.append([prev,next,k])
            OX[k] = "X"
            
            # 제일 마지막 여부 k 처리
            if next == n+1:
                k = prev
            else:
                k = next
            # 제거 후 앞 뒤로 연결
            if prev == 0:
                linked_list[next][0] = 0
            elif next == n+1:
                linked_list[prev][1] = n+1
            else: 
                linked_list[prev][1] = next
                linked_list[next][0] = prev
                
        elif c[0] == "Z":
            prev, next, now = stack.pop()
            OX[now] = 'O'
            
            if prev == 0:
                linked_list[next][0] = now
            elif next == n+1:
                linked_list[prev][1] = now
            else:
                linked_list[prev][1] = now
                linked_list[next][0] = now
    # print(OX)
    return "".join(OX[1:])