주어진 문자열 중에서 K개의 문자를 제거해서 숫자를 생성했을 때 가장 큰 수를 만들어 내는 문제이다. 내가 생각한 방법은 K개를 기준으로해서 최대한 제거할 수 있는 경우의 수 중에서 가장 큰수를 먼저 찾는 방식이다. 먼저 stack을 이용해서 stack에 값이 존재하는 경우에는  1) 최대 제거 갯수가 남아있는지 => K 가 0보다 클 때만 문자열 제거가 가능!2) stack에 들어있는 값이 내가 조회한 값보다 작다면 제거, 아니면 일단 현재 값도 stack에 추가(제거 후보로 등록) 오늘은 한번 enumerate를 사용해봤다.이 함수는 python에서 list 조회 시에 index와 함께 조회하는 것으로 익혀두고 사용하면 도움이 될 것 같다!!def solution(number, k): stack..

오늘의 구명보트 문제는 테스트 케이스를 보고 접근해서 잘못된 방향으로 풀고 다시 사고를 고쳐나가는 과정이 있었다. 우선 테스트케이스만 봤을때는 오름차순으로 정렬하고 앞에서 둘의 합이 최대를 넘지 않으면 pop 두번, 넘는 순간부터는 한번씩 pop을 하자고 생각했는데 무엇보다 시간초과가 발생했고 아래의 케이스에서는 최적의 값을 도출할 수 없었다. + 엣지 케이스까지는 아니지만 내 풀이의 반례)[20,30,50,60,70,80] 의 경우 => 4가지 를 만족해야하지만 내 풀이대로라면 (20,30), 50, 60, 70, 80 으로 5가지라는 오답이 나온다. 따라서 sorting을 한 후에 투포인터로 접근해보았다.최대한 limit에 가깝게 만드는게 좋으니 양 끝값을 더해서 limit을 초과한다면 오른쪽 끝, ..

화 / 목은 아무래도 늘어지는 날인거 같다 >. 오늘의 코딩테스트 : 단지 번호 붙이기 map 이 등장하고 그래프 갯수를 세며 하나의 그래프 내에 들어있는 노드의 수를 계산하는 전형적인 DFS 문제이다.DFS, 재귀함수의 경우 메모리 관리를 제대로하지 않으면 C 같은 경우 stack에 함수에 대한 정보 및 지역변수가 계속 쌓여서 stack overflow를 발생시키기도 한다.   늘 하는대로 DFS는 1. dy, dx 설정해서 map 탐색하기2. 최단거리를 구할 때는 map 정보를 바꿔서 가장 마지막에 누적해서 적기도하지만 오늘은 그래프 내의 노드의 갯수 즉, 재귀가 얼마나 발생했는지를 계산해야 하므로 cnt에 이전의 dfs에서 return한 값을 누적하도록 계산한다.3. 출력 방식을 고려하여 반드시 s..

다시 오늘 해야할 일에 집중하자!!알바 갔다가 조금 뒹굴뒹굴하고 나니 벌써 하늘이 어둡다니!!!!  오늘의 문제는 모음사전이다.제일 처음 들었던 생각과 또 좀 더 고민해서 풀었던 풀이 두가지를 가지고 글을 쓰고자한다. 일단 먼저 문자열 길이가 최대 5개 그리고 종류도 5개!!이 경우 문자열 나열과 관련해서 떠오르는 키워드는 순열, 조합 (itertools) 가 사용이 가능하다는 것이다!! 근데 오늘 문제의 경우에는 고등학교때 함수의 갯수를 구하는 방법으로 배웠던 중복조합이 필요하다.( 정의역의 원소의 갯수가 r개, 치역의 원소의 갯수가 n개일 때 => n^r) python의 itertools에서는 product라는 함수로 지원한다. import itertoolsdef solution(word): a..

from typing import Listclass WordFilter: def __init__(self, words: List[str]): self.prefix_suffix_map = {} for index, word in enumerate(words): length = len(word) for i in range(length + 1): prefix = word[:i] # 가능한 모든 접두사 for j in range(length + 1): suffix = word[j:] # 가능한 모든 접미사 self.pre..

어제 풀었던거랑 완전 동일한 방식으로 금방해결할 수 있었다.역시 hash 짱 -> O(1)로 key에 해당하는 것의 갯수를 출력할 수 있다는 점에서 너무 편리하다!! import syssys.stdin = open("input.txt")M = int(input())ms = list(map(int, input().split(" ")))target = {}for i in ms: if i in target: target[i] += 1 else: target[i] = 1N = int(input())ns = list(map(int, input().split(" ")))answer = []for j in ns: if j in target: answer.appen..

