Level 3 표 편집 <2021 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/81303?language=python3 

코딩테스트 연습 - 표 편집

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_표편집.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(n, k, cmd):
    check = ['O']*n
    linked_list = {i:[i-1, i+1] for i in range(n)}
    stack = []
    cursor = k
    for command in cmd:
        if command[0] == 'U':
            x = int(command.split(" ")[1])
            for _ in range(x):
                cursor = linked_list[cursor][0]
            
        elif command[0] == 'D':
            x = int(command.split(" ")[1])
            for _ in range(x):
                cursor = linked_list[cursor][1]
                
        elif command[0] == 'C':
            prev, next = linked_list[cursor][0], linked_list[cursor][1]
            check[cursor] = 'X'
            stack.append([prev, next, cursor])
            if prev == -1:
                linked_list[next][0] = prev
                cursor = next
            elif next == n:
                linked_list[prev][1] = next
                cursor = prev
            else:
                linked_list[prev][1] = next
                linked_list[next][0] = prev
                cursor = next
            
        elif command[0] == 'Z':
            prev, next, idx = stack.pop()
            check[idx] = 'O'
            linked_list[idx][0] = prev
            linked_list[idx][1] = next
            if prev == -1:
                linked_list[next][0] = idx
            elif next == n:
                linked_list[prev][1] = idx
            else:
                linked_list[prev][1] = idx
                linked_list[next][0] = idx
            
    return "".join(check)

---

풀이 과정

U, D, C 명령을 할 때 시간복잡도를 고려해줘야 한다.

한 칸씩 행을 탐색하면서 삭제된 행인지 아닌지 고려해주려면 최대 X+삭제된 행의 수만큼 시간이 소요되고 시간초과가 나기 마련이다.

따라서, X번만 탐색하기 위해서 연결 리스트를 사용해야 한다.

2021 카카오 인턴십 코딩테스트 해설을 보면 연결 리스트 사용에 관한 힌트를 얻을 수 있다.

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

2021 카카오 인턴십 for Tech developers 코딩 테스트 해설

 

행을 삭제할 때 next와 prev를 끊어주고 다시 연결해줌으로써 U, D를 수행할 때 연결된 리스트를 따라 X번만 탐색하면 된다.

행을 되돌리기 할 때에도 next와 prev만 다시 연결해주면 된다.

def solution(n, k, cmd):
	#check[i] = i번 행이 존재한다면 O, 삭제되었다면 X
    check = ['O']*n
    
    #linked_list[i] = [prev, next] i번 행의 이전 행 번호 = prev, i행의 다음 행 번호 = next
    linked_list = {i:[i-1, i+1] for i in range(n)}
    
    #삭제된 행의 [prev, next, 행 번호]를 담는 스택
    stack = []
    
    #현재 선택된 행 번호
    cursor = k
    
    for command in cmd:
    	#위로 X칸 이동
        if command[0] == 'U':
            x = int(command.split(" ")[1])
            
            #현재 선택된 행을 시작으로 연결된 prev 행을 따라 X번 이동해서 cursor 값을 갱신한다
            for _ in range(x):
                cursor = linked_list[cursor][0]
        
        #아래로 X칸 이동
        elif command[0] == 'D':
            x = int(command.split(" ")[1])
            
            #현재 선택된 행을 시작으로 연결된 next 행을 따라 X번 이동해서 cursor 값을 갱신한다
            for _ in range(x):
                cursor = linked_list[cursor][1]
        
        #현재 선택된 행 삭제
        elif command[0] == 'C':
        	#현재 선택된 행의 이전 행 번호 prev, 다음 행 번호 next
            prev, next = linked_list[cursor][0], linked_list[cursor][1]
            
            #현재 선택된 행을 삭제 처리 한다
            check[cursor] = 'X'
            
            #prev와 next, 삭제된 행 번호를 stack의 top에 push
            stack.append([prev, next, cursor])
            
            #현재 삭제된 행이 가장 첫 행인 경우,
            if prev == -1:
            	#현재 삭제된 행의 다음 행이 가장 첫 행이 된다
                linked_list[next][0] = prev
                #cursor를 현재 삭제된 행의 다음 행 번호로 갱신한다
                cursor = next
                
            #현재 삭제된 행이 가장 마지막 행인 경우,
            elif next == n:
            	#현재 삭제된 행의 이전 행이 가장 마지막 행이 된다
                linked_list[prev][1] = next
                #cursor를 현재 삭제된 행의 이전 행 번호로 갱신한다
                cursor = prev
                
            #현재 삭제된 행이 중간에 있는 행인 경우,
            else:
            	#현재 삭제된 행의 이전 행을 현재 삭제된 행의 다음 행과 연결해준다
                linked_list[prev][1] = next
                #현재 삭제된 행의 다음 행을 현재 삭제된 행의 이전 행과 연결해준다
                linked_list[next][0] = prev
                #cursor를 현재 삭제된 행의 다음 행 번호로 갱신한다
                cursor = next
                
        #가장 마지막에 삭제한 행 되돌리기    
        elif command[0] == 'Z':
        	#가장 마지막에 삭제한 행의 정보를 가져온다
            prev, next, idx = stack.pop()
			
            #idx 행을 되돌린다
            check[idx] = 'O'
            #idx 행의 이전 행 번호는 prev, 다음 행 번호는 next로 연결해준다
            linked_list[idx][0] = prev
            linked_list[idx][1] = next
            
            #되돌린 행이 첫 행인 경우,
            if prev == -1:
            	#다음 행의 이전 행 번호를 되돌린 행으로 연결해준다
                linked_list[next][0] = idx
                
            #되돌린 행이 맨 마지막 행인 경우,
            elif next == n:
            	#이전 행의 다음 행 번호를 되돌린 행으로 연결해준다
                linked_list[prev][1] = idx
                
            #되돌린 행이 중간에 있는 행인 경우,
            else:
            	#이전 행의 다음 행 번호를 되돌린 행으로 연결해준다
                linked_list[prev][1] = idx
                #다음 행의 이전 행 번호를 되돌린 행으로 연결해준다
                linked_list[next][0] = idx
            
    return "".join(check)
    
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

