2020년 4월 28일 화요일

5208. [파이썬 SW 문제해결 구현] 5일차 - 전기버스2

내가 지금까지 한 재귀 중 제일 자랑스러워서와 발상이 좋은 것 같아 올려봄.
또 오랜만에 타블렛 좀 써보고 싶었따.
처음에 index 0부터 시작해서 일단 숫자만큼 더하고 차차 빠지는 식으로 재귀. step을 +1씩 올리며 카운트 한다. best를 저장.
차차 +2까지 1씩해서 올리지 않고 바로 +2해서 -1만큼 한 이유는 코드의 편의성과 먼저 best를 설정해서 backtracking의 기준점 설정을 좀더 빠르게 하기 위함.

import sys

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

def gobus(start_index,step, end_index):
    global scn
    # print("start_index" , start_index,"step",step,"end_index",end_index)
    if step > scn:
        return
    elif start_index >= end_index:
        # print("end.. step",step, "scn",scn)
        if step < scn:
            scn = step
            # print("scn",scn)
    else:
        for i in range(start_index+N[start_index],start_index,-1):
            gobus(i,step+1,end_index)


    return

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

    scn = len(N)-1
    gobus(0,0,len(N))

    print("#{}".format(test_case),scn-1)

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

2020년 4월 27일 월요일

blogger에서 code highlight

https://www.compromath.com/2017/02/adding-specific-code-syntax-highlighter.html
<pre class="prettyprint"><code class="language-py">YOUR CODE HRER</code></pre>

5204. [파이썬 SW 문제해결 구현] 4일차 - 병합 정렬

나중에 연구할려고 남겨놓았다.
이 문제는 원래 list를 이용해서 merge 할 시 리스트의 재배열 문제로 시간이 오래 걸려서 문제를 못 풀게 해서 linked list로 풀게끔 유도하고 있었으나
merge 할 때 list의 크기를 고정시켜서 정보를 빼내는 방법으로 아슬아슬하게 통과한 것 같다.
나중에 node를 이용해서 만들어봐야 할 듯 하다.. 근데 어케 하지

import sys

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

def merge(left, right):

    # 밑의 것은 이론에서 리스트를 사용할 경우의 병합과정이다.
    # 근데 시간이 너무 오래 결려 안되는 것 같다.
    # 리스트를 고정 길이로 만들기.
    # https://tothefullest08.github.io/algorithm/2019/08/31/1_5204_%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%AC/

    result = [0] * (len(left) + len(right))
    # 두 개의 분할된 리스트를 병합하여 result를 만듦
    i=0
    j=0
    while i < len(left) and j < len(right) :
        # 양쪽 리스트에 원소가 남아있는 경우
        # 두 서브 시르스틔 첫 원소들을 비교하여 작은 것부터 result에 추가함
        if left[i] <= right[j]:
            result[i+j] = left[i]
            i += 1
        else:
            result[i + j] = right[j]
            j += 1
    while i < len(left) :
        # 왼쪽 리스트에 원소가 남아있는 경우
        result[i+j] = left[i]
        i += 1
    while j < len(right) :
        # 오른쪽 리스트에 원소가 남아있는 경우
        result[i + j] = right[j]
        j += 1
    return result

    # 밑에가 원본. 위에가 개조 버전.

    # while len(left) > 0 and len(right) > 0 : # 양쪽 리스트에 원소가 남아있는 경우
    #     # 두 서브 시르스틔 첫 원소들을 비교하여 작은 것부터 result에 추가함
    #     if left[0] <= right[0]:
    #         result.append(left.pop(0))
    #     else:
    #         result.append(right.pop(0))
    # if len(left) > 0: # 왼쪽 리스트에 원소가 남아있는 경우
    #     result.extend(left)
    # if len(right) > 0: # 오른쪽 리스트에 원소가 남아있는 경우
    #     result.extend(right)
    # return result


