설탕 배달 (실버4)

문제의 감을 찾기 위해 1부터 30까지 대략 암산해보다가 -1이 뜨는 경우는 1의 자리 수만 존재하는 것 같았다. 그 이상 수에서는 -1이 뜰 이유가 없고 그래서 한 50 부터 다시 암산을 해본 결과 5개 담는 봉투가 후퇴할 일은 2번 이상이 없어서 그대로 코딩했다. 그리디 알고리즘 방식으로... 혹여나 놓친 것이 있을까봐 max_try는 2가 아니라 그냥 5로 넣었다. 느려져봤자 얼마나 느려지겠다고 해서

def pocket_n(num):
    can_5 = num // 5
    can_3 = num % 5 
    max_try = 0 
    while max_try < 5 and can_5 >= 0:
        max_try += 1
        if can_3 % 3 == 0:
            print(can_5, can_3//3)
            return can_5 + (can_3 // 3)
        else:
            can_5 -= 1
            can_3 += 5
    return -1

print(pocket_n(int(input()))

5개의 봉투를 최대한 사용하고 남은 것이 3으로 나누어 떨어지지 않을 시 5개의 봉투의 최대사용량 -1을 해서 다시 동일한 논리로 반복, 만약 5개 봉투의 최대사용량이 0미만으로 갔는데도 3으로 나누어떨어지지 않는다면 -1 전형적인 그리디 방식이다.

괄호 (실버4)

학교 자료구조 수업때 실습해본 기억으로 풀었다. 큐를 활용하면 매우 쉬운 문제. for문으로 괄호 데이터를 큐에 넣을지 말지 결정하면 된다. "("일 경우 큐에 넣고 ")"가 나타나면 큐에서 get()을 한다 만약 비어있거나 get을 했는데 "("가 아니라 ")"가 나타나면 return False이다. 이 과정이 끝이나고 큐가 모두 비어있다면 return True이다.

from queue import Queue

n = int(input())
def check_vps(data):
    que_vps = Queue()
    for i in data:
       if i == "(":
        que_vps.put(i)
       else:
          if que_vps.empty():
              return "NO"
          if que_vps.get() != "(":
              return "NO"
    if que_vps.empty():
        return "YES"
    else:
        return "NO"
        
for i in range(n):
    data = str(input())
    print(check_vps(data))

체스판 다시 칠하기 (실버 4)

8x8짜리 윈도우를 만들어서 가능한 모든 경우의 수를 탐색해야할 것 같다. 문제에 이미 힌트로 8x8에서 가능한 체스판 디자인의 경우의 수는 두가지이니 두가지 윈도우를 가능한 경우에 대해 모두 돌려서 바꿔야 할 요소들에 대한 count합들을 min()하여 return하면 될 것 같다.

N, M = map(int, input().split())
origin = []
for i in range(N):
    item = list(str(input()))
    origin.append(item)
    
def how_dif(start_low, start_col, start_what, origin):
    first_item = 0
    item = 0
    count = 0
    for i in range(8):
        item = item + first_item
        for j in range(8):
            if origin[start_low + i][start_col + j] != start_what[item % 2]:
                count += 1
            item += 1
        first_item += 1
        item = 0
    return count

lst_try = []

for i in range(N-7):
    for j in range(M-7):
        lst_try.append(how_dif(i, j, ["W","B"], origin))
        lst_try.append(how_dif(i, j, ["B","W"], origin))

print(min(lst_try))
        

개인적으로는 이 티어의 문제 난이도는 아닌 것 같다 꽤 어렵다. how_dif쪽을 작성하는데 생각이 꼬일 수 있고 아래에 7칸씩 배제하는 것을 8칸씩 배제하는 것으로 작성해서 실수하는 경우도 많을 것 같다. 브루트 방법보다 더 나은 방법이 있을까? 잘 모르겠다.

카드2 (실버 4)

queue를 이용해야하는 문제, queue에 모든 데이터를 넣고, 문제에 나온 조건을 그대로 실행한다. queue의 길이가 1이 될때까지. 이 문제는 시간복잡도를 고려했음에도 시간초과가 나서 어디서든 시간을 줄여보려고 했다.

# 첫 제출 500000(max) 기준 1.79초
from queue import Queue

n = int(input())
que = Queue()
for i in range(1, n+1):
    que.put(i)

while que.qsize() != 1:
    que.get()
    que.put(que.get())
    

print(que.get())

# 두번째 제출 500000(max) 기준 1.72초
from queue import Queue

n = int(input())
que = Queue()
for i in range(1, n+1):
    que.put(i)

length = que.qsize()
while length != 1:
    que.get()
    que.put(que.get())
    length -= 1
    

print(que.get())

첫 제출이 왜 안되는 지도 모르겠다. 기껏해야 N^2가 된게 아니라 2N정도인데.. 파이썬이 문제인가 싶다. max에서 0.05초 줄여서 성공했다. 코드를 보았을때 수정할만한게 while이 돌아갈 때 마다 qsize()를 다시 구하는 속도적 결함 말고는 보이진 않았다. 다른 자료구조를 가져와야하나 싶었지만, 큐보다 더 나은게 있나 싶다. 파이썬 큐 라이브러리가 어떻게 구현되어 있는지 알아봐야할 듯 하다.