h32j00

문제

처음 작성한 코드

import sys
from math import gcd

N = int(sys.stdin.readline())

wallet = 0
charge = None # 충전금
min_M = pow(10,18)

for _ in range(N):
    money , remain = map(int, sys.stdin.readline().split())
    if wallet + money < 0: #충전
        if remain != 0:
            min_M = min(min_M, remain) # min_M(남은 금액의 최소)이 충전금보다 많으면 오버해서 충전한거
        
        charge_tmp = remain - money - wallet #현재 충전된 금액

        #charge -> 충전값 정함
        if charge == None:
            charge = charge_tmp
        else:
            charge = gcd(charge, charge_tmp)
        
        #오버해서 충전했거나, charge==1일때는 무조건 remain이 0이어야하는데 그 조건을 만족 못 시킬 경우
        if (min_M != pow(10,18) and charge <= min_M) or (charge == 1 and remain!=0):
            print(-1)
            break
    else: #충전안해도 될 때는 원래 있던 돈(wallet)과 현재 입출금된 돈(money)를 더하면 현재 남아있는 돈(remain)이 되어야한다.
        if wallet + money != remain:
            print(-1)
            break
    wallet = remain #현재 남아있는 돈(remain)을 원래있던 돈(wallet)에 넣는다.
else:
    if charge == None: #충전금이 사용되지 않을때
        print(1)
    else: print(charge)

깨달은 점

• 위 문제는 구현하는 데 어려움이 없었지만 조건을 생각해야하는 데서 2시간이 걸렸다.. 자증나!
• 제일 이해 안갔던 조건은 최소충전금액이 남아있는 금액(입력값에서 두번째, remain)의 최소값보다 커야한다는 점이었다. 그래서 이해가 안가서 바람쐬러 가면서 생각했는데 ---> 돈이 없어서 충전을 했어 근데? 충전한 값보다 남은 돈이 더 많아? 그럼 충전을 안해도 됐는데 한거니까 모순된 행동인거다.. 글 쓰면서 또 이해 안가서 10분 생각했음.. -_-

반례

3
1500 1500
-1600 1200
-400 0
>> -1 (3번째 로그에 모순이 있음)

문제

처음 작성한 코드

import sys

# graph = [정점 번호, 거리]
def search(k, node):
    result = 0
    visited = [False] * (len(graph.keys())+1)
    stack = graph[node][:]
    visited[node] = True

    # 정점과 인접해있는 노드에서 k이상이면 result++
    for s in stack: 
        visited[s[0]] = True
        if s[1] >= k:
            result += 1

    # 인접해있는 노드말고
    while stack:
        n, d = stack.pop()
        for i in graph[n]:
            if not visited[i[0]]:
                visited[i[0]] = True
                min_d = min(d, i[1])
                stack.append([i[0], min_d])
                if min_d >= k:
                    result += 1
    return result

n, q = map(int, sys.stdin.readline().split())
graph = {i+1: list() for i in range(n)}

for i in range(n-1):
    s, e, distance = map(int, sys.stdin.readline().split())
    graph[s].append([e, distance])
    graph[e].append([s, distance])

for _ in range(q):
    k, node = map(int, sys.stdin.readline().split())
    print(search(k, node))

1. for i in range(n-1) 에서 연결관계가 입력되는데 만약 1 2 3 이렇게 입력되면 "1과 2는 3의 길이로 연결되어있다." 이 뜻이다. 그러면 나는 graph를 dictionary형태로 초기화해놓은 상태에서 1: [2,3], 2:[1,3] 이렇게 쌍방으로 넣어주면서 탐색할 준비를 했다.
2. 처음에 일단 정점 번호 node에서 인접한 노드만 따져서 k랑 비교후 result값을 증가시켜줬다.
3. 그 후에는 인접하지 않은 노드를 깊게 들어가면서 min()함수를 통해 최소값을 구해 그 값과 k와 비교해줬다.

깨달은 점

• 그냥 풀었는데 풀렸다.. 그말은 즉슨 dfs인지 bfs인지 모르고 풀었다는 것.. 근데 푼것만 보면 dfs같은데 stack을 이용하면 bfs라고 하고.. 참 어렵다 !!!!
• python3으로 채점받으면 시간초과 나는데 pypy3으로 하니까 통과됐다.. 실제 코테에선 얄짤없겠지? ㅜ.ㅜ

문제

처음 작성한 코드

import sys

def graph(i):
    far = 0
    diameter = 0
    visited = [False] * (v+1)
    visited[i] = True

    stack = tree[i][:]
    for s in stack:
        visited[s[0]] = True
        if s[1] > diameter:
            far = s[0]
            diameter = s[1]

    while stack:
        node, distance = stack.pop()
        for i in tree[node]:
            if not visited[i[0]]:
                visited[i[0]] = True
                stack.append((i[0], distance + i[1]))
                if diameter < distance +i[1]:
                    far = i[0]
                    diameter = distance+i[1]

    return far, diameter
v = int(sys.stdin.readline())
tree = dict()

for i in range(v):
    tmp = list(map(int, sys.stdin.readline().split()))
    tree[tmp[0]] = list()
    for j in range(1, len(tmp)-1, 2):
        tree[tmp[0]].append((tmp[j],tmp[j+1]))
        
far, _ = graph(1)
print(graph(far)[1])

