내 인생 이대로 ㅈ될 수 없다

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

내 풀이

from collections import deque

def solution(cacheSize, cities):
    time=0
    cache = deque()
    
    cities=[i.lower() for i in cities]
    
    
    for i in cities:
        if len(cache) <cacheSize:
            if i in cache:
                time +=1
                cache.append(i)
                cache.remove(i)
            else:
                cache.append(i)
                time+=5
        else:
            if i in cache:
                time+=1
                cache.append(i)
                cache.remove(i)
                
            else:
                cache.append(i)
                cache.popleft()
                time+=5
        
        
        
                
            
    return time

다른사람의 풀이

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

maxlen으로 길이를 정해줄수있다는것을 배웠다.

https://school.programmers.co.kr/learn/courses/30/lessons/118667

내 풀이

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    sumq1= sum(q1)
    target = (sum(q1) + sum(q2)) /2
    count=0
    
    while q1 and q2:
        if sumq1 == target:  
            return count
        elif sumq1 > target:  
            sumq1 -= q1.popleft()
        else:  
            q1.append(q2.popleft())
            sumq1 += q1[-1]
            
        count += 1

    return -1

deque를 이용한 평범한 풀이다. 

최초에는 sumq를 이용하지 않고 매번 sum을 구해줘서 했는데 그러니까 시간초과가 나더라.

그래서 따로 구해주고 +-만 해줬다.

다른 풀이를 보니까 q1 q2 둘다 append pop해줬던데 그럴필요없이 비교할 하나만 정해서

비교군이 타겟보다 크면 비교군에만 빼주고 다른 한쪽은 가만히 두는게 더 나은거 같다.

다른사람의 풀이

from collections import deque

def solution(queue1, queue2):
    qu_1 = deque(queue1)
    qu_2 = deque(queue2)
    sum_1 = sum(qu_1)
    sum_2 = sum(qu_2)

    for i in range(len(queue1) * 3):
        if sum_1 == sum_2:
            return i
        if sum_1 > sum_2:
            num = qu_1.popleft()
            qu_2.append(num)
            sum_1 -= num
            sum_2 += num
        else:
            num = qu_2.popleft()
            qu_1.append(num)
            sum_2 -= num
            sum_1 += num
    return -1

https://dev-dain.tistory.com/228

최초에 코테칠때 이 두문제 풀고나니 시간을 다써서 아무것도 못했었던 기억이난다..

발전을 하긴하는거같다 이 두문제 풀고나니까 동기부여를 조금 받은거 같다

이 두문제처럼 아주 어려운 문제들도 나중에 보면 그땐 그랬지 할 수 있었으면 한다.

https://school.programmers.co.kr/learn/courses/30/lessons/118666?language=python3 

내 풀이

#1번 라이언(R),튜브(T)
#2번 콘(C),프로도(F)
#3번 제이지(J),무지(M)
#4번 어피치(A),네오(N)

from collections import defaultdict

def solution(survey, choices):
    answer=''
    candi = defaultdict(int)
    
    for s,c in zip(survey,choices):
        if c<4:
            candi[s[0]] +=(4-c)
        elif c>4:
            candi[s[1]] +=c-4
    print(candi)
    
    answer +='R' if candi['R'] >= candi['T'] else 'T'
    answer +='C' if candi['C'] >= candi['F'] else 'F'
    answer +='J' if candi['J'] >= candi['M'] else 'M'
    answer +='A' if candi['A'] >= candi['N'] else 'N'
    
    
    return answer

defaultdict를 이용한 풀이다.

아니면 set에다 기본 값 주고 시작해도 될듯.

다른사람의 풀이

from collections import defaultdict

def solution(survey, choices):
    indicator = [('R', 'T'), ('C', 'F'), ('J', 'M'), ('A', 'N')]
    answer = ''
    personality = defaultdict(int)
    for s, c in zip(survey, choices):
        if c < 4:
            personality[s[0]] += (4 - c)
        elif c > 4:
            personality[s[1]] += (c - 4)
    for i in indicator:
        if personality[i[0]] >= personality[i[1]]:
            answer += i[0]
        else:
            answer += i[1]
    return answer

