2023.01.18 코딩 테스트 공부 기록 입니다.

프로그래머스 : 큰 수 만들기

🤡큰 수 만들기 (Lv.2)

🤑풀이

def solution(number, k):
    stack = []
    l = len(number)
    for num in number:
        if not stack:
            stack.append(num)
            continue
        if k > 0:
            while stack[-1] < num:
                stack.pop()
                k -= 1
                if not stack or k == 0:
                    break
        stack.append(num)
        
    stack = stack[:-k] if k > 0 else stack
    return ''.join(stack)

👩‍🏫 참고 코드

• 문제를 푸는테 테스트 코드 10번에서 시간 초과가 발생하였습니다. 여러 트릭들을 추가 했지만 시간 초과 문제가 개선되지 않아서 구글링을 통해 문제를 해결했습니다.(ㅜ..ㅜ)
• 저는 문자열 슬라이싱을 통해서 문제를 풀어나갔는데 그 부분에서 시간이 많이 소요되었습니다.
• 위 코드를 구조적으로 리뷰하여 다음에 비슷한 유형의 문제를 잘 풀 수 있도록 문제를 잘 흡수 하려고 합니다.

1. 문자열 슬라이싱은 시간 소요가 크다.

• 시간 초과를 유도하기 위해 인위적으로 늘린 문자열에 대한 처리는 문자열 슬라이싱으로 접근하는 것이 아니다.
• 보통 이런 문제는 stack, queue, index을 통해서 문제를 해결하는 것 같고 구조를 파악하여 적절한 자료구조를 선택하자.
• 자료 구조 안에 원소들이 FIFO, LIFO인지 고려하여 queue, stack을 선택해야 합니다. 이 문제는 stack을 선택하고 stack 안의 마지막 원소와 number에서 추출한 숫자 num과 비교합니다.

2. loop가 어디서, 몇번, 어떻게 도는지 생각하자

• 위 문제는 구조적으로 2번의 loop가 필요하다고 생각합니다. number 문자열에서 숫자 num를 하나씩 받아오는게 첫번째 loop이고, num과 number를 비교하는 것이 두번 째 loop입니다.

3. greedy 문제에서 "탐욕적으로 결정된 것"은 "결정된 후" 변하지 않는다는 것을 염두하자

• 위 문제는 greedy 문제로서 "탐욕적으로 결정된 것"은 "결정된 후" 변하지 않는다는 것을 염두해 두어야 합니다. 따라서, "탐욕적으로 마감시킬 수 있는 결정 조건"에 대해서 생각해야 합니다.

• 위 풀이의 접근은 number에서 num이 추출되고 while loop을 돌면 방금 고려한 num을 더이상 고려할 필요 없도록 조건을 만들었습니다.

• 위 조건이 없다면, number에 접근하는 index를 +1, -1 하면서 계속 위치를 수정해야 되는거 같습니다.

  • 비슷한 문제로는 투포인터 같은게 있을거 같습니다.

향후 문제 접근 방식

• 앞으로 비슷한 문제를 다음과 같이 접근하려고 합니다.

1. 인위적으로 시간초과를 유도하고 있는가 확인
2. 자료구조 선택. (FIFO, LIFO)
3. 최소 loop 수 추론 하기
4. 두번 째 loop가 종료 될때, 첫번 째 loop에서 추출한 원소는 더이상 고려할 필요 없이 로직 설계
5. 위 내용이 불가능 해 보이면 투 포인터(index 조절) 접근

Reference

Velog.soo5717 - 큰 수 만들기

프로그래머스 : 삼각 달팽이

🤡삼각 달팽이 (Lv.2)

🤑풀이

def down(row, col, now, n) :
    for _ in range(n) :
        lst[row][col] = now
        now += 1
        row += 1
    return row-1, col+1, now

def right(row, col, now, n) :
    for _ in range(n) :
        lst[row][col] = now
        now += 1
        col += 1
    return row-1, col-2, now

