[백준] 자료구조_17103, 17087, 10828, 9012, 10773, 1935, 1406, 10799

골드바흐 파티션

• 코드

import math
def get_primary_list(n):
    array = [1 for _ in range(n+1)]

    for i in range(2, int(math.sqrt(n))+1):
        k = 2
        if array[i]:
            while k * i <= n:
                array[k*i] = False
                k+=1

    return array

n = int(input())
nums = [int(input()) for _ in range(n)]
max_num = max(nums)
primarys = get_primary_list(max_num)

for num in nums:
    result = 0

    for i in range(2, num // 2 + 1):
        if primarys[i] and primarys[num - i]:
            result += 1

    print(result)

• 풀이를 생각해낸 과정
  • 에라토스테네스의 채를 이용하여 소수 여부를 판단하고, 시간 초과로 인해 구하는 과정을 함수로 뺀다.
• 시간복잡도 계산
  • O(N^2)

숨바꼭질 6

• 코드

def get_gcd(a,b):
    if a < b:
        a, b = b, a
    while a > 0:
        b, a = a, b%a
    return b

n , s = map(int,input().split())
arr = list(map(int,input().split()))

temp = []

for i in arr:
    temp.append(abs(s-i))

gcd = temp[0]
for i in range(1,len(temp)):
    gcd = get_gcd(gcd,temp[i])
print(gcd)

• 풀이를 생각해낸 과정
  • 수빈의 위치에서 각 동생의 위치의 차의 절대값을 리스트에 넣고 이 값들의 최대 공약수가 가능한 D의 최대 값을 보장한다.
• 시간복잡도 계산
  • O(N)

스택

• 코드

import sys
input = sys.stdin.readline
n = int(input())

count = 0
arr = []

while count < n:
    count +=1
    cmd = input().split()
    
    length = len(arr)

    if cmd[0] == "push":
        arr.append(int(cmd[1]))
        
    elif cmd[0] == "empty":
        if length == 0:
            print("1")
        else:
            print("0")
    elif cmd[0] == "pop":
        if length == 0:
            print("-1")
        else:
            print(arr.pop())
    elif cmd[0] == "size":
        print(len(arr))    
    elif cmd[0] == "top":
        if length == 0:
            print("-1")
        else:
            print(arr[-1])

• 풀이를 생각해낸 과정
  • if~elif로 해당 명령어 각각 처리
  • append() : O(1)
  • pop() : O(1)
  • 시간 초과 해결
    • import sys 로 입력 받기
    • 입력받을 때 split(” “) 처리해주기
• 시간복잡도 계산
  • O(N)

괄호

• 코드

import sys
input = sys.stdin.readline
n = int(input())

for i in range(n):
    vps = input()
    check = []
    
    for j in range(len(vps)):
        if vps[j] == "(":     
            check.append(1)
        elif vps[j] == ")":
            if check == []:
                print("NO")
                break
            else: check.pop()
        elif j == len(vps)-1:
            if check == []:
                print("YES")
            else:
                print("NO")

• 풀이를 생각해낸 과정
  • “(” 개수 만큼 “)”가 존재해야 한다
  • “(” 일 때는 리스트에 1을 추가해주고, ”)” 일 때는 리스트가 비워져 있다면 NO를 출력하고 해당 반복문 종료 아니라면 pop을 실행한다.
  • 원소의 마지막일 때 비워져 있다면 YES, 아니라면 NO
• 시간복잡도 계산
  • O(N^2)

제로

• 코드

import sys
input = sys.stdin.readline
n = int(input())

money = []
for i in range(n):
    m = int(input())
    
    if m == 0:
        money.pop()
    else:
        money.append(m)
print(sum(money))

• 풀이를 생각해낸 과정
  • 입력 값이 0일 때 지울 수 있는 수가 있음을 보장한다는 문제 조건이 있으므로 리스트 확인 안해도 됨
  • 리스트의 pop과 append 함수를 이용하여 구현 후, sum 함수로 최종 합을 구한다.
• 시간복잡도 계산
  • O(N)

후위 표기식2

• 코드

def calculations(c, arr):
    num1 = arr.pop()
    num2 = arr.pop()
    if c == "+":
        op.append(num2 + num1)
    if c == "-":
        op.append(num2 - num1)
    if c == "*":
        op.append(num2 * num1)
    if c == "/":
        op.append(num2 / num1)
  
n = int(input())
notation = input()
dic = {}
op = []

for i in range(n):
    k = int(input())
    dic[chr(65+i)] = k

for i in notation:
    if i.isalpha():
        op.append(dic[i])
    else:
        calculations(i, op)
print("%.2f"%op[0])

• 풀이를 생각해낸 과정
  • 후위 표기법 참고 
    • 알파벳이면 딕셔너리에 저장된 해당 알파벳 숫자를 리스트에 저장한다. (append)
    • 연산자이면 리스트에서 마지막에 담긴 2개 숫자를 꺼내고(pop) 해당 연산 계산 후 결과를 리스트에 저장한다.
    • 최종적으로 남아있는 리스트 값을 출력한다.
  • ‘%.2f’ % 함수를 이용하여 소수점 자릿수를 제한한다.
• 시간복잡도 계산
  • O(N)

에디터

• 코드

import sys
input = sys.stdin.readline

sl = list(input().rstrip()) 
n = int(input())
sr = []

for i in range(n):
    cmd= input().split()
    
    if cmd[0] == "L":
        if sl:
            sr.append(sl.pop())
    if cmd[0] == "D":
        if sr:
            sl.append(sr.pop())
    if cmd[0] == "B":
        if sl:
            sl.pop()
    if cmd[0] == "P":
        sl.append(cmd[1])
sl.extend(reversed(sr))
print(''.join(sl))

• • rstrip()으로 ‘\n’ 제거
  • 커서를 기준으로 리스트를 나누어서 계산하여 pop, append만 이용해서 시간 복잡도를 줄일 수 있다.
  • sr에 값이 아무것도 존재하지 않는다면 sr.reverse() 는 TypeError를 띄우기 때문에 reversed(sr)를 사용하여 리스트를 뒤집어준다.풀이를 생각해낸 과정
• 시간복잡도 계산
  • O(N)