251127 코테연습 기록

길 찾기 게임 (프로그래머스)

• 어제 못풀었던 문제
• 클래스로 노드 구현하는 법은 알았으나, 그거만 가지고 안 됨
• 노드 클래스는 만들었는데, 그래서 그걸 어떻게 써먹을지 바로 구상이 안 됨
• 유사한 문제를 몇 번 풀어보고 다시 도전해야할듯

가장 긴 팰린드롬 (프로그래머스)

• 제한 시간 : 30분
• 접근 방식 : DP
• 풀이 성공.. 하지만 비효율적

제출 코드

def solution(s):
    dp = [0]*len(s)
    string = ""
    for i in range(len(s)):
        string += s[i]
        for j in range(len(string)):
            target = string[j:]
            #print(string[j::-1])
            if target == target[::-1]:
                dp[j] = max(dp[j], len(target))
    
    #print(dp)
    
    return max(dp)

• 초반에 좀 당황하긴 했는데, DP로 풀렸다 (각 글자마다 그 글자부터 시작해서 문자열 끝까지를 뒤집어서 같은지 확인)
• 이번에는 방심하지 않고 테스트 케이스 몇 개 더 만들어서 코드를 수정할 수 있었다
• 슬라이싱한 문자열을 뒤집으려고 할 때 string[j::-1] 이런식으로 쓰면 이상해져서 따로 변수에다 할당하고 target[::-1] 이렇게 비교했다
• 다만 문자열 s의 길이가 2500까지인 거 보고 이렇게 풀었는데, 다행히 효율성 테스트는 통과했지만 2초 정도 걸린다
• 아무래도 찝찝해서 찾아보니까 이 방법은 거의 O(n^3)에 가까울 정도로 비효율적이다.. 투 포인터로 푸는 게 정석이었다
• 다음에 다시 한번 풀어봐야겠다

가장 먼 노드 (프로그래머스)

• 이미 풀었던 문제 (다익스트라)
• 다만 주의할 점 하나 발견

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    shortest = [10**15]*(n+1)
    for i,j in edge:
        graph[i].append(j)
        graph[j].append(i)

    shortest[0] = 0
    shortest[1] = 0

    queue = []
    heappush(queue, [0,1])
    while queue:
        accum_dist, node = heappop(queue)
        for next_node in graph[node]:
            if accum_dist + 1 >= shortest[next_node]:
                continue
            shortest[next_node] = accum_dist + 1
            heappush(queue, [accum_dist+1, next_node])

    #print(shortest)
    #shortest.sort()

    return shortest.count(max(shortest))

여기서 accum_dist + 1 >= shortest[next_node]: 이 부분 등호 안넣어주면 일부 테스트케이스에서 queue가 비질 않아서 무한루프 돌게되는 현상 확인!