Python78 [Python] Trie 자료구조 Trie(트라이) 자료구조는 문자열 집합에서 키를 효율적으로 저장하고 조회하는데 사용된다. 스펠 체커나 자동완성 기능에서 사용된다. 파이썬에서는 딕셔너리 자료구조를 이용해 쉽게 구현할 수 있다. insert (단어 삽입) 단어의 키(문자)가 커서에 존재하지 않는 경우 해당 키로 딕셔너리를 생성하고, 커서 위치를 업데이트 해준다. 단어 삽입이 완료되면 * 키를 생성해서 끝임을 표기한다. search (단어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 False를 반환하고, 커서 위치를 업데이트 해준다. 단어 순회가 완료되었을 때 * 키가 커서에 있을 경우 True를 반환하고 없을 경우 False를 반환한다. startswith (접두어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 Fals.. 2021. 10. 10. [Python] 전화번호 목록 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr Point 해쉬를 이용한 문제로, 트라이(Trie) 자료구조를 응용해서 풀어보기 좋은 문제이다. 실제로 많은 분들이 리스트와 반복문을 이용해서 풀고 있는데, 만약 문제의 제약조건이 타이트했다면 해결하기 어려울 것이다. Tip 정렬을 하지 않는 것이, 최악 테스트케이스에서 수행 시간이 더 빠르다. 따라서 prefix+a 문자열이 이미 트라이에 있을 때, pre.. 2021. 9. 25. [Python] LongestPassword https://app.codility.com/demo/results/trainingPB6C9Y-2CD/ Test results - Codility You would like to set a password for a bank account. However, there are three restrictions on the format of the password: it has to contain only alphanumerical characters (a−z, A−Z, 0−9); there should be an even number of letters; there should be an app.codility.com Point 제시된 조건에 따라 validation check를 수행한다 스플릿 하여 fo.. 2021. 7. 18. [Python] 20056. 마법사 상어와 파이어볼 www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net Point 첫 입력에서 서로 다른 두 파이어볼 위치가 같은 경우는 없음 파이어볼 질량이 0 이 되면 소멸 Tip 2차원 리스트 배열을 선언하여 이동이 끝난 뒤 파이어볼 합치기/분열을 연산 파이어볼의 방향을 연산할 때, 총합이 짝수/홀수냐로 모두 짝수/홀수인지 아닌지를 판별하면 안된다. 짝짝홀홀일 때 총합은 짝수이기 때문이다. 메모리 (제한: 512MB) 138280 KB .. 2021. 4. 24. [Python] 20057. 마법사 상어와 토네이도 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net Point 토네이도가 (0,0) 도달 시 종료 한칸 움직일 때마다 모래를 퍼트림 Tip 반시계 방향 회전가능할 때까지 전진 시간 절약을 위해 현 위치의 모래가 0이 아닐때만 (A[y][x] != 0) 모래를 퍼트림 메모리 (제한: 512MB) 132984 KB 시간 (제한: 1초) 476 ms 결과 100% import sys from collections import deque.. 2021. 4. 24. [Python] 16234. 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net Point 시작점을 기준으로 bfs를 통해 연합국가의 좌표를 탐색하고, 평균을 연산한다. 실제 값 반영은 이동에서 수행한다. Tip bfs의 세번째 반환값으로 flag를 세워서 인구이동이 필요없는(길이가 1)인 국가를 이동대상에 포함하지 않으므로서 연산량을 대폭 줄인다 check 이차원 배열을 선언해 한번 연합이 탐지된 국가는 모두 True 표시하여 bfs 연산이 필요없도록 한다 메모리 (제한: .. 2021. 4. 24. [Python] 19238. 스타트 택시 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net Point 처음엔 매 승객마다 최단거리를 구해줬고 시간초과가 났다. 그럴 필요 없이 현재 택시 위치 기준으로 맵의 최단거리를 구하고 Pop(index) 를 이용해서 연산을 반복한다. 메모리 (제한: MB) 124568 KB 시간 (제한: 초) 204 ms 결과 100% def shortest_path(taxi): global n dist = [[-1]*n for _ in .. 2021. 4. 23. [Python] 이차원 배열과 연산 www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 포인트 두자리 이상의 수에 대해서 정렬하는 것을 고려 100초까지 확인해야 하므로 101번까지 반복해야 함 Tip 내장함수 zip(*arr) 을 사용하여 세로 줄에 대해서 정렬을 연산한다. Defaultdic 과 DeepCopy를 사용한다. 시간을 줄이기 위해 2차원 배열로 연산을 해보자 메모리 (제한: 512 MB) 129132 KB 시간 (제한: 0.5 초) 300 ms 결과 100% from .. 2021. 4. 21. [Python] 17142. 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 아무리 수정해도 계속 시간초과 됨 ㅠㅠ 다음에 재도전 메모리 (제한: MB) 0 KB 시간 (제한: 초) 0 ms 결과 시간초과 import itertools def bfs(_lst,_dist): global n,answer,vacumm lst = list(_lst) cnt = 0 infected = 0 for i in range(len(lst)): _dist[lst[i][0]][lst[i][1]] = 0 while T.. 2021. 4. 20. 이전 1 2 3 4 ··· 9 다음 728x90 반응형