내 인생 이대로 ㅈ될 수 없다

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/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가 될 수가 없다.

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

다른사람의 풀이

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

내 풀이

def solution():
    n = int(input())
    lis=list(map(int,input().split()))
    for i in range(1,n):
        #(print(f'lis[{i}]={lis[i]},lis[{i-1}]+lis[{i}]={lis[i-1]+lis[i]}'))
        lis[i] = max(lis[i],lis[i-1]+lis[i])
        
    #print(lis)
    print(max(lis))
solution()

일반적인 dp랑 다르게 굳이 memoization 리스트를 선언할 필요가 없다.

결국 핵심은 연속적인 수들의 합이기 때문이다. 

다른사람의 풀이

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

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

def solution():
    n,m = map(int,input().split())
    graph=[list(input().strip()) for _ in range(n)]
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    def bfs(x,y):
        visit = [[0]* m for _ in range(n)]
        visit[x][y]=1
        q = deque([(x,y)])
        
        
        
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0>nx or nx>=n or 0>ny or m<=ny or graph[nx][ny]=='W' or visit[nx][ny]  :
                    continue
                
                visit[nx][ny] = visit[x][y] + 1             
                q.append((nx,ny))
        
        return visit[x][y]-1
    max_time=0  
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='L':
                if 0<=i-1 and i+1<n:
                    if graph[i-1][j]=='L' and graph[i+1][j]=='L':
                        continue
                if 0<=j-1 and j+1<m:
                    if graph[i][j-1]=='L'and graph[i][j+1]=='L':
                        continue
                max_time=max(bfs(i,j),max_time)
    print(max_time)
                
solution()

문제 자체는 진짜 평이했는데 그놈의 시간초과가 나를 괴롭혔다.

당연히 pypy로 풀면 해결되지만 코딩테스트에서는 pypy를 지원하지 않는 경우가 많아서 꼭 파이썬으로 풀고 싶었다.

조건을 조금 더 생각해보니, 그래프에서 양 옆이 모두 육지인 경우는 절대 최대값일 수가 없었다.

가령

LLW

LWW

LLL

이런 그래프가 있다하면

그래프에서 (0,2)인 지점은 절대 최대값일 수가 없다 왜?

내 옆에 땅을 거쳐가면 반드시 현재 위치보다 더 긴시간이 걸릴테니까

이런 문제의 핵심은 적어도 파이썬으로 풀때는, 숨겨진 조건을 찾는것인거 같다.

다른사람의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
bomool = []
land = []
for i in range(N):
    temp = list(map(str, input()))
    for j in range(len(temp)):
        if temp[j] == 'L':
            land.append((i, j))
    bomool.append(temp)

dr = [-1, 0, 1, 0]  # 행 상 우 하 좌
dc = [0, 1, 0, -1]  # 열 상 우 하 좌


def bfs(r, c):
    queue = deque([[r, c, 0]])
    visited[r][c] = True
    while queue:
        r, c, distance = queue.popleft()

        for i in range(4):

            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M or visited[nr][nc] or bomool[nr][nc] == 'W':
                continue

            visited[nr][nc] = True
            queue.append([nr, nc, distance + 1])

    return distance


max_ = 0
for i in range(len(land)):
    visited = [[False] * M for _ in range(N)]
    distance = bfs(land[i][0], land[i][1])
    if max_ < distance:
        max_ = distance

print(max_)

https://ji-gwang.tistory.com/m/406