(파이썬 S/W 문제해결 기본) Stack1 - 4869번 4866번 4871번 4873번

작성일 2019-08-15 In ALGORITHM 🎯 , SW 아카데미 댓글:

4869번 - 종이붙이기

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

피보나치 수열과 비슷


# def paper_paste(s):

# if s == N:

# return 1

# if s > N:

# return 0

# return paper_paste(s+10) + paper_paste(s+20)\*2

def paper_paste(s):
arr = [0]\*(s//10)
arr[0] = 1
arr[1] = 3

    for i in range(2, s//10):
        arr[i] = arr[i-1] + arr[i-2]*2

    return arr[s//10-1]

T = int(input())

for test_case in range(1, T+1):
N = int(input())

    print('#{} {}'.format(test_case, paper_paste(N)))

4866번 - 괄호검사

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

stack을 활용한 괄호검사

def count_parenthesis(line):
stack = []

    for key in line:
        if key == "(" or key == "{":
            stack += key
        elif key == ")" or key == "}":
            if len(stack) == 0:
                stack += key
                break
            elif key == ")" and stack[-1] == "(":
                stack.pop()
            elif key == "}" and stack[-1] == "{":
                stack.pop()
            else:
                stack += key
                break
    isPare = 0
    if len(stack) == 0:
        isPare = 1

    return isPare

T = int(input())

for test_case in range(1, T+1):
input_line = input()

    print('#{} {}'.format(test_case, count_parenthesis(input_line)))

4871번 - 그래프 경로

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

graph와 DFS
BFS는 queue를 사용하고, DFS는 stack을 사용함

def makeGraph(V, E): # 정점 번호를 key값, set()를 value값으로 갖는 기본 그래프 # ex) {1:set(), 2:set(), 3:set()}
graph = {key+1:set() for key in range(V)}

    # 정점(V)에 연결된 다음 노드(E) 입력, 그래프 수정
    # ex) {1:{3, 4, 6}, 2:{3}, 3:set()}
    for _ in range(E):
        key, val = map(int, input().split())
        graph[key].add(val)
    return graph

def DFS(graph, V, E):
visited = []
stack = []

    stack.append(V)

    is_path = 0
    while stack:
        node = stack.pop()
        if node == E:
            is_path = 1
            break

        if node not in visited:
            visited.append(node)
            stack.extend(graph[node])
    return is_path

T = int(input())

for test_case in range(1, T+1): # V: 정점 E: 간선을 입력
V, E = map(int, input().split()) # 간선(E) 수 만큼 반복하며 딕셔너리형 그래프 만듬
myGraph = makeGraph(V, E)

    # 확인할 경로의 시작 정점과 끝 정점 입력
    cV, cE = map(int, input().split())
    # 깊이우선탐색으로 경로 확인
    ans = DFS(myGraph, cV, cE)

    print('#{} {}'.format(test_case, ans))

4873번 - 반복문자 지우기

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

stack을 활용

T = int(input())

for test_case in range(1, T+1): # 일단 입력 받고
seq_string = list(input()) # 스택을 만들어서 한 단어씩 push, pop 한다
stack = []

    for word in seq_string:
        # 맨 처음 스택이 비어있을 때,
        if len(stack) == 0:
            stack.append(word)
        # 그 외, 새로 입력되는 문자와 스택 마지막 문자가 같으면 pop
        else:
            if stack[-1] == word:
                stack.pop()
            else:
                stack.append(word)

    print('#{} {}'.format(test_case, len(stack)))

(파이썬 S/W 문제해결 기본) String - 4864번 4861번 4865번

작성일 2019-08-14 In ALGORITHM 🎯 , SW 아카데미 댓글:

4864번 - 문자열 비교

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

보이어 무어 알고리즘 활용

def boyer_moore(pattern, text):
result = 0
pivot = len(pattern)-1
skip = list(pattern)
skip.reverse()

    while result!=1 and pivot<len(text):
        if pattern[len(pattern) - 1] != text[pivot]:
            if text[pivot] in skip:
                nums = skip.index(text[pivot])
                pivot += nums
            else:
                pivot += len(pattern)
        else:
            for i, j in zip(range(pivot, pivot - len(pattern), -1), skip):
                if text[i] == j:
                    result = 1
                else:
                    result = 0
                    pivot = i
                    break
    return result

T = int(input())

for test_case in range(1, T+1):
str1 = input()
str2 = input()

    print('#{} {}'.format(test_case, boyer_moore(str1, str2)))

4861번 - 회문

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

2차원 리스트 다루는게 아직 익숙하지 않다

TC = int(input())

for tc in range(1, TC+1):
N, M = map(int, input().split())
result = []

    #가로줄 확인
    Garo_lst = []
    for i in range(N):
        Data = input()
        Garo_lst.append(Data)
        for i in range(len(Data)-M+1):
            if Data[i:M+i] == Data[i:M+i][::-1]:
                result.append(Data[i:M+i])

    #세로줄 확인
    Sero_lst = []
    Sero_sub_lst = ''
    for x in range(N):
        for y in Garo_lst:
            Sero_sub_lst += y[x]
        Sero_lst.append(Sero_sub_lst)
        Sero_sub_lst =''
    print(Sero_lst)

    for sero_data in Sero_lst:
        for j in range(len(sero_data)-M+1):
            if sero_data[j:M+j] == sero_data[j:M+j][::-1]:
                result.append(sero_data[j:M+j])

    # print(result)
    print("#%d %s"%(tc, result[0]))

4865번 - 글자수

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

T = int(input())

for test_case in range(1, T+1):
str1 = input()
str2 = input()
cnt, max_cnt = 0, 0

    for i in str1:
        for j in str2:
            if i == j:
                cnt += 1
        if cnt > max_cnt:
            max_cnt = cnt
        cnt = 0

    print('#{} {}'.format(test_case, max_cnt))

(파이썬 S/W 문제해결 기본) List2 - 4836번 4837번 4839번 4843번

작성일 2019-08-07 In ALGORITHM 🎯 , SW 아카데미 댓글:

4836번 - 색칠하기

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

T = int(input())

for test_case in range(1, T + 1):
red_color = []
blue_color = []

    N = int(input())
    for i in range(N):
        purple_color = 0
        r1, c1, r2, c2, color = map(int, input().split())

        for y in range(c1, c2+1):
            for x in range(r1, r2+1):
                if color==1:
                    red_color.append([x,y])
                elif color==2:
                    blue_color.append([x,y])


        for red in red_color:
            for blue in blue_color:
                if red == blue:
                    purple_color += 1

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

4837번 - 부분집합의 합

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

부분집합을 구할 때, 비트연산을 사용

set_A = [num for num in range(1,13)]
subset_A = [[set_A[j] for j in range(12) if i&(1<<j)] for i in range(1<<12)]

T = int(input())

for test_case in range(1, T + 1):
N, K = map(int, input().split()) # N : 부분집합 원소의 수, K : 부분집합의 합
cnt=0

    for subset in subset_A:
        if len(subset)==N and sum(subset)==K:
            cnt+=1

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

4839번 - 이진탐색

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

이진탐색 재귀함수

def binary_search(left, right, key, cnt):
if left>right:
return None
else:
middle = (left+right)//2
if key==middle:
return cnt
elif key<middle:
return binary_search(left, middle, key, cnt+1)
else:
return binary_search(middle, right, key, cnt+1)

T = int(input())

for test_case in range(1, T + 1):
P, A, B = map(int, input().split())

    winner = 0
    if binary_search(1, P, A, 0)<binary_search(1, P, B, 0):
        winner ='A'
    elif binary_search(1, P, A, 0)>binary_search(1, P, B, 0):
        winner = 'B'

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

4843번 - 특별한 정렬

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

정렬시키고 양끝에서 안쪽으로 iter 반복

def special_sort(arr):
s_arr = sorted(arr)
length = len(s_arr)

    special_arr = []
    for i in range(length):
        if i%2==0:
            special_arr.append(s_arr[length-1-i//2])
        else:
            special_arr.append((s_arr[i//2]))
    return special_arr

T = int(input())

for test_case in range(1, T + 1):
N = int(input())
arr_N = [int(num) for num in input().split()]

    print('#{} '.format(test_case), end='')
    for a in special_sort(arr_N)[:10]:
        print(a, end=' ')
    print()

NUNU

개인적으로 공부하면서 정리한 내용들을 블로그에 남기고 있습니다.

RSS