내 인생 이대로 ㅈ될 수 없다

https://www.acmicpc.net/problem/2504

내 풀이

def solution():
    n = input().strip()
    stack = []
    sums=1
    result=0
    
    for i in range(len(n)):
        if n[i] == '[':
            sums *=3
            stack.append(n[i])
            
        elif n[i]=='(':
            sums *=2
            stack.append(n[i])
            
        elif n[i] == ']':
            if len(stack) == 0 or stack[-1] =='(':
                result=0
                break

            elif n[i-1] =='[':
                result += sums
                
            stack.pop()
            sums //=3
        else:
            if len(stack)==0 or stack[-1]=='[':
                result=0
                break
            elif n[i-1]=='(':
                result +=sums
            stack.pop()  
            sums //=2
    
    if stack:
        result= 0
    
    print(result)
(solution())

다른사람의 풀이

1학년때 이거관련해서 과제한적 있었는데 이렇게 오래걸릴줄 상상도 못했다;

최초에 고려하지 못했던 부분이 약 2개정도 있는데

첫째, pop은 무조건 해야한다. 처음에는 맞는 괄호만 나올때만 pop했는데 그러면 나중에 쌓여서 안됨 -

둘째,여는 괄호만 나올때도 고려해야한다 그거 고려안해서 10분동안 잡고있었음

https://www.acmicpc.net/problem/1939

내 풀이

import sys
from collections import deque

input = sys.stdin.readline
    
def solution():
    n,m = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))
    start,end = map(int,input().split())
    
    
    
    def bfs(k):
        q = deque([start])
        visit=[0]* (n+1)
        visit[start]=True
        
        while q:
            x = q.popleft()
            for i,j in graph[x]:
                if not visit[i] and j>=k:
                    visit[i]=1
                    q.append(i)
        return True if visit[end] else False
    
    def binary():
        answer=0
        left,right =0,int(1e9)
        
        while left<=right:
            mid = (left+right)//2
            if bfs(mid):
                answer = mid
                left = mid +1
            else:
                right = mid -1
        print(answer)
    binary()
solution()

개인적으로 좋은문제라고 생각했다!

bfs와 이진탐색의 결합이였는데 문제자체가 풀고나니 어렵지는 않았는데(전형적인 허세) 풀이과정을 생각해내기가 쉽지않아

구글링 좀 해보았다

다른사람의 풀이

https://velog.io/@ckstn0778/백준-1939번-중량제한-1-Python

https://www.acmicpc.net/problem/10816

내 풀이

from collections import defaultdict

def solution():
    n=int(input())
    lists = list(map(int,input().split()))
    m = int(input())
    candi = list(map(int,input().split()))
    number_of_candi=defaultdict(int)
    
    for i in lists:
        number_of_candi[i] +=1
    for i in candi:
        if i in number_of_candi:
            print(number_of_candi[i],end=' ')
        else:
            print(0,end=' ')
        
        
    
solution()

딱 보자마자 생각난건 defaultdict였다.

하나 실수한게 candi에 있는걸 lists 로 추적하면 갯수가 안맞는다. 가령 10을 추적하면 1번 밖에 안나올것이다.

CANDI와 Lists에 공통적으로 존재하는 숫자의 갯수를 찾는거기때문에

lists에 있는걸 defaultdict에 넣고, 그걸 반대로 candi로 추적해야한다.

다른사람의 풀이

https://www.acmicpc.net/problem/1806

내 풀이

시도1

import sys
input = sys.stdin.readline
def solution():
    n,s = map(int,input().split())
    candi = list(map(int,input().split()))
    
    answer=[]

    for i in range(len(candi)):
        m_sum=0
        count =1
        m_sum += candi[i]
        for j in range(i+1,len(candi)):
            if m_sum == s:
                answer.append(count)
                break
            elif m_sum > s:
                break
            m_sum += candi[j]
            count +=1
    return min(answer)
    



print((solution()))

사실 아무생각없이 이중루프를 돌렸는데 이제와서 생각해보니까 안되는게 당연하다. 항상 문제조건을 보고 문제를풀자

두번째시도

def solution():
    n,s =  map(int,input().split())

    lists = list(map(int,input().split()))
    sum_parts= 0
    starts=0
    ends=0
    answer=int(1e9)
    while True:
        if sum_parts >= s:
            answer = min(answer,ends-starts)
            
            sum_parts -=lists[starts]
            starts +=1
        else:
            if n==ends:
                break
            sum_parts +=lists[ends]
            ends +=1

    print(0 if answer==1e9 else answer)
    
    
