[python code review] 3주차 (소수&팰린드롬, AC, 합승택시요금)

[소수&팰린드롬]

https://www.acmicpc.net/problem/1747

1. 코드 구현 (하)

from math import sqrt
import sys
input = sys.stdin.readline

def isPrime(num):
    if num == 1: return False
    for i in range(2, int(sqrt(num))+1):
        if num % i == 0:
            return False
    return True

def isPalindrome(num):
    data = str(num)
    k = len(data)
    for i in range(k//2):
        if data[i] != data[k-1-i]:
            return False
    return True

n = int(input())
while True:
    if isPrime(n) and isPalindrome(n):
        print(n)
        break
    n += 1

팰린드롬 함수를

def isPalindrome(num):
    data = str(num)
    return data == data[::-1]

처럼 구현하는 것보다 위와 같이 구현하는게 좀 더 빠르게 동작했다.

 

[AC]

https://www.acmicpc.net/problem/5430

5430번: AC

1. 코드 구현 (상)

for _ in range(int(input())):
    fn = input()
    # 두 번 뒤집는 경우 제외 
    fn.replace("RR", '')
    n = int(input())
    arr = input()[1:-1].split(',')  
        
    D_front, D_back, check = 0, 0, True
    for key in fn:
        if key == 'R': 
            check = not check
        elif key == 'D': 
            if check: 
                D_front += 1
            else: 
                D_back += 1
    
    if D_front + D_back <= n:
        arr = arr[D_front:n-D_back]
        if not check: 
            arr.reverse()
        print('[' + ','.join(arr) + ']')
    else: 
        print("error")

시간 초과 발생하여 다른 풀이를 참고하였는데 전혀 생각치 못한 풀이였다.

 - 만약 'R'이 등장한다면 기존에 'D'가 앞에서 삭제되던 것이 뒤에서 삭제되어야 하므로

   check 변수를 False 처리하여 뒤에서 꺼낸다.

 - 'D' 연산이 들어왔을때 바로 원소를 삭제하지 않고 인덱스 값을 D_front, D_back 변수로 관리하여

    마지막에 슬라이싱으로 한번에 결과를 처리한다. 

 

arr = list(map(str, input()[1:-1].split(',')))  <- 이부분을 

아래와 같이 구현하면 에러가 발생하는데 이유를 아직 찾지 못했다. 

data = input()
arr = [data[i*2+1] for i in range(n)]

 

[합승택시요금] (상)

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

코딩테스트 연습 - 합승 택시 요금

+ 같이 보면 좋은 문제 (다익스트라 최소 비용 문제) https://www.acmicpc.net/problem/1916

1. 코드 구현 

import heapq

def dijkstra(s, e):
    global graph, lenth
    visit = [1e9 for _ in range(length+1)]
    visit[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    while que:
        cost, node = heapq.heappop(que)
        if visit[node] < cost:
            continue
        for i in graph[node]:
            next_node, next_cost = i[0], i[1]
            next_cost += cost
            if next_cost < visit[next_node]:
                visit[next_node] = next_cost
                heapq.heappush(que, (next_cost, next_node))
    return visit[e]

def solution(n, s, a, b, fares):
    global graph, length
    length = n
    answer = 1e9
    graph = [[] for _ in range(n+1)]
    # 무방향 그래프 
    for i, j, c in fares:  
        graph[i].append((j, c))
        graph[j].append((i, c))
    # 최소 비용 구하기
    for i in range(1, n+1):
        # s = i : 합승 x, s != i : 합승 o 
        answer = min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b))
    return answer

내용이 어려워 블로그를 참고함..

 

- 다익스트라 알고리즘 : 단계마다 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드를 선택하여 해당 노드를 거쳐가는 경우를 확인하여 최단 거리를 갱신하는 방법 

특정 노드까지의 최단거리 정보를 힙에 넣어 처리함으로써 출발노드로부터 가장 짧은 노드를 더욱 빠르게 찾을 수 있다.