가장 긴 팰린드롬

🤖문제 : 가장 긴 팰린드롬 Lv3

😎풀이

def solution(s):
    answer = 1
    if len(s) == 1 :
        return 1
    
    # 홀수 개
    for i in range(1, len(s)-1) :
        for j in range(i) :
            if i-1-j < 0 or i+1+j+1 == len(s)+1:
                break
            before = s[i-1-j:i]
            after = s[i+1 : i+1+j+1]
            if before == after[::-1] :
                length = 2*(j+1)+1
                answer = length if length > answer else answer
            else :
                break
                
    # 짝수 개
    for i in range(len(s)-1) :
        for j in range(i+1) :
            if i-j < 0 or i+1+j+1 == len(s)+1:
                break
            before = s[i-j:i+1]
            after = s[i+1 : i+1+j+1]
            if before == after[::-1] :
                length = 2*(j+1)
                answer = length if length > answer else answer
            else :
                break
    
    return answer

👩‍🏫접근 방식

• 투 포인터.
• i로 중심점을 잡고, j를 활용하여 한칸씩 이동하며 팰린드롬 여부를 비교.
• 문제의 차원 분해
  • 팰린드롬 문자열의 길이가 홀수일 경우와 짝수일 경우를 동시에 조사하면 논리가 복잡해지고 구현이 어려워짐.
  • 시간 체크이후 두 조건을 분리하여 진행해도 문제 없음을 파악했고, 홀수일 경우와 짝수일 경우를 분리해서 구함.

행렬 테두리 회전하기

🤖문제 : 행렬 테두리 회전하기 Lv3

😎풀이

import numpy as np

def solution(rows, columns, queries):
    answer = []
    before_arr = np.array([[columns*j+i for i in range(1, columns+1)] for j in range(0, rows)])
    after_arr = np.array(before_arr, copy=True)
 
    for [tr, tc, br, bc] in queries :
        min_num = 100*100
        # top move to right
        for c in range(tc-1, bc-1) :
            after_arr[tr-1][c+1] = before_arr[tr-1][c]
            min_num = int(after_arr[tr-1][c+1]) if int(after_arr[tr-1][c+1]) < min_num else min_num
        
        # right move to down
        for r in range(tr-1, br-1) :
            after_arr[r+1][bc-1] = before_arr[r][bc-1]
            min_num = int(after_arr[r+1][bc-1]) if int(after_arr[r+1][bc-1]) < min_num else min_num
            
        # bottom move to left
        for c in range(bc-1, tc-1, -1) :
            after_arr[br-1][c-1] = before_arr[br-1][c]
            min_num = int(after_arr[br-1][c-1]) if int(after_arr[br-1][c-1]) < min_num else min_num
            
        # left move to up
        for r in range(br-1, tr-1, -1) :
            after_arr[r-1][tc-1] = before_arr[r][tc-1]
            min_num = int(after_arr[r-1][tc-1]) if int(after_arr[r-1][tc-1]) < min_num else min_num
        
        answer.append(min_num)
        before_arr = np.array(after_arr, copy=True)
    return answer

👩‍🏫접근 방식

• 단순 구현 문제.
• 런타임 에러
  * 런타임 에러가 발생했을 때, 발생가능한 상황이 indexing 뿐이라고 생각했고, 인덱싱에서 문제를 초래할 수 있는 array 생성 부분을 수정했다.
  

숫자 변환하기

🤖문제 : 숫자 변환하기 Lv2

😎풀이

def solution(x, y, n) :
    if x == y :
        return 0
    memory = {}
    num, cnt = x, 1
    for v in [num+n, 2*num, 3*num] :
        memory[v] = min(memory[v], cnt) if v in memory else cnt

    max_cnt = ((y-x)//5) + 1
    for _ in range(max_cnt) :
        cnt += 1
        num_lst = [i for i in memory.keys()] 
        for num in num_lst :
            for v in [num+n, 2*num, 3*num] :
                if v <= y :
                    memory[v] = min(memory[v], cnt) if v in memory else cnt
            if y in memory :
                return memory[y]
            del memory[num]
    return -1

👩‍🏫접근 방식

• Dynamic programming, memorization
• 문제 조건상 연산하면 증가하는 방향으로만 진행이되므로 다음 두개의 정보를 추론할 수 있음.
  • 가장 처음 y가 되는 연산 횟수가 정답이 됨.
  • num을 $+n$, $\times 2$, $\times 3$ 연산이후 num을 memory에서 제거해 줄 수 있음.