빛의 블로그

시발 뭐 이딴게 다있냐

이 문제와는 별개로 몇 군데를 찾아보니 접미어배열 자체가 유용한 듯 하다.

강의와 외부 코드를 참고해서 작성했다.

일단 set을 이용해서 꼼수 비슷하게 정답 하나 만들어놓고, 접미어 배열와 LCP배열 만들어 놓은거를 이용해서 푼 것과 비교해서 작성했다.

for i 문을 통해 A[i][1] 의 string을 보는데 A[i][1] 의 string도 앞에서부터 끊어 읽으면 set에서의 부분문자열을 읽는 것과 비슷해진다.

단지 이렇게 끊어 읽기만 하면 i의 뒤를 읽을 때 중복해서 읽는 문제가 생긴다.

가령 abac를 보면 처음엔 A[0][1]을 봐서 'abac'를 'a', 'ab', 'aba', 'abac'로 다 읽었다 치자.

그 뒤엔 A[1][1]을 보고 'ac'를 'a', 'ac'로 읽지만 이미 'a'는 중복이므로 이를 빼고 읽어야 한다.

하지만 이미 LCP를 통해 앞의 문자와 얼마나 중복되는 가를 이미 파악했다. 그래서 중복되는 만큼 더 건너뛰어서 시작하기 위해 LCP의 값을 이용한다.

import sys

# http://cd4761.blogspot.com/2017/02/trie-1.html
# http://cd4761.blogspot.com/2017/03/trie-2.html
# https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/
# http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221028710658
# https://swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?searchCondition=COMMU_DETAIL-COMMU_TITLE-NICK_NAME_TAG&commuId=AXAuybMapTADFAXq&searchKeyword=5254&orderBy=DATE_DESC&pageSize=10&pageIndex=1&&&&&&


def LongestCommonPrefix(a,b):
    i=0
    while i < min(len(a),len(b)):
        if a[i] != b[i]: break
        i += 1
    return i

sys.stdin = open("sample_input2.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..

    inp = input().split()
    n = int(inp[0])
    s = inp[1]

    print(s)
    print("n :",n)
    # 그냥 배열로 하니까 안됨.
    # 진짜 접미어 트리 배열 써야 하는 듯..
    sps = set()
    for i in range(len(s)):
        for j in range(len(s),i,-1):
            sps.add(s[i:j])
    sp = sorted(list(sps))
    print(sp)

    A = [[0] * 2 for _ in range(len(s))]
    for i in range(len(s)):
        A[i][0] = i
        A[i][1] = s[i:]
    # print(A)
    A = sorted(A,key=lambda a:a[1])
    print(A)
    LCP = [0] * len(A)
    LCP[0] = 0
    for i in range(1,len(A)):
        LCP[i] = LongestCommonPrefix(A[i-1][1],A[i][1])
    print(LCP)

    resultc = ''
    resultl = 0
    for i in range(len(A)):
        suffix_index = A[i][0]
        curstr = A[i][1]
        if n > len(curstr):
            n += LCP[i] - len(curstr)
        else:
            resultc = curstr[0]
            resultl = len(curstr[:(n+LCP[i])])
            break

    print("#{}".format(test_case),resultc,resultl)

    # ///////////////////////////////////////////////////////////////////////////////////

5250. [파이썬 SW 문제해결 구현] 7일차 - 최소 비용

다익스트라 알고리즘에 익숙해지기 위해 씀.

최소 거리부터 집합 S에 합치는 방식이다.

import sys

sys.stdin = open("sample_input.txt", "r")

def printmatrix(matrix):
    for i in matrix:
        print(i)
# https://hongsj36.github.io/2020/02/02/Ad_GraphMST/
def Dijkstra_custom(tera):
    # 원래 visited 리스트 만들어서 append 했었는데 역시 실행시간에 문제가 발생.
    # 나도 고정배열 써야지
    visited = [[False]*N for _ in range(N)]
    # d = [[1000] * N for _ in range(N)]
    d = [[float('inf')] * N for _ in range(N)]
    # Q = []
    Q = set()
    d[0][0] = 0
    # Q.append((0,0))
    Q.add((0,0))
    while True:
        # 최소 거리부터 집합 S에 합치는 다익스트라 알고리즘임.
        y,x = 0,0
        # minfuel = 1000000
        minfuel = float('inf')
        for r, c in Q:
            if d[r][c] < minfuel and not visited[r][c]:
                minfuel = d[r][c]
                y,x = r,c

        visited[y][x] = True
        Q.remove((y,x))
        if y == N-1 and x == N-1:
            return d[N-1][N-1]
        for i in range(4):
            new_y, new_x = y + dy[i], x + dx[i]
            if 0<=new_y tera[y][x]:
                    fuel = d[y][x] + tera[new_y][new_x] - tera[y][x] + 1
                else:
                    fuel = d[y][x] + 1
                if fuel < d[new_y][new_x]:
                    d[new_y][new_x] = fuel
                    Q.add((new_y,new_x))



T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())

    tera = [list(map(int, input().split())) for _ in range(N)]

    #왼,아래,오,위
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]

    result = Dijkstra_custom(tera)

    print("#{}".format(test_case),result)

    # ///////////////////////////////////////////////////////////////////////////////////

빛의 블로그

2020년 5월 6일 수요일

업로드

5254. [파이썬 SW 문제해결 최적화] 1일차 - 부분 문자열

5250. [파이썬 SW 문제해결 구현] 7일차 - 최소 비용