[Programmers] 표 편집 (파이썬, Python)

https://pixabay.com/ko/photos/꽃-식물-선셋-노란-꽃-6339436/

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

코딩테스트 연습 - 표 편집

해당 문제는 Programemrs의 2021 카카오 채용연계형 인턴십 문제집에 속해 있는 문제입니다.

 

문제에는 총 4가지의 명령어가 존재하며, 입력으로 주어진 명령어를 차례로 모두 수행한 후 남아 있는 행과 삭제된 행을 출력하는 것이 이 문제의 목표입니다.

 

해당 문제는 정확성 테스트와 효율성 테스트가 따로 진행되며 두 테스트 모두 통과를 해야 정답으로 인정이 되는 문제입니다.

 

정확성 테스트는 문제에 주어진 조건대로 실수 없이 구현을 하면 통과가 됩니다.

효율성 테스트는 배열(리스트)를 이용하면 통과를 할 수 없지만 LinkedList(연결 리스트)를 사용하면 통과할 수 있습니다.

 

저는 이 문제를 처음 풀때 효율성 테스트를 통과하지 못하고 kakao tech blog의 문제 해설을 본 후 아이디어를 얻어 문제를 해결했습니다.

해설 링크는 아래와 같습니다.

https://tech.kakao.com/2021/07/08/2021-카카오-인턴십-for-tech-developers-코딩-테스트-해설/

 

제 코드는 굉장히 길고 지저분한 부분이 있으니 흐름 위주로 보시는 게 좋을 거 같습니다🥲

전체 코드는 아래와 같습니다.

전체 코드

- 실패한 코드 (효율성 테스트 8번 케이스 실패)

def solution(n, k, cmd):
    answer = ''
    
    check_list = ["O"] * n
    del_stack = []
    last_idx = n-1
    moving_cnt = 0
    cur_idx = k
    
    for e in cmd:
        if e.startswith("U"):
            _, X = e.split()
            X = int(X)
            moving_cnt -= X
        
        elif e.startswith("D"):
            _, X = e.split()
            X = int(X)
            moving_cnt += X
        
        elif e.startswith("C"):
            if moving_cnt > 0:
                for i in range(cur_idx+1, n):
                    if check_list[i] == "O":
                        moving_cnt -= 1
                    
                    if moving_cnt == 0:
                        cur_idx = i
                        break
                
            elif moving_cnt < 0:
                moving_cnt = moving_cnt * -1
                for i in range(cur_idx-1, -1, -1):
                    if check_list[i] == "O":
                        moving_cnt -= 1
                    
                    if moving_cnt == 0:
                        cur_idx = i
                        break
                    
            check_list[cur_idx] = "X"
            del_stack.append(cur_idx)
            
            if cur_idx == last_idx:
                for i in range(cur_idx-1, -1, -1):
                    if check_list[i] == "O":
                        cur_idx = i
                        last_idx = i
                        break
                
            else:
                for i in range(cur_idx+1, n):
                    if check_list[i] == "O":
                        cur_idx = i
                        break
                
        else:
            if moving_cnt > 0:
                for i in range(cur_idx+1, n):
                    if check_list[i] == "O":
                        moving_cnt -= 1
                    
                    if moving_cnt == 0:
                        cur_idx = i
                        break
                
            elif moving_cnt < 0:
                moving_cnt = moving_cnt * -1
                for i in range(cur_idx-1, -1, -1):
                    if check_list[i] == "O":
                        moving_cnt -= 1
                    
                    if moving_cnt == 0:
                        cur_idx = i
                        break
                        
            recovery_idx = del_stack.pop()
            check_list[recovery_idx] = "O"
            
            if recovery_idx > last_idx:
                last_idx = recovery_idx
                
    
    answer = "".join(check_list)
    
    return answer

 

- 성공한 코드

def solution(n, k, cmd):
    answer = ''
    
    check_list = [ [i-1, i+1] for i in range(n) ]
    check_list[n-1][1] = -1
    answer_list = ["O"] * n
    
    del_stack = []
    moving_cnt = 0
    cur_idx = k
    
    for e in cmd:
        if e.startswith("U"):
            _, X = e.split()
            X = int(X)
            moving_cnt -= X
        
        elif e.startswith("D"):
            _, X = e.split()
            X = int(X)
            moving_cnt += X
        
        elif e.startswith("C"):
            while moving_cnt != 0:
                prev_pos, next_pos = check_list[cur_idx]
                
                if moving_cnt > 0 :
                    cur_idx = next_pos
                    moving_cnt -= 1
                else:
                    cur_idx = prev_pos
                    moving_cnt += 1
                    
            answer_list[cur_idx] = "X"
            del_stack.append(cur_idx)
            prev_pos, next_pos = check_list[cur_idx]
            
            if next_pos == -1:
                check_list[prev_pos][1] = -1
                cur_idx = prev_pos
                
            else:
                if prev_pos == -1:
                    check_list[next_pos][0] = -1
                    
                else:
                    check_list[prev_pos][1] = next_pos
                    check_list[next_pos][0] = prev_pos
                
                cur_idx = next_pos
            
                
        else:
            while moving_cnt != 0:
                prev_pos, next_pos = check_list[cur_idx]
                
                if moving_cnt > 0 :
                    cur_idx = next_pos
                    moving_cnt -= 1
                else:
                    cur_idx = prev_pos
                    moving_cnt += 1
            
            recovery_idx = del_stack.pop()
            answer_list[recovery_idx] = "O"
            
            prev_pos, next_pos = check_list[recovery_idx]
            
            if next_pos == -1:
                check_list[prev_pos][1] = recovery_idx
                
            elif prev_pos == -1:
                check_list[next_pos][0] = recovery_idx
                
            else:
                check_list[prev_pos][1] = recovery_idx
                check_list[next_pos][0] = recovery_idx
                
            
    answer = "".join(answer_list)
    
    return answer

 

추가 정리

문제의 조건에 효율성 테스트가 있거나, 입력 값의 범위가 너무 커서 시간 초과가 우려될 때

단순 배열로 순회 및 탐색하는 방법보다는 LinkedList 또는 Binary Search를 상황에 따라 고려해서 사용하면 좋을 거 같습니다.

 

---

읽어 주셔서 감사합니다 :)

잘못된 부분이 있다면 댓글로 편히 알려주세요😊