h32j00

문제

www.acmicpc.net/problem/1744

처음 작성한 코드

import sys

def get_max(arr):
    result = 0
    for i in range(0, len(arr), 2):
        if i < len(arr)-1:
            result += arr[i] * arr[i+1]
        else:
            result += arr[i]
    return result

N = int(sys.stdin.readline())
positive = [] #1초과
negative = [] #0이하, 0은 음수가 하나일 때, 곱해지는게 이득
one = [] #1은 곱해지지않고 더해져야 더 큰 수가 나옴

for i in range(N):
    tmp = int(sys.stdin.readline())
    if tmp <= 0: negative.append(tmp)
    elif tmp > 1: positive.append(tmp)
    else : one.append(tmp)

negative.sort() # 작은 것부터 나열해서 곱하면 제일 커지는 방향
positive.sort(reverse=True) # 큰 것부터 나열해야 제일 커지는 방향

result = get_max(negative) + get_max(positive) + sum(one) # 1은 모두 더해줘야 제일 커짐

print(result)

1. 입력받은 수를 0이하인 수(negative), 1초과인 수(positive), 1인 수들(one)으로 나눈다.
2. 음수는 작은거를 두개 곱하면 더 큰 수를 만들 수 있으니 그냥 sort를, 양수는 큰거 두개를 곱해야 더 큰 수를 만들 수 있으니 reverse=True 옵션을 줘서 정렬했다.
3. 1은 곱하는 것보다 더하는게 더 큰 수를 만들 수 있으니 sum(one)을 통해 입력받은 모든 1을 더해주도록 했다.

깨달은 점

• 이 문제는 그리디를 이용하여 푸는 문제라고 한다. 그리디 잘 모르겠다. 현재 상태에서 제일 좋은 걸 고르면 된다고 하는데 나는 그것도 모르고 현 상태 아니고 모든 상태에서 젤 좋은 값 구하려고 if문을 9138234개 정도 쓰면서 2시간을 날렸다 ㅋㅋ 재밌넹

문제

www.acmicpc.net/problem/2668

처음 작성한 코드

import sys

N = int(sys.stdin.readline())
arr = {i:int(sys.stdin.readline()) for i in range(1, N+1)} 
visited = [False] * (N+1)
result = []

for i in range(1, N+1):
    tmp = []
    if not visited[i]:
        visited[i] = True
        tmp.append(i)
        while tmp:
            if not visited[arr[tmp[-1]]]:
                visited[arr[tmp[-1]]] = True
                tmp.append(arr[tmp[-1]])
            else:
                if tmp[0] == arr[tmp[-1]]:
                    for j in tmp:
                        result.append(j)
                else:
                    for j in tmp:
                        visited[j] = False
                tmp = []

print(len(result))
for i in sorted(result):
    print(str(i))

예제 입력을 기준으로 설명하겠다.

1. 1->3, 3->1 이면 루프가 생기고 이런 루프가 생기면 result에 넣는 방식으로 작성. 5->5도 루프가 생기니까 result에 넣음
2. while문 안에 첫 if-else 문은 현재 번호와 연결되어있는 번호가 방문이 되어있는지를 체크한다. 만약 방문이 안됐으면 방문됐다고 체크하고 tmp에 연결되어있는 번호를 넣는다. 이렇게 계속 하다보면 연결되어있는 모든 노드를 계속 들어가면서 방문하게 된다.
3. else(연결되어있는 번호가 이미 방문됐다면)를 만나서 만약 시작점과 지금 가려는 번호(방문되었다고 체크되서 else로 빠진 번호)가 같으면 루프를 생성하니까 result에 tmp에 있는 번호를 다 넣는다. ex) 1->3->1(arr[tmp[-1]])일때 tmp[0](시작점)과 arr[tmp[-1]](지금 가려던 번호)가 같으니 tmp에 있는 1과 3을  result에 넣는다.
4. 만약 시작번호와 지금 번호가 같지 않다면 방문되어있다는 걸 다시 false로 바꿔줘야 그 뒤 진행을 다시 할 수 있다. ex) 4->5->5 일때 4와 5를 visited false로 해줘야 5->5일때를 잡을 수 있다 왜냐면 제일 큰 for 문에서 not visited상대로만 진행하기 때문에..

코드 리뷰 후

import sys

def DFS(i, start):
    visited[i] = True

    if not visited[arr[i]]:
        DFS(arr[i],start)
    elif visited[arr[i]] and arr[i] == start:
        result.append(i)


N = int(sys.stdin.readline())
arr = {i:int(sys.stdin.readline()) for i in range(1, N+1)}
result = []

for i in range(1,N+1):
    visited = [False] * (N+1)
    DFS(i,i)

print(len(result))
for i in sorted(result):
    print(i)

처음 작성한 코드를 재귀로 푼 모습이다!

깨달은 점

• 마지막에 출력할 때 for문 돌면서 프린트하는 걸 까먹어서 '\n'.join(result)이런식으로 했는데 결과는 똑같던데 백준에서는 틀렸다고 해서 그거때문에 시간 날렸음!!!
• 생각하는데 오래걸리지 않았는데 구현하는데 오래걸렸다 왤까?

문제

www.acmicpc.net/problem/14719

처음 작성한 코드

import sys

h, w = map(int, sys.stdin.readline().split())

block = list(map(int, sys.stdin.readline().split()))
rain = 0

for i in range(w):
    left_max = max(block[:i+1])
    right_max = max(block[i:])
    point = min(left_max,right_max)
    rain += abs(point - block[i])

print(rain)

1. 자신을 포함한 왼쪽에서 제일 높은 블럭을 구한다.
2. 자신을 포함한 오른쪽에서 제일 높은 블럭을 구한다.
3. 1번과 2번에서 구한 블럭 중 더 낮은 블럭을 구한다. 이를 기준으로 빗물이 고일 것이기 때문
4. 현재 인덱스와 더 낮은 블럭(3번에서 구한 블럭)과의 차이를 더해준다.

깨달은 점

• 사실 다른 분 코드 보고 짰다.. 처음에 생각한 방법은 현재 인덱스에서 오른쪽으로 가면서 나보다 높은 블럭을 만나기 전까지 만났던 블럭들의 차이를 더해주는 식으로 짜려고 했는데 생각해보니 그럼 나보다 낮은 애들이 나오면 어쩌지? 라는 생각에 계속 정체됐던 것 같다.. 사람들은 너무 똑똑행!

문제

처음 작성한 코드

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)