오늘은 백준 문제를 푸는 날~!오랜만에 입출력까지 고려하니까 머리가 아프군... import syssys.stdin = open("input.txt", "r")N = int(input())target = {}arr = list(map(int, input().split(" ")))for i in arr: target[i] = 1#print(arr)#print(target)M = int(input())answer = []arr2 = list(map(int, input().split(" ")))for j in arr2: if j in target: answer.append(1) else: answer.append(0)print(*answer)

문제 설명코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았다. 아래의 규칙을 사용하여 원하는 순서의 단어배열을 사용할 수 있는지를 확인하자. 1. 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.2. 한 번 사용한 카드는 다시 사용할 수 없습니다.3. 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.4. 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다. 예시cards1 : ["i", "drink", "water"]cards2 : ["want", "to"]goal : ["i", "want", "to", "drink", "water"]=> result : "Yes" cards1 : ["i", "water", "drink"]cards2 : ["want", "to"]goal : [..

그냥 heap 안쓰고 deque 쓰다가 시간초과와 싸우다가 결국 heapq를 쓰고 말았다...아무래도 입력 값이 많고, 문제에서 원하는 처리 후 다시 정렬이 필요할 때는 heapq를 쓰는게 맞는 거 같다.  또 하나 유념할 점이 계속 heappop을 이용해서 해당 list 내의 가장 최솟값을 뽑아오는 연산을 하는데제일 작은 값이 K 보다 크다면 굳이 한번 더 second 값을 가져올 필요가 없다. 나는 이점을 그냥 가볍게 생각하고 first와 second를 모두 뽑아둔 상태로 first가 K보다 크다면 그냥 while 문을 종료시켜버리고 값을 return 하도록 했는데 heappop 연산 한번이 무의미하게 진행되는 것으로 인해서 시간초과가 발생했다.(사소하다고 생각했던 한번의 연산이 시간초과를 내는걸 보..

오늘의 문제는 생각보다 간단히 해결할 수 있었다.그냥 문제를 읽으면서 문제에 명시되어 있는 그대로를 작성했다.    일단 speed를 가지고 걸리는 날짜를 구한 후앞의 일이 끝나지 않았다면 끝나기를 기다렸다가 하루동안 해결할 수 있는 일의 양을 반환하도록 코드를 구성했다. 이 풀이는 정말 직관적으로 해결한 것이라 다른 풀이를 고민해보다가 생각나면 다시 도전해 봐야지~! def solution(progresses, speeds): days = [] for i in range(len(progresses)): if (100-progresses[i]) % speeds[i] ==0: days.append((100 - progresses[i]) // speeds[i]) ..

생각보다 시간이 오래걸렸다.옛날옛적 알고리즘 공부하면서 꼭 필수로 나오던 문제였는데 그 풀이방법을 기억해내느라 오래걸렸던거 같다. 처음에는 문제가 주어질때 큐/스택이라해서 직접 옮기는걸 구현하려고 했는데 역시나 어려웠다.그래서 그냥 원래 이 문제의 접근방법인 재귀를 통해서 해결했다.  재귀 머리아파....................    이 문제는 n = 2인 케이스를 적용해서는 절대 풀리지 않는다.(일단 나는 그랬다..) n = 3 인 경우를 그림으로 표현해보자.   여기서 빨간 박스 부분이 지금 n = 2 인 경우 하노이 탑이 생성되고 있음을 알 수 있다.즉, 우리는 1 ~ n-1 개를 보조 기둥에 하노이 탑으로 쌓고, 가장 마지막 n 번째 원판을 목적지에 이동 후다시 보조 기둥에서 목적지로 이동하..

오늘의 문제는 간단하게 고딩때 배웠던 집합 or 경우의 수를 살짝 이용하면 풀리는 문제였다!(딕셔너리 사용법이 오랜만이라 어색해서 문제였지..ㅋㅋ) 부분집합의 갯수를 구한다고 생각하면 된다.종류가 같은 옷들이 하나의 집합에 들어간다고 생각을 하면 각각의 집합에서 원소를 선택하는 경우의 수는 원소의 갯수 + 1 이 된다!따라서 모든 경우의 수를 곱하고 마지막에 아무것도 안입은 경우인 1을 빼주면 내가 원하는 경우의 수가 나온다! def solution(clothes): dict = {} cnt = 1 for i in range(len(clothes)): if clothes[i][1] not in dict: dict[clothes[i][1]] = 1 ..