[프로그래머스] 표 편집 (Python) - Linked List

2023. 3. 2. 18:16·Algorithm (PS)
목차
  1. 문제상황 (시간 초과)
  2.  
  3. 해결방법 
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/81303

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

오랜만에 자료구조형에 대해 생각해 볼 수 있는 문제를 풀었당

 

문제상황 (시간 초과)

맨 첨에는 list 만들고 삭제하면 0 , 데이터 있는 값은 1 이렇게 테이블을 만들어주었다. 

그러나 list 로 테이블을 관리하게 되면.. Z 복구 연산의 경우 0 -> 1로 바꿔주는거니 O(1) 이지만, 

행들을 순차적으로 탐색해야 하는 U, D, C 연산의 경우 시간복잡도에서 걸린다. 

최대 cmd 가 200000개이고, 예를들어 선형 탐색 O(N)을 하는 U,D,C 연산만 수행하며, 테이블 행 길이가 최대 1000000 이면 연산량이 크다 (그리고 문제에서 효율성 점수가 있다고 언급했다 )

 

해결방법 

자료구조형을 연결리스트로 구현할 수 있다. 중간 중간 테이블의 데이터가 삭제되어서 칸의 이동을 해주어야 하는 경우, link로 previous node, next node를 이을 수 있다.

U, D, C연산의 시간복잡도는 O(X) 까지 줄일 수 있으며, Z 연산의 경우 O(1)에 해결할 수 있다...! 

* X 는 커서가 이동하는 노드 수이다. 리스트 자료구조는 모든 원소를 하나씩 거쳐가야 하지만, 링크드리스트는 유효한 행 (노드)들만 거쳐갈 수 있다. 

 

def solution(n, k, cmd):
    answer = ['O']*n
    
    table = {i : [i-1, i+1] for i in range(n)} # 행번호 : [prev, next]
    table[0][0] = None
    table[n-1][1] = None 
    
    buffer = []
    
    for c in cmd:
        cmd_list = c.split(' ')
        if cmd_list[0] == 'U': # up 이므로 prev <-
            m = int(cmd_list[1])
            for i in range(m): # next 만큼 이동하기 
                k = table[k][0]
                
        elif cmd_list[0] == 'D': # down 이므로 next ->
            m = int(cmd_list[1])
            for i in range(m):
                k = table[k][1]
                
        elif cmd_list[0] == 'C':
            answer[k] = 'X'
            prev, next = table[k]
            buffer.append([prev, k, next])
            
            # k 처리하기 
            if next == None:
                k = prev
            else:
                k = next
            
            # 연결해제하기 
            if prev == None: # 맨 앞 노드였음
                table[next][0] = None 
                
            elif next == None: # 맨 끝 노드
                table[prev][1] = None 
                
            else: # 일반적인 노드 
                table[next][0] = prev
                table[prev][1] = next
                
            
        else: # Z 복구 
            prev, now, next = buffer.pop()
            answer[now] = 'O' # 복구하기
            if prev == None: # now 가 맨 첫번재 노드 
                table[next][0] = now # next 값만 처리해주면 된다. 
            elif next == None:# now가 맨 마지막 노드
                table[prev][1] = now 
            else:    
                table[next][0] = now # next 의 prev는 now
                table[prev][1] = now # prev 의 next는 now 
    
    return "".join(answer)
728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 1956번: 운동 Python (플로이드-워셜)  (0) 2023.03.04
[프로그래머스] 경주로 건설 (DFS+DP) Python + 히든케이스 정리  (1) 2023.03.04
[백준] 1987번: 알파벳 Python - DFS/Backtracking  (0) 2023.02.28
[백준] 3584번: 가장 가까운 공통 조상 (Python/파이썬) - tree 문제  (0) 2023.02.27
[백준] 17141 연구소 2 Python  (0) 2023.02.27
  1. 문제상황 (시간 초과)
  2.  
  3. 해결방법 
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 1956번: 운동 Python (플로이드-워셜)
  • [프로그래머스] 경주로 건설 (DFS+DP) Python + 히든케이스 정리
  • [백준] 1987번: 알파벳 Python - DFS/Backtracking
  • [백준] 3584번: 가장 가까운 공통 조상 (Python/파이썬) - tree 문제
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • Leetcode
  • 데이터엔지니어
  • 카카오코딩테스트
  • python
  • Swift
  • EC2
  • 리눅스
  • dfs
  • AWS
  • 쿠버네티스
  • dp
  • ansible
  • 클라우드
  • BFS
  • 운영체제
  • 빅데이터
  • 백준
  • 데이터브릭스
  • 데이터엔지니어링
  • linux
  • docker
  • Kubernetes
  • Databricks
  • 스파크
  • 코딩테스트
  • 파이썬
  • SPARK
  • 백트래킹
  • 프로그래머스
  • 알고리즘

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[프로그래머스] 표 편집 (Python) - Linked List
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.