프로그래머스 - 표편집 파이썬

문제 

프로그래머스

 

문제설명(내용 이해 어렵지 않음 구현하기가 어려울 뿐)

한 줄 정리: 명령어 기반 표의 행을 선택, 삭제, 복구하는 프로그램 작성 후, 삭제되지 않은 행 '0', 삭제된 것 'x'로 표시, return 

n = 처음 표의 행 개수 

k = 처음 선택된 행의 위치

cmd = 수행한 명령어들이 담긴 문자열 배열 

파란색은 현재 선택된 행을 의미한다(한 번에 한 행만 선택 가능)

 

명령어 정리 

'U X'	현재 선택된 행에서 x칸 위에 있는 행 선택
'D X'	현재 선택된 행에서 x칸 아래에 있는 행 선택
'C'	현재 선택된 행 삭제, 바로 아래 행 선택(전자가 마지막이면 바로 윗 행 선택)
'Z'	가장 최근 삭제된 행 복구

 

예시 

오른쪽 사진이 'D 2'를 한 상태이다(2만큼 아래의 행을 선택) 

왼쪽을 'c'한 상태가 오른쪽 사진

'C'한 상태(기존의 프로도가 없어지고 네오가 올라옴) 

'U 3'

'U 3'를 수행한 상태(위로 3행 올라옴)

'c'를 한 상태

'C'를 한 상태(기존에 선택된 행이 없어지고, (지금 상황에서는) 아래가 하나씩 올라옴)

'D 4'를 한 상태

'D 4' 4만큼 아래의 행을 선택한 상태 

'C'를 한 상태

'C'를 한 상태, 아래의 선택된 행을 없앰 

'U 2'를 한 상태

좌(1,2): 'Z'한 상태 / 우(3,4): 가장 최근에 사라졌던 라이언 행 사진 

'Z'를 한 상태 

좌(1,2): 콘의 부활 / 우(3,4): 사라졌던 콘

'Z'를 한 상태 

모든 명령어를 끝내고 비교해 보면 '프로도'가 삭제되었음을 확인할 수 있고, 'OX'를 채워 넣을 수 있다 

그래서 여기서 result 값은 '0000X000'이 된다 

 

제한사항 

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

 

아이디어 

1. 시간복잡도 

U, D, C는 최악의 경우 O(n)이 소요 

Z는 해당인덱스를 찾고 바꾸는 것이라 O(1) 소요 

 

1-2. 왜 3단계 문제인가 

다른 명령어보다 'Z'가 까다로움 

제거할 당시 어떤 값이 어디에 있었는지 같이 저장해야 하는 점이 까다로움 

 

2. 그래서 어떤 개념이 필요 

양방향 연결 리스트 사용 or 이진 검색 트리 

 

3. 왜? 

- 커서가 돌아다니면서 중간에 삭제를 하는 형태이므로 양방향 연결 리스트가 필요함을 유추 

  비슷한 문제 추천 

1406번: 에디터

5397번: 키로거

 

4. 어떻게 구현 

- 파이썬에서는 직접 연결 리스트를 구현해야 함 / 클래스 or dict자료구조를 이용하여 구현 

key의 값: 열 번호, value 값: [prev 열, next열]로 지정

 

연결리스트 통과 코드 

def solution(n, k, cmd):
    cur = k  # 현재 커서 위치
    deleted = []  # 삭제된 원소들을 저장하는 리스트
    table = {i: [i - 1, i + 1] for i in range(n)}  # 인덱스 간의 연결 정보를 저장하는 딕셔너리
    answer = ['O'] * n  # 원소 상태를 저장하는 리스트

    for c in cmd:
        if c[0] == "C":  # 삭제
            deleted.append([cur, answer[cur]])  # 삭제된 원소의 위치와 상태를 저장
            answer[cur] = 'X'  # 원소 상태를 'X'로 변경
            prev, nxt = table[cur]  # 이전 원소와 다음 원소의 인덱스
            if prev != -1:
                table[prev][1] = nxt  # 이전 원소의 다음 원소를 다음 원소로 변경
            if nxt != n:
                table[nxt][0] = prev  # 다음 원소의 이전 원소를 이전 원소로 변경
            if nxt == n:
                cur = prev  # 마지막 원소를 삭제한 경우, 커서를 이전 원소로 이동
            else:
                cur = nxt  # 다음 원소를 삭제한 경우, 커서를 다음 원소로 이동

        elif c[0] == "Z":  # 복구
            restore, status = deleted.pop()  # 삭제된 원소를 꺼내와서 위치와 상태를 복구
            answer[restore] = status  # 원소 상태를 복구
            prev, nxt = table[restore]  # 이전 원소와 다음 원소의 인덱스
            if prev != -1:
                table[prev][1] = restore  # 이전 원소의 다음 원소를 복구된 원소로 변경
            if nxt != n:
                table[nxt][0] = restore  # 다음 원소의 이전 원소를 복구된 원소로 변경

        else:  # 커서 이동
            direction, count = c.split(' ')
            count = int(count)
            if direction == 'D':  # 아래로 이동
                for _ in range(count):
                    cur = table[cur][1]  # 다음 원소로 커서 이동
            else:  # 위로 이동
                for _ in range(count):
                    cur = table[cur][0]  # 이전 원소로 커서 이동

    return ''.join(answer)  # 결과 반환

 

해당 코드의 시간복잡도 

U X	O(X)
D X	O(X)
C	O(1)
Z	O(1)

 

ref 

https://blog.encrypted.gg/1001