사실 이 문제 코테를 처음 준비하기 시작했을 때 무턱대고 지원했던 카카오 인턴 1차 문제에서 어렵게 풀었었던 기억이있다.

그때 이 문제푸는데 2시간 걸렸었는데 참 시간이 많이 지났음을 느낀다..

https://school.programmers.co.kr/learn/courses/30/lessons/12978

내 풀이

1.

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

def solution(N,road,K):
    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    distance[1]=0
    for r in road:
        graph[r[0]].append((r[1],r[2]))
        graph[r[1]].append((r[0],r[2]))
    def ekdlrtmxmfk():
        q=[]
        heapq.heappush(q,(0,1))
        
        while q:
            dist,now = heapq.heappop(q)
            #print((dist,now))
            #print(dist)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q,(cost,i[0]))
    ekdlrtmxmfk()
    #print(graph)
    #print(distance)
    return len([x for x in distance if x<=K])

2.

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

def solution(N,road,K):
    graph = [[] for _ in range(N+1)]
    distance = [INF] * (N+1)
    distance[1]=0
    for r in road:
        graph[r[0]].append((r[2],r[1]))
        graph[r[1]].append((r[2],r[0]))
    def ekdlrtmxmfk():
        q=[]
        heapq.heappush(q,(0,1))
        
        while q:
            dist,now = heapq.heappop(q)
            #print((dist,now))
            #print(dist)
            if distance[now] < dist:
                continue
            for i,j in graph[now]:
                if i+dist < distance[j]:
                    distance[j] = i+dist
                    heapq.heappush(q,(dist+i,j))
    ekdlrtmxmfk()
    
    return len([x for x in distance if x<=K])

대표적인 다익스트라 알고리즘이다.

너무 오랜만에 풀어서 진짜 한참 헤맸다..

처음에는 visit를 만들어서 풀었는데, 시간초과 나서 heapq을 썼다.

다익스트라 알고리즘이 적용가능할 때는 음의 값이 없을때임을 명심해야한다.

1 번풀이 2번풀이 둘다 비슷한데 1번은 이코테의 내용을 참고했다.

1번이 좀 더 직관적인 풀이법같다.

두 풀이법의 가장 큰 차이점은, (노드,가중치 ) 의 순서가 다르다.

다른사람의 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/76502

내 풀이

사람마다 정말 다양한 정답이 나올 수 있을거 같은 문제이다.

그렇지만 대부분은 스택을 썼을꺼라 생각하는데, 오랜만에 풀어서 그런지 너무 더럽게 푼거같다;

다른사람의 풀이

def is_valid(s):
    stack = []
    for ch in s:
        if not stack:
            stack.append(ch)
        elif stack[-1] == '(':
            if ch==')': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '{':
            if ch=='}': stack.pop()
            else: stack.append(ch)
        elif stack[-1] == '[':
            if ch==']': stack.pop()
            else: stack.append(ch)

    return False if stack else True

def solution(s):
    answer = 0
    for i in range(len(s)):
        answer += is_valid(s[i:]+s[:i])
    return answer

정처기 실기를 치고 공부하고 시험치고 온다고 한동안 공부를 소홀히 했는데 남은 방학동안 열심히 해봐야 겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/1844

내 풀이

from collections import deque

def solution(maps):
    dy = [-1,1,0,0]
    dx = [0,0,-1,1]
    
    N = len(maps)
    M = len(maps[0])
    
    queue=deque([(0,0)])
    
    while queue:
        x,y = queue.popleft()
        if (x,y) ==(N-1,M-1):
            return maps[x][y]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if maps[nx][ny]==1:
                    maps[nx][ny] = maps[x][y]+1
                    queue.append((nx,ny))
                    
    return -1

https://playedenough.tistory.com/83?category=1050629 

이거랑 완전 동일하다. 

다른사람의 풀이