one Book a Day

아직 EOF 다루는게 익숙하지 않다. 예외처리에 대해 공부해야 할 듯. from collections import defaultdict while True: try: a=input() b=input() alpha1=defaultdict(int) alpha2=defaultdict(int) ans='' for s in a: alpha1[s]+=1 for s in b: alpha2[s]+=1 s = [] for char in alpha1: if char in alpha2: s.append(char) s.sort() for char in s: ans += char*min(alpha1[char],alpha2[char]) print(ans) except: break

겹치지않으면서 최소 집합과 최대집합의 차이가 최소가 되려면 공차가 1인 등차수열을 이뤄야함. 수열을 제외한 나머지는 K로 나누어 떻어져야 최소. import sys input = sys.stdin.readline N, K = map(int, input().split()) min_gap = K * (K + 1) // 2 if min_gap > N: print(-1) exit() answer = K - 1 if not (N - min_gap) % K else K print(answer)

제한된 선택지에서 선택하는 문제는 dp로 접근하자 import sys input = sys.stdin.readline dp = [[1 if j==0 else i if j==1 else 0 for i in range(2001)] for j in range(15)] # j가 0일때 1이고 아니면 i인데 j가 1일때 i 고 아니면 0이다. for i in range(2,15): for j in range(1,2001): dp[i][j] = dp[i-1][j//2] + dp[i][j-1] for _ in range(int(input())): n,m = map(int,input().split()) sys.stdout.write(str(dp[n][m]) +'\n')

싸이클을 지나는 경로에 속한 노드들에 대해 처리하는 문제입니다. 아직 scc에 대해 익숙하지 못해 TLE상태입니다. 현 로직은 dfs를 통해 방문 횟수를 check해 0, 1, 2상태에 대해서 처리 한 후 cycle에 속한 요소를 찾았다면 각 요소들에 대해 dfs로 순회해주며 이미 -1 처리되었다면 return하는 백트래킹까지 해주었습니다. 아직 7번째 test set에서 TLE상태라 조금 더 보완하겠습니다. import sys input = sys.stdin.readline # 1부터 탐색. cycle생기면 cycle에 포함되는 요소 하나 check. def dfs(cur_node, path): if answer[cur_node] < 2: answer[cur_node] += 1 for next_node..

실패한 코드입니다. 최초는 규칙대로 gcd를 모두 구해가며 진행했으나 TLE가 납니다. 때문에 소인수분해를 해서 각 요소를 제거해가며 풀이하려 했으나 아직 로직이 완벽하지 못합니다. 추후 보완하겠습니다. import sys input = sys.stdin.readline from collections import defaultdict for test in range(int(input())): n = int(input()) a = list(map(int, input().split())) cnt = 0 primes = defaultdict(int) for i in range(n): tmp = a[i] for j in range(2, tmp + 1): if tmp == 1: break if not tmp % ..

구현중 가장 귀찮은 구현이 배열 회전인것같다.. 확산, 회전순으로 과정압축없이 진행 위는 내코드 아래는 1등코드 1등코드는 내 코드보다 10배 빠르다. 차이점은 dusts를 배열로 관리했다는 것. 불필요한 과정이었던것같다. import sys input = sys.stdin.readline from collections import deque def rotate_dust(): up_cycle = deque() down_cycle = deque() up_cycle_down, down_cycle_up = air_clear[0][0], air_clear[1][0] # 0, 공기청정기 x 작은 좌표, 좌, 우 -> rotate(-1) for i in range(C): up_cycle.append(matrix[0..

암호문에서 16진수로 표현된 바코드를 찾아 2진수로 변환, decode 규칙에 따라 해석한 10진수가 암호의 조건에 맞으면 암호값을 산출하는 문제입니다. input값을 정제하는 것부터 매우 어려웠습니다. 결국 핵심은 2진수 값을 구하면 0,1,0,1의 비율을 찾아 매칭시키는 것 입니다. 웃긴건 112자리 안에 56자리 암호가 숨어있을수도 있으니 조심하시면 됩니다. import sys sys.stdin = open('input.txt') # 알파뱃이면 10 + 그 번호 즉 16진수를 10진수로 치환하는 함수. def get_val(ch): val = (ord(ch) - ord('A')) + 10 if ord(ch) > ord('9') else ord(ch) - ord('0') return val # 남의 ..

카카오 블라인드 1차 6번 효율성 문제. 구간 합을 이용해 갱신하는 방법으로 그때 아이디어만 얻어두었다가 드디어 해결했다. 양 끝에만 적어두고 dp로 누적값 배열을 만든 후 최종 배열은 원배열 + 변화량 배열의 합으로만 구하는 방법. 프로그래머스에 이번년도 문제 올라오면 다시 풀어보자. 사람들이 웰노운 웰노운 거리더니.. 여튼 좋은 방법론을 얻었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) H = list(map(int, input().split())) save = [0] * (N+1) for _ in range(M): a, b, k = map(int, input().split()) save[a-1] += k save[..

결국 조사한 지점은 다시 조사하지 않아도 된다는 점. 누적되는 것은 좀 더 긴 값으로 갱신하면 된다는 점. 결국 '최장거리' 경로를 구하는 문제이고 이는 다익스트라의 dists 배열처럼 더 크거나 더 작은 값으로 갱신되는 구조를 띈다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def dfs(x, y): # 이미 다른 조사에서 완료된 지점이면 패스 if dp_dist[x][y]: return dp_dist[x][y] # 조사 안됐으면 1부터 시작. dp_dist[x][y] = 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

파라매틱 서치. k번 이상 자를 수 있는지 결정하는 문제. 자주나오는데 아직 좀 사고가 더디다. import sys input = sys.stdin.readline def is_minimum(mini): left = 0 cnt = 0 for right in cut_points: if right - left >= mini: left = right cnt += 1 if cnt > k: return True return False N, M, L = map(int, input().split()) cut_points = [int(input()) for _ in range(M)] + [L] for _ in range(N): k = int(input()) # M개의 지점 중 k개 선택. 사잇값의 최솟값이 가장 큰. ..