def diagonal(row, col, now, n) :
    for _ in range(n) :
        lst[row][col] = now
        now += 1
        row -= 1
        col -= 1
    return row+2, col+1, now

def solution(n) :
    global lst
    lst, max_num, now = [], 0, 1
    for i in range(1, n+1) :
        max_num += i
        lst.append([0 for _ in range(i)])
    row, col = 0, 0
    while now <= max_num :
        row, col, now = down(row, col, now, n)
        n -= 1
        if n == 0 or lst[row][col] != 0 :
            break
        row, col, now = right(row, col, now, n)
        n -= 1
        if lst[row][col] != 0 :
            break
        row, col, now = diagonal(row, col, now, n)
        n -= 1
        if lst[row][col] != 0 :
            break
    answer = []
    for ls in lst :
        answer.extend(ls)
        
    return answer

👩‍🏫 아이디어

1. 정삼각형을 직각 삼각형으로 생각하자

• n의 크기가 1000이하이기 때문에 문제의 조건대로 이동시키는 방식을 선택했습니다.
• 문제에서 정삼각형이 나올 때, 왼쪽 빗면을 직각으로 만들어서 직각 삼각형으로 생각하곤 합니다.
• 이렇게 접근하면, 2차원 리스트로 문제를 풀 수 있습니다.

2. 제시된 조건대로 위치를 이동시켜 구현하자

• 문제를 좀 단순화 하기 위해서 "시작점", "끝점", "이동 방향"을 "시작점", "이동 횟수", "이동 방향"으로 단순화 했습니다. 이렇게 되면 끝점을 계산할 필요가 없기 때문에 문제 설계의 난이도가 감소합니다.

프로그래머스 : 아이템 줍기

🤡아이템 줍기 (Lv.3)

🤑풀이

def get_board_matrix(rectangle) :
    max_x, max_y = 0, 0
    for box in rectangle :
        if box[2] > max_x :
            max_x = box[2]
        if box[3] > max_y :
            max_y = box[3]
    board = [[0 for _ in range(2*max_x)] for _ in range(2*max_y)]
    return board

def update_board_matrix(rectangle, board) :
    for box in rectangle :
        x_length = 2*(box[2] - box[0]) + 1
        y_length = 2*(box[3] - box[1]) + 1
        # fill bottom, up
        for i in range(x_length) :
            board[2*box[1]-1][2*box[0]-1+i] = 1     # bottom
            board[2*box[3]-1][2*box[0]-1+i] = 1     # up
        for i in range(y_length) :
            board[2*box[1]-1+i][2*box[0]-1] = 1     # right
            board[2*box[1]-1+i][2*box[2]-1] = 1        
    return board

# 현재 어떤 box의 side 정보를 출력
def get_start_info(rectangle, now_x, now_y) :
    start = {}
    # 각각의 사각형에서 이동 가능한 경로 생성 (Board 생성)   
    for idx, info in enumerate(rectangle) :
        x1, y1, x2, y2 = info[0], info[1], info[2], info[3]
        start[idx] = {'left'  : [[2*x1-1], [i for i in range(2*y1-1, 2*y2)]],
                      'right' : [[2*x2-1], [i for i in range(2*y1-1, 2*y2)]],
                      'up'    : [[i for i in range(2*x1-1, 2*x2)], [2*y2-1]],
                      'down'  : [[i for i in range(2*x1-1, 2*x2)], [2*y1-1]]
                     }
    now_info = []
    for box in start :
        for side in start[box] :
            if now_x in start[box][side][0] and now_y in start[box][side][1] :
                now_info.append((box, side))
    return now_info

# '0' : left, '1' : right, '2' : up, '3' : down
def go_line(start_info, now_x, now_y) :
    if start_info[0][1] == 'left' :
        next_x, next_y = now_x, now_y+1
    elif start_info[0][1] == 'right' :
        next_x, next_y = now_x, now_y-1
    elif start_info[0][1] == 'up' :
        next_x, next_y = now_x+1, now_y
    elif start_info[0][1] == 'down' :
        next_x, next_y = now_x-1, now_y         
    return next_x, next_y