solution()

두번째는 시간초과를 막기위하여 이중루프를 없앴다. 풀다보니 예전에 부분합 풀었던 기억이 있어서 더듬더듬 풀었다..

찾아보니 투 포인터라는 알고리즘이라고 한다.

다른사람의 풀이

https://www.acmicpc.net/problem/1238

내 풀이

시도1

def solution():
    INF = int(1e9)
    n,m,x=map(int,input().split())
    time_list=[]
    result=[[]]
    
    graph = [[] for _ in range(m+1)]
    
    for _ in range(m):
        a,b,c= map(int,input().split())
        graph[a].append((b,c))
      
    def get_smallest_node():
        min_value = INF
        index = 0
        for i in range(1, n+1):
            if distance[i] < min_value and not visited[i]:
                min_value = distance[i]
                index = i
        return index
    def ekdlrtmxmfk(start):
        distance[start]=0
        visited[start]=1
        
        for j in graph[start]:
            distance[j[0]]=j[1]
        for _ in range(n-1):
            now = get_smallest_node()
            visited[now] = True
        
            for j in graph[now]:      
                cost = distance[now] + j[1]

                if cost<distance[j[0]]:
                    distance[j[0]] = cost
        return distance
    for i in range(1,n+1):
        distance = [INF] * (n+1)
        visited = [0] * (n+1)
        result.append(ekdlrtmxmfk(i))

    for i in range(1, n+1):
        time_list.append(result[i][x] + result[x][i])
    
    print(max(time_list))

시간초과가 났다. 특정 한 점에서 다른 모든점까지의 거리를 구하는 부분에서 다익스트라는것을 알았지만 단 한번도 다익스트라 문제를 풀면서 heapq를 사용하지 않은적이 없어서 문득 그냥 구현하면 통과가 될까싶어 한번해보았다.

시도2

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)


def solution():
    n,m,x = map(int,input().split())
    graph =[[] for _ in range(n+1)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
    
    def ekdlrtmxmfk(start):
        q = []
        heapq.heappush(q,(0,start))
        distance[start] = 0

        while q:
            dist,now = heapq.heappop(q)
            
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]]=cost
                    heapq.heappush(q,(cost,i[0]))
        return distance
    
    result = [[]]
    dis =[]

    for i in range(1,n+1):
        distance= [INF] * (n+1)
        result.append(ekdlrtmxmfk(i))
    for i in range(1,n+1):
        dis.append(result[i][x]+result[x][i])
    print(max(dis))
    

solution()

원리는 같은데 heapq를 사용한 방법이다. 

다른사람의 풀이

최근에 기사시험을 시작으로 본격적인 취준이 시작되었다. 아직 한학기가 남긴했지만 지원가능한 회사에 꽤나 많이 지원했는데(다행히도 서류는 꽤 많이 붙었다) 저번주부터 코딩테스트가 시작되었다. 18학점을 들어야하는 상황이라 학교 중간고사도 겹치다보니 쉽지않다..

하루에 하나정도는 문제를 꼭 풀어야겠다 + sql도

내 풀이

def solution():
    n ,m = input().split()
    
    graph = [list(map(int,input().split())) for _ in range(int(m))]
    
        
    condi = {5:2,2:5,1:1,8:8}
    
    answer = [[0]*int(m) for _ in range(int(m))]
    for i in range(int(m)):
        for j in range(int(m)):
            if n == 'L' or n == 'R':
                if graph[i][j] in condi.keys():
                    answer[i][int(m)-j-1] = condi[graph[i][j]]
                else:
                    answer[i][int(m)-j-1]='?'
            elif n=='U' or n=='D':
                if graph[i][j] in condi.keys():
                    answer[int(m)-i-1][j]=condi[graph[i][j]]
                else:
                    answer[int(m)-i-1][j]='?'
    for i in answer:
        for j in i:
            print(j,end=' ')
        print('')
        
        
        
            
                    
                
solution()

일단 문제 자체가 성립하려면 조건이 필요하다.

1) 전자식이라는 조건이 없다. 근데 숫자가 전자식이 아니면 2를 뒤집으면 5가 될 수가 없다.

그냥 전자식이라고 가정하고 풀었다.

다른사람의 풀이