1. 트리에서 임의의 점을 잡고 거기서 제일 먼 점을 구한다. -> far, _ = graph(1)
2. 그 점과 가장 먼 점을 구하고 그 길이를 출력한다. -> print(graph(far)[1])
3. stack.append할때 i[1]를 넣지않고 distance+i[1]를 추가하는 이유는 i[0]까지의 거리가 distance(그 전 점까지의 거리)와 i[1](그 점부터 i[0]까지의 거리)를 더해줘야하기 때문이다.

깨달은 점

• 트리의 지름을 구하는 공식이 있다. 임의의 점에서 제일 먼 점을 구하고 그 점에서 제일 먼 점까지의 거리가 트리의 지름이라고 한다. 처음에 임의의 점 (여기선 1번)에서 제일 먼 점까지의 거리만 출력하게 했는데 예시는 잘 나왔는데 틀렸다고 했다. 보니까 예시가 예외사항을 고려안해도 되는 그런 예시였던 것.... 어쨋든 어렵지만 잘 풀었다!
• 그래프에 관한 문제를 풀때는 stack(dfs), queue(bfs), visited만 생각하면 어떻게 풀 지는 그려질 것 같다.

문제

www.acmicpc.net/problem/17298

처음 작성한 코드(시간초과 ㅋㅋ)

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
result = [-1] * n
stack = []
for i in range(n-1):
    for j in range(i+1,n):
        if arr[i] < arr[j]:
            result[i] = arr[j]
            break
            
print(*result)

코드 리뷰 후

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
result = [-1] * n
stack = []
for i in range(n):
    while(stack and arr[stack[-1]] < arr[i]):
        result[stack.pop()] = arr[i]
    stack.append(i)
    
print(*result)

1. stack에는 오큰수를 찾지 못한 원소의 인덱스를 넣을 것이다.
2. while문을 통해 오큰수를 찾으면 stack에서 하나씩 빼서 오큰수를 result에 저장한다. 

깨달은 점

• 다시 이 문제를 봐도 시간초과 나게 문제를 풀 것 같다 ㅎㅋㅎㅋ 어떻게 스택을 이용해서 풀지..

문제

www.acmicpc.net/problem/4949

처음 작성한 코드

import sys

while True:
    tmp = sys.stdin.readline()
    if tmp == '.\n':
        break
    bracket = []
    for i in tmp:
        if i == '(' or i == '[':
            bracket.append(i)
        elif i == ')':
            if not bracket or bracket.pop() != '(':
                print('no')
                break
        elif i == ']':
            if not bracket or bracket.pop() != '[':
                print('no')
                break
    else:
        print('yes') if not bracket else print('no')

문제

www.acmicpc.net/problem/10828

처음 작성한 코드

import sys
n = int(sys.stdin.readline())
stack = []

for i in range(n):
    tmp = sys.stdin.readline().split()
    if tmp[0] == "push":
        stack.append(tmp[1])
    elif tmp[0] == "pop":
        print(stack.pop()) if stack else print(-1)
    elif tmp[0] == "size":
        print(len(stack))
    elif tmp[0] == "empty":
        print(0) if stack else print(1)
    elif tmp[0] == "top":
        print(stack[-1]) if stack else print(-1)    

문제

www.acmicpc.net/problem/10845

처음 작성한 코드

from collections import deque
import sys

n = int(sys.stdin.readline())
queue = deque()

for i in range(n):
    tmp = sys.stdin.readline().split()
    if tmp[0] == 'push':
        queue.append(tmp[1])
    elif tmp[0] == 'pop':
        print(queue.popleft()) if queue else print(-1)
    elif tmp[0] == 'size':
        print(len(queue))
    elif tmp[0] == 'empty':
        print(0) if queue else print(1)
    elif tmp[0] == 'front':
        print(queue[0]) if queue else print(-1)
    elif tmp[0] == 'back':
        print(queue[-1]) if queue else print(-1)

문제

www.acmicpc.net/problem/10773

처음 작성한 코드

import sys

n = int(sys.stdin.readline())
stack = []

for i in range(n):
    tmp = int(sys.stdin.readline())
    if tmp!=0:
        stack.append(tmp)
    else:
        stack.pop()
print(sum(stack))

다른 분들은 배열을 이용해서 풀었길래 카운트만 가지고 풀어봤습니다.

고려할 점

1. '('을 입력받을 때는 아무조건없이 카운트를 센다.

2. ')'을 입력받을 때는 '('의 카운트값과 비교해서 카운트를 센다. 

   --> 즉, 현재 입력받은 괄호 중에서 여는 괄호보다 닫는 괄호가 많아버리면 그 자리에서 반복문을 끝내고 NO를  출력하게 된다.

다음은 C언어로 작성한 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>

int main()
{
	int T;
	char input[51];
	int i, j, o_cnt = 0, c_cnt = 0;
	scanf("%d", &T);
	for (i = 0;i < T;i++) {
		scanf("%s", input);
		for (j = 0;j < strlen(input);j++)
		{
			if (input[j] == '(') o_cnt++;
			else {
				if ((c_cnt + 1) <= o_cnt) c_cnt++;
				else { c_cnt = -1;break; }
			}
		}
		if (o_cnt == c_cnt) printf("YES\n");
		else printf("NO\n");
		o_cnt = 0;
		c_cnt = 0;
	}
}

다른 풀이법(스택 이용)

1. 입력받은 '('을 스택에 push한다.

2. ')'가 입력받아지면 스택에서 '('를 pop한다.

3. 입력이 끝나고 스택이 비어있지 않으면 "NO"를 출력한다. (VPS라면 스택의 모든 '('가 pop되어야 정상이기 때문)