# 같은 박스 내에서 꺽는 이동
def change_direction(start_info, now_x, now_y) :
    if start_info[0][1] in ['left', 'up'] and start_info[1][1] in ['left', 'up'] :
        next_x, next_y = now_x+1, now_y
    if start_info[0][1] in ['right', 'up'] and start_info[1][1] in ['right', 'up'] :
        next_x, next_y = now_x, now_y-1
    if start_info[0][1] in ['left', 'down'] and start_info[1][1] in ['left', 'down'] :
        next_x, next_y = now_x, now_y+1
    if start_info[0][1] in ['right', 'down'] and start_info[1][1] in ['right', 'down'] :
        next_x, next_y = now_x-1, now_y
    return next_x, next_y


def move_to_other_box(start_info, now_x, now_y) :
    if start_info[0][1] in ['left', 'down'] and start_info[1][1] in ['left', 'down'] :
        next_x, next_y = now_x-1, now_y
    if start_info[0][1] in ['left', 'up'] and start_info[1][1] in ['left', 'up'] :
        next_x, next_y = now_x, now_y+1
    if start_info[0][1] in ['right', 'up'] and start_info[1][1] in ['right', 'up'] :
        next_x, next_y = now_x+1, now_y
    if start_info[0][1] in ['right', 'down'] and start_info[1][1] in ['right', 'down'] :
        next_x, next_y = now_x, now_y-1   
    return next_x, next_y




# 바깥쪽으로 도는 방법 -> (진행 방향을 직진으로 설정하는 기준) -90도, 180도, 90도 위 순서대로 확인  
def search_lst(dx, dy) :
    return [[-1*dy, dx], [dx, dy], [dy, -1*dx]]


def solution(rectangle, characterX, characterY, itemX, itemY) :
    start, getItem = True, False
    # Make Matrix Board 2X scale (x -> 2x-1, y -> 2y-1)
    board = get_board_matrix(rectangle)
    board = update_board_matrix(rectangle, board)
    now_x, now_y = 2*(characterX)-1, 2*(characterY)-1
    # 시작점 도는 방향 설정
    before = (now_x, now_y)
    item_length, return_length = 0, 0

    while True :
        if start :
            start_info = get_start_info(rectangle, now_x, now_y)
            if len(start_info) == 1 :
                next_x, next_y = go_line(start_info, now_x, now_y)
            else :
                if start_info[0][0] != start_info[1][0] :
                    next_x, next_y = move_to_other_box(start_info, now_x, now_y)
                else :
                    next_x, next_y = change_direction(start_info, now_x, now_y)
            start = False
            
        else :
            dx, dy = now_x - before[0], now_y - before[1]
            search = search_lst(dx, dy)
            for check in search : 
                next_x, next_y = now_x+check[0], now_y+check[1]
                if next_x > 0 and next_x < len(board[0]) and next_y > 0 and next_y < len(board) :
                    if board[next_y][next_x] == 1 :
                        break
        # 시작점 -> item
        if getItem  :
            return_length +=1
            if next_x == 2*characterX-1 and next_y == 2*characterY -1 :
                break
        else : # item -> 시작점 
            item_length +=1
            if next_x == 2*itemX-1 and next_y == 2*itemY-1 :
                getItem = True

        before = (now_x, now_y)
        now_x, now_y = next_x, next_y
        
    return min(return_length, item_length)//2

👩‍🏫 아이디어

• 제가 풀었지만..... 일일히 다 구현한 코드라 좋은 풀이 같지는 않습니다.... 조금 더 간결하게 풀 수 있도록 고민해봐야 겠습니다.

1. 꺽는 부분을 고려하기 위해 좌료를 확장(X 2) 하자.
2. 문제에서 주어진 조건 대로 구현하자.