오답 노트

풀이 시간 1시간 37분

 2021 카카오 인턴십에 지원했었고 코테를 볼 때 이 문제에서 정확성 1개의 테스트케이스가 틀려서 오류를 찾다가 아쉽게 시험이 끝났었다. 시험이 끝나고도 어느 부분이 틀렸을까 하고 계속 고민하다가 결국 오류를 찾아서 고치는데 5분밖에 걸리지 않았고 그래서 너무 아쉬웠었다. 내 실력이 내가 봐도 애매했었고 코딩테스트 준비를 본격적으로 하기 이전이라 그럴 수 밖에 없었다.

막학기가 끝나면 본격적으로 제대로 공부를 하자고 다짐하며 팔을 걷어 올리는 계기가 되었다.

 

 3개월 정도 지난 지금 다시 문제를 풀어봤고, 1시간 37분동안 고민하면서 작성했던 코드는 아래와 같다.

결과는 정확성은 모두 맞았고, 효율성 반절이 틀렸다. 효율성에서 통과하지 못하는 이유는 예상했다.

U, D, C 명령의 시간복잡도는 O(n), Z 명령의 시간복잡도는 O(1)이며, 바깥 for문이 len(cmd)만큼 반복한다.

 즉, 최악의 경우 n = 1,000,000, len(cmd) = 200,000으로 200,000,000,000번의 연산이 소요되므로 제한시간 안에 통과할 수 없다

from collections import deque
def solution(n, k, cmd):
    stack = deque()
    visit = [1]*n
    cursor = k
    end = n-1
    for command in cmd:
        if command[0] == "U":
            x = int(command.split()[1])
            while x > 0:
                cursor -= 1
                if visit[cursor] == 1:
                    x -= 1
        elif command[0] == "D":
            x = int(command.split()[1])
            while x > 0:
                cursor += 1
                if visit[cursor] == 1:
                    x -= 1
        elif command[0] == "C":
            visit[cursor] = 0
            stack.append(cursor)
            if cursor == end:
                while not visit[cursor]:
                    cursor -= 1
                end = cursor
            else: 
                while not visit[cursor]:
                    cursor += 1
        elif command[0] == "Z":
            row = stack.pop()
            visit[row] = 1
            if row > end:
                end = row
    return "".join(list(map(str, visit))).replace('1','O').replace('0','X')

 

• 결과

 인턴십에 도전했을 때 이후로 자료구조와 알고리즘 공부를 1개월 반정도 공부했다. 이전에는 문제를 읽고 시간복잡도를 고려하여 알고리즘을 짜고, 적절한 자료구조를 선택하는 것에 미숙했는데 공부하면서 차츰 눈에 보이기 시작했다. 그러면서 코딩테스트 문제를 푸는 과정이 더 재밌어졌다. 그리고 공부를 하면 할 수록 부족한 부분이 계속해서 생겨난다. 그럴 때일수록 배우고 얻을 것이 더 많아졌다고 긍정적으로 생각하면서 재미있게 끝까지 공부하는 마음자세로 노력해야겠다! 화이팅

 

---

참고

• 1. 숫자 문자열과 영단어 ->  2021.08.20 - [코테 노트/프로그래머스] - Level 1 숫자 문자열과 영단어<2021 카카오 인턴십> Python 3

Level 1 숫자 문자열과 영단어<2021 카카오 인턴십> Python 3

• 2. 거리 두기 확인하기 -> https://hwayomingdlog.tistory.com/146

Level 2 거리두기 확인하기 <2021 카카오 인턴십> Python 3

• 4. 미로 탈출
• 5. 시험장 나누기