Week02 TEST

문제 1

• 소요 시간 : 30분
• 카테고리 : 분할 정복, 재귀

 

• input이 잘린 걸 모르고 이상한 input으로 테스트하다가 문제가 이해가 안돼서,, 문제 이해에만 10분을 날렸다.
• 문제를 제대로 안읽어서 전체가 0또는 1일때도 () 안에 넣어서 출력하게끔 구현해서 10분을 삽질함

 

🏃‍♂️ Try 1 Fail 83%

import sys

input = sys.stdin.readline
n = int(input())
graph, answer = [], []
dx = [0, 1, 0, 1]
dy = [0, 0, 1, 1]

for _ in range(n):
    graph.append(list(input().rstrip()))

# 색이 모두 동일한 지 판단
def validation(n, x, y):
    color = graph[y][x]
    for i in range(y, y + n):
        for j in range(x, x + n):
            if graph[i][j] != color: return False
    return color

def quad_tree(n, x, y):
    for i in range(4):
        nx = x + dx[i] * n
        ny = y + dy[i] * n 
        rst = validation(n, nx, ny)
        if rst == False:
            answer.append('(')
            quad_tree(n // 2, nx, ny)
            answer.append(')')
        else:
            answer.append(rst)

if validation(n, 0, 0) != False: answer.append(graph[0][0])
else: quad_tree(n // 2, 0, 0)

print('(', ''.join(answer), ')', sep='')

• 마지막 프린트 문 보면 무조건 ‘(’ ‘)’를 포함해서 출력함. → 문제 조건 미충족

 

🎉 Success

import sys

input = sys.stdin.readline
n = int(input())
graph, answer = [], []
dx = [0, 1, 0, 1]
dy = [0, 0, 1, 1]

for _ in range(n):
    graph.append(list(input().rstrip()))

# 색이 모두 동일한 지 판단
def validation(n, x, y):
    color = graph[y][x]
    for i in range(y, y + n):
        for j in range(x, x + n):
            if graph[i][j] != color: return False
    return color

def quad_tree(n, x, y):
    for i in range(4):
        nx = x + dx[i] * n
        ny = y + dy[i] * n 
        rst = validation(n, nx, ny)
        if rst == False:
            answer.append('(')
            quad_tree(n // 2, nx, ny)
            answer.append(')')
        else:
            answer.append(rst)

# 전체가 0 또는 1이면 바로 출력 후 프로그램 종료
if validation(n, 0, 0) != False: sys.exit(print(graph[0][0]))
else: quad_tree(n // 2, 0, 0)

print('(', ''.join(answer), ')', sep='')

 

 

 

---

문제 2 ⭐️ Retry -> KMP

• 소요 시간 : 32분
• 카테고리 : 문자열, 스택

 

• 타겟 문자열에서 패턴 문자열 찾는 문제
• KMP로 풀고 싶었지만,, 아직 제대로 이해못한 상태라 어쩔 수 없이 스택 완전 탐색으로 풀었다.
  ↪️ KMP 로 다시 풀어보기

 

import sys

input = sys.stdin.readline
string = list(reversed(input().rstrip()))
bomb = list(input().rstrip())
slen, blen = len(string), len(bomb)
stack = []

def check_str():
    if len(stack) < len(bomb): return False
    for i in range(-1, -blen -1, -1):
        if stack[i] != bomb[i]: return False
    return True

while string or flag:
    if string:
        stack.append(string.pop())
    flag = check_str() 
    if flag:
        for _ in range(blen): stack.pop()

if stack: print(''.join(stack))
else: print('FRULA')

• check_str
• 타겟 문자열 스택에 패턴 문자열이 포함되어 있는 경우 : True 리턴

flag : 마지막에 연쇄적으로 문자열 폭발이 일어날 때를 처리해주기 위함

 

 

 

---

문제 3

• 완전 탐색과 heap으로 구현

❌ Fail

import sys
from math import pow
from heapq import *

input = sys.stdin.readline
k, n = map(int, input().split())
arr = list(map(int, input().split()))
multi_prime = []
cnt = 0

for i in range(k - 1):
    j = 1
    while pow(arr[i], j) <= arr[i + 1]:
        multi_prime.append(pow(arr[i], j))
        j += 1
multi_prime.append(arr[-1])

cnt = len(multi_prime)
if cnt >= n:
    sys.exit(print(multi_prime[n - 1]))

# flag, multi_len = 0, len(multi_prime)
# while cnt < n:
#     if flag > multi_len: 
#         m = heappop(multi_prime)
#         flag = 0

• 우선 현재 있는 소수들의 제곱 수를 원본 배열에 추가해주는 방식으로 구현했다.
• 뒷 부분의 소수 곱들은 힙으로 넣고 pop을 하려고 했지만,,,^^
  • 제대로 구현도 못해보고 시험 시간 종료 😅..!

 

↪️ Retry

import sys
from heapq import *

input = sys.stdin.readline
k, n = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
priority_queue = [] # 소수 곱들이 들어가는 힙
for a in arr: # 원본 소수 힙에 삽입
    heappush(priority_queue, a)

cnt = 1
while True:
    x = heappop(priority_queue)
    if cnt == n:
        print(x)
        break

    for a in arr:
        heappush(priority_queue, x * a)   
        if x % a == 0: break
    cnt += 1

• x번째 수를 구하려면 힙에서 x번 원소를 뽑아내면 됨
• `if x % a == 0: break` ? 
  • 중복으로 원소를 넣는 경우 방지 위함

 

 

 

 

🙂 Best : 시간 체킹 및 시간 분배를 하면서 푸니까 실제 코테 느낌이 났다.

🙁 Worst : 또 문제 조건 실수,,,

→ 문제 이해 최대 10분으로 잡고 문제 이해 및 예외 조건 명확히 파악하기!