어디까지 갈 수 있을까?

[배열돌리기 2] 문제링크 https://www.acmicpc.net/problem/169267 배열돌리기 1을 할 때는 원본 배열을 copy해서 돌렸는데 한번 돌릴때마다 계속 배열을 복사해야 하다보니 시간이 오래걸렸다. 배열돌리기 2에서도 배열돌리기 1에서 하던 로직으로 pypy3는 통과했지만, python에서는 시간초과가 났다. 그래서, queue를 사용해서 1차원적으로 접근해 돌릴 수 있는 만큼 다 돌리고 원본배열에 반영했는데 훨씬 쉬웠다. queue같은 경우 linkedlist로 구현돼 맨앞이나 맨뒤에서 append나 pop이 일어난다고 해도 O(1)안에 연산이 가능해 시간도 많이 줄었다. python으로도 268ms에 맞았습니다 판정이 났다. [배운점] while과 queue의 조합이 너무 좋았..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/67258 1. 최소 길이를 구할 땐 투포인터 알고리즘을 생각해보자 2. 0 인덱스를 갖는 값은 미리 넣어준다 [답코드] from collections import defaultdict def solution(gems): gems_len=len(set(gems)) dic=defaultdict(int) dic[gems[0]]=1 answer=[] start=0; end=0 while start

문제링크 https://programmers.co.kr/learn/courses/30/lessons/72412 0. 딕셔너리에 문자열 모두 붙여서 key값으로 넣기 1. 컴비네이션으로 내가 들어갈 수 있는 모든 경우의 수를 만들어 내 int 값을 넣기 2. 정렬된 값에서 이분탐색으로 위치 찾기 [답코드] from collections import defaultdict from itertools import combinations def solution(info, query): dict=defaultdict(list) for i in info: i = i.split() dict_key=i[:-1] dict_val=int(i[-1]) for size in range(0, 5): for c in combina..

문제링크 https://www.acmicpc.net/problem/1062 1. set()은 문자열로 넣어도 원소 하나하나로 접근한다는 점 2. combination에 현재 list 길이보다 큰 값이 들어오면 combination 함수가 돌아가지 않는다는 점 3. set() 연산 : |= 합집합, - 차집합 을 배웠다. [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import sys from itertools import combinations input = sys.stdin.readline n, k = map(int, input().split()..

문제링크 https://www.acmicpc.net/problem/16940 order 배열에 노드별 우선순위를 담은 다음 그를 이용해 graph를 정렬하는 문제이다 order의 인덱스 : 노드 번호 order의 value : 우선순위 sort() 함수가 굉장히 다방면으로 쓰일 수 있어 신기했다 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import sys from collections import deque input=sys.stdin.readline def bfs(s): visited=[False]*(n+1) ..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43164 [답코드] def dfs(cand, visit, target): global n, answer if len(visit) == n: answer.append(visit+[target]) return for i, v in enumerate(cand): if v[0] == target: dfs(cand[:i] + cand[i + 1:], visit + [v[0]], v[1]) def solution(tickets): global n, answer n = len(tickets) answer = [] for i, v in enumerate(tickets): if v[0] == "ICN": dfs(tick..

문제링크 programmers.co.kr/learn/courses/30/lessons/42579 1. sort() 활용 잘하기, -붙이면 reverse=True 와 같은 역할 함 [답코드] def solution(genres, plays): answer = [i for i in range(len(genres))] dict = {} for i in range(len(genres)): if genres[i] not in dict: dict[genres[i]] = plays[i] else: dict[genres[i]] += plays[i] answer.sort(key=lambda x: (-dict[genres[x]], -plays[x], x)) genre_dict = {} ret=[] for j in answ..

문제링크 programmers.co.kr/learn/courses/30/lessons/42890 [정리] 1. 전치행렬 만들기 list(map(list, zip(*relation))) 2. append는 ()안 요소 전체를 추가 하지만 extned는 ()안 요소 하나하나를 접근해 배열에 추가 3. set()으로 만들 값은 변형 불가능한 값이어야 하기 때문에 원소들을 tuple로 변형시킨다 4. 최소성 만족을 위해 set(j).issubset(i) ex) j=[1,2,2] i=[1,2,3] 일 때도 = (하위집합 j에 중복되는 원소가 있을 때도) 상위집합의 부분집합으로 인정하기 위해 set(j)를 붙여주는 걸로 추정 [답코드] from itertools import combinations def solut..