프로그래머스 표 편집 (카카오 기출, with Python)

내가 생각한 Solution

문제에서 생각해볼 점

• 총 2가지 방법으로 구현해보고자 합니다. (효율성 테스트 때문에)

• 풀이 1

  • 그냥 문제에서 주어진대로 풀었습니다.

  • 배열을 생성했습니다.

  • 행을 탐색할 때 삭제한 원소는 카운트 없이 넘어갑니다.

    • ex)

    • [O, O, O, X, O, X, O] 라는 배열이 있고 현재 선택된 index 가 0이라고 합니다.

    • D 4 라는 cmd 가 주어졌다면, 가르켜야 하는 index 는 6이 됩니다.

• 풀이 2

  • 풀이 1은 효율성을 절반밖에 못맞춥니다.

  • 그래서 linked list 를 활용하여 직접 구현해보고자 했습니다.

    • 아이디어는 요기서 얻게되었고, 'linked list 활용'이라는 글자만 보고 직접 구현했습니다.

  • 이게 얼마나 빠를까 의문이었는데, 실제로 많이 빠른가 봅니다. (앞으로 문제를 풀때 linked list 도 잘 기억해놔야 겠습니다.)

  • linked list 의 개념은 어렵지 않으니 직접 구현해보시면 좋을 것 같습니다.

  • 코드에 주석을 최대한 달아놨으니 직접 코드 보면서 이해하시면 좋을 것 같습니다.

코드 구현

• 풀이 1

def solution(n, k, cmd):
    answer = ['O'] * n
    idx = k
    deleted = []
    
    for el in cmd:
    
        if el[0] == 'D':
            cnt = int(el.split()[1])
            for i in range(idx+1, n):
                if answer[i] == 'O':
                    cnt -= 1
                if cnt == 0:
                    idx = i
                    break
            
        elif el[0] == 'U':
            cnt = int(el.split()[1])
            for i in range(idx-1, -1, -1):
                if answer[i] == 'O':
                    cnt -= 1
                if cnt == 0:
                    idx = i
                    break
            
        elif el[0] == 'C':
            deleted.append(idx)
            answer[idx] = 'X'
            isFind = False
            # 삭제했을 때 현재 idx 뒤로 가르킬 원소가 존재한다면
            # 해당 원소를 가리킬 것
            for i in range(idx+1, n):
                if answer[i] == 'O':
                    isFind = True
                    idx = i
                    break
            # idx 뒤로는 가리킬 원소가 없다면 앞으로 찾아봐야 함
            if not isFind:
                for i in range(idx-1, -1, -1):
                    if answer[i] == 'O':
                        idx = i
                        break
                
        else:
            deleted_idx = deleted.pop()
            answer[deleted_idx] = 'O'

    return ''.join(answer)

• 풀이 2

def solution(n, k, cmd):
    answer = ['O'] * n
    
    arr = []
    del_elems = []
    
    # 링크드 리스트를 표현하는 배열 생성
    # 각 원소는 [내가 가리키는 원소, 나를 가리키는 원소] 구성으로 이루어집니다.
    for i in range(n):
        if i == 0:
            arr.append([None, i+1])
        elif i == n-1:
            arr.append([i-1, None])
        else:
            arr.append([i-1, i+1])
    
    # 명령어 수행 부분
    for each_cmd in cmd:
        
        if each_cmd[0] == 'D':
            cnt = int(each_cmd.split()[1])
            for i in range(cnt):
                k = arr[k][1]
        
        elif each_cmd[0] == 'U':
            cnt = int(each_cmd.split()[1])
            for i in range(cnt):
                k = arr[k][0]
        
        elif each_cmd[0] == 'C':
            # 맨 끝에 원소가 삭제되는 케이스
            del_elems.append([k, arr[k]])
            if arr[k][1] == None:
                pre_k = arr[k][0]
                arr[pre_k][1] = None
                k = pre_k
            # 맨 앞의 원소가 삭제되는 케이스
            elif arr[k][0] == None:
                next_k = arr[k][1]
                arr[next_k][0] = None
                k = next_k
            else:
                pre_k = arr[k][0]
                next_k = arr[k][1]
                
                arr[pre_k][1] = next_k
                arr[next_k][0] = pre_k
                
                k = next_k
        
        else:
            # 가장 최근 삭제된 index 와 정보 불러오기
            restore_k, info = del_elems.pop()
            pre_k = info[0]
            next_k = info[1]
            
            # 맨 앞의 원소가 복원되는 경우
            if pre_k == None:
                arr[next_k][0] = restore_k
            # 맨 뒤의 원소가 복원되는 경우
            elif next_k == None:
                arr[pre_k][1] = restore_k
            else:
                arr[pre_k][1] = restore_k
                arr[next_k][0] = restore_k
    
    # 삭제된 부분만 X 표시하고, 리스트를 문자열로 변환 후 반환
    for restore_k, info in del_elems:
        answer[restore_k] = 'X'
    
    return ''.join(answer)