def merge_sort(m):
    global iflgtr

    if len(m) <= 1:
        return m

    # 1. DIVIDE 부분
    mid = len(m) // 2
    left = m[:mid]
    right = m[mid:]

    # 리스트의 크기가 1이 될 때까지 merge_sort 재귀 호출
    left = merge_sort(left)
    right = merge_sort(right)

    if left[-1] > right[-1]:
        iflgtr += 1

    # 2. CONQUER 부분 : 분할된 리스트들 병합
    return merge(left, right)

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

    iflgtr = 0
    LS = merge_sort(L)

    print("#{}".format(test_case),LS[N//2], iflgtr)

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

5110. [파이썬 SW 문제해결 기본] 7일차 - 수열 합치기

나도 참고할라고 전에 했던거 가져왔다.

노드를 추가할 때 기존에 가지고 있던 head의 노드부터 addToLast를 계속 이용해서 추가한게 아니라 head2의 독자 linkedlist를 만들어 head1의 끝의 링크를 head2의 첫번재 노드에 연결했던 것만 기억이 난다.

import sys

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

class Node:
    def __init__(self, item, link=None):
        self.item = item
        self.link = link

    def addToFirst(self,data):
        global Head
        Head = Node(data,Head)

    def add(self,pre, data):
        if pre == None:
            print('error')
        else:
            pre.link = Node(data, pre.link)


    def addToLast(self,data):
        global Head
        if Head == None:
            Head = Node(data, None)
        else:
            p = Head
            while p.link != None:
                p = p.link
            p.link = Node(data, None)

    def printall(self):
        if self == None:
            print("empty")
        else:
            p = self            while p != None:
                print(p.item)
                p = p.link

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

    Head = None    for item in numbers:
        Node.addToLast(Head,item)


    for _ in range(M-1):
        InsertNumbers = list(map(int, input().split()))

        new_node = Node(InsertNumbers[0])
        node = new_node
        for item in InsertNumbers[1:]:
            node.link = Node(item)
            node = node.link

        new_last_node = node

        # 처음에 있을 경우        if Head.item > InsertNumbers[0]:
            new_last_node.link = Head
            Head = new_node
            continue
        # 중간에 있을 경우        MT = False        node = Head
        pre_node = None        while node != None:
            if node.item > InsertNumbers[0]:
                pre_node.link = new_node
                new_last_node.link = node
                MT = True                break            pre_node = node
            node = node.link
        if MT: continue
        # 끝까지 못 찾은 경우 (끝에 붙여야 한다)        pre_node.link = new_node

    result_list = []
    node = Head
    while node != None:
        result_list.append(node.item)
        node = node.link
    print("#{}".format(test_case),*result_list[:-11:-1])

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

5203. [파이썬 SW 문제해결 구현] 3일차 - 베이비진 게임

정답률이 의외로 낮아서 올려봄.
이론에서 나온 count list 방식을 이용하여 구하는 방법을 그대로 사용하였다.
특이한 점이라면 0~9까지의 카드를 쓰기 때문에 count list 길이는 10이 되어야 할 것 같지만 12로 했다. 그래야 run과 triplet을 동시에 검사할 때 [i] == [i+1] == [i+2] 를 이용할 시 index 범위를 넘어서 조사하는 일이 생기는데 이를 일일이 if문 예외로 걸러내기 귀찮아서 그랬다.
import sys

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

def is_run_or_triplet(count_list):
for i in range(len(count_list)):
if (count_list[i] >= 1) and (count_list[i+1] >= 1) and (count_list[i+2] >= 1):
return True
if (count_list[i] >= 3):
return True
return False

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

fpc = [0] * 12
spc = [0] * 12

result = 0
for i in range(len(full_list)):
if i % 2 == 0:
fpc[full_list[i]] += 1
if is_run_or_triplet(fpc):
result = 1
break
else:
spc[full_list[i]] += 1
if is_run_or_triplet(spc):
result = 2
break

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

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

2020년 4월 24일 금요일

5189. [파이썬 SW 문제해결 구현] 2일차 - 전자카트

예시에서 연결이 1-2-3-1, 1-3-2-1 이런식으로 두개라는 것을 보고 딱 봐도 순열이라고 생각했다.
[1,2,3] 개가 주어질 경우 맨 왼쪽, 맨 오른쪽은 1로 고정되어 있으니 [2,3] 끼리의 순열만을 생각한다.
import sys

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

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

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

cb = list(itertools.permutations(range(2,N+1),r=N-1))

distance = []
for tup in cb:
sub_distance = 0
sub_distance += route[0][tup[0]-1]
for i in range(len(tup)-1):
sub_distance += route[tup[i] - 1][tup[i+1] - 1]
sub_distance += route[tup[len(tup)-1]-1][0]
distance.append(sub_distance)

print("#{}".format(test_case),min(distance))

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