[프로그래머스]표 편집

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 표의 갯수가 백만 개 이하이므로 연결리스트를 구현한다.

2. cmd가 C일 때는 해당 표를 삭제해야하므로 해당 표가 맨 아래인지 구분한다. 맨 아래라면 커서를 위로 이동하고 그렇지 않다면 커서를 아래로 이동한 후에 head와 tail인지를 구분하고 연결리스트를 변경한다. 그리고 삭제한 표를 stack에 담아준다.

3. cmd가 Z일 때는 stack.pop()을 이용하여 최근에 삭제된 표를 알아낸다. C일 때와 마찬가지로, head인지 tail인지를 구분하고 연결리스트를 다시 이어준다.

4. cmd가 U와 D일 때는 연결리스트를 통해 지정된 횟수만큼 이동한다.

 

def solution(n, k, cmd):
    answer = ['O']*n #answer의 초기값이다. 삭제를 한다면 해당 표는 'X'로 바꿔준다.
    cur = k #현재 어떤 표인지를 나타내는 커서값이다.
    table = {i:[i-1, i+1] for i in range(n)} #1번
    table[0] = [None, 1] #Head
    table[n-1] = [n-2, None] #Tail
    stack = [] #삭제되는 표가 담기는 리스트이다.
    
    for i in cmd:
        if i == 'C': #2번
            prev, next = table[cur]
            stack.append([prev, cur, next]) #삭제한 표를 담아준다.
            answer[cur] = 'X' #삭제하였으므로 answer 값을 변경한다.
            if next == None: #해당 표가 가장 아래에 있어서 커서를 한 칸 올려줘야할 때이다.
                cur = prev
            else:
                cur = next
                
            if prev == None: #Head일 때
                table[next][0] = None
            elif next == None: #Tail일 때
                table[prev][1] = None
            else: #나머지의 경우
                table[next][0] = prev
                table[prev][1] = next

        elif i == 'Z': #3번
            prev, now, next = stack.pop()
            answer[now] = 'O' #삭제한 것을 복귀하였으므로 answer 값을 변경한다.
            if prev == None: #Head일 때
                table[next][0] = now
            elif next == None: #Tail일 때
                table[prev][1] = now
            else: #나머지의 경우
                table[next][0] = now
                table[prev][1] = now

        else: #4번
            i1, i2 = i.split(' ')
            i2 = int(i2)
            if i1 == 'D':
                for _ in range(i2):
                    cur = table[cur][1]
            else:
                for _ in range(i2):
                    cur = table[cur][0]

### 4번 코드를 다음과 같이 작성하면 에러가 발생한다. 이유는 잘 모르겠다 ㅠㅠ
#		else:
#            if i[0] == 'D': 이건 왜 안되지 ??
#                for _ in range(int(i[2])):
#                    cur = table[cur][1]
#            else:
#                for _ in range(int(i[2])):
#                    cur = table[cur][0]
###
            
    return ''.join(answer)

 

파이썬으로 연결리스트를 구현하는 것은 처음이었기에 다른 블로그를 많이 참고하였다.

특이하게 딕셔너리를 사용하여 연결리스트를 구현한다는 것이 매우 매력적이었던 것 같다.

초기에 코드를 작성할 때는 시간복잡도를 고려하여 이중 for문을 사용하지 않고 아래와 같이 작성하였는데, sort()하는 부분이나 pop()을 할 때, 생각보다 많은 작업이 소요된 것 같다.

하지만 이번 문제를 통해 파이썬으로 연결리스트를 구현하는 개념을 완벽하게 터득한 것 같아서 매우 뿌듯하다.

 

#초기 작성 코드
def solution(n, k, cmd):
    answer = ''
    friends = [i for i in range(n)]
    index = k
    history = []
    for i in range(len(cmd)):
        if cmd[i][0] == 'D':
            index += int(cmd[i][2])
        elif cmd[i][0] == 'U':
            index -= int(cmd[i][2])
        elif cmd[i][0] == 'C':
            history.append(friends.pop(index))
            if index == len(friends)+1:
                index -= 1
        elif cmd[i][0] == 'Z':
            friends.append(history.pop())
            friends.sort()
    check = {}
    for i in range(n):
        check[i] = 0
    for i in friends:
        check[i] += 1
    for i in check.values():
        if i == 1:
            answer += 'O'
        else:
            answer += 'X'
    return answer