공부 기록

✏️ 문제 문제 파악나는 skill_trees의 문자열들 중에 skill에 없는 문자가 있다면 replace로 없애고 난 후에 비교했는데 다른 분들은 그냥 제거 과정 없이 바로 비교해서 푸셔서 코드가 훨씬 간결하셨다..  코드def solution(skill, skill_trees): answer = 0 for i, skill_tree in enumerate(skill_trees): for s in skill_tree: if s not in skill: skill_tree = skill_tree.replace(s, '') skill_trees[i] = skill_tree for skill_tree in..

✏️ 문제 문제 파악scoville 길이가 최대 1,000,000이기 때문에 배열을 반복문을 통해 돌면 당연히 시간복잡도에서 걸린다.  이때 이 문제는 힙을 사용하면 좋은데 이유는 최소값이나 최대값을 효율적으로 빠르게 추출해야 하고 힙 속성 덕분에 힙에 넣으면 자동으로 정렬이 되기 때문이다.배열은 특정 값을 찾을 때 최악의 경우 O(n)이라는 시간이 소요되고, 계속해서 정렬을 해줘야하는 반면힙은 최소값이나 최대값을 찾을 때 O(1)이라는 시간이 소요된다.  그래서 이러한 힙을 활용해서 문제를 풀면 쉽게 풀 수 있다.   코드import heapqdef solution(scoville, K): heapq.heapify(scoville) answer = 0 while len(scovi..

✏️ 문제 문제 파악처음엔 이중 for 반복문 사용했다가 numbers 길이가 1,000,000 까지라 시간복잡도에서 무조건 걸릴거라 예상했다..그래서 배열을 한바퀴 돌되 그 전에 있던 값들도 비교를 하려면 stack에 넣어서 안의 값을 계속 비교하며 처리해야 할 것 같아 stack을 사용했다. 아직 stack을 잘 사용할 줄 모르는 거 같아서 큰일이다.. ㅠ유사한 문제로는 주식가격이 있다. 코드실패 코드def solution(numbers): answer = [] for i in range(len(numbers)-1): for j in range(i+1, len(numbers)): if numbers[i] 성공 코드def solution(number..

✏️ 문제 문제 파악처음엔 배열[:]을 사용했다가 topping의 길이가 최대 1,000,000까지 되므로 당연히 시간초과가 떴고.. 그 후에 pop()도 사용했으나 매번 set(topping)처리하는 과정에서 시간 복잡도가 컸었다..  그래서 각 토핑의 개수를 센 딕셔너리를 만들고 나누는 경계선이 변하면서 해당 토핑의 종류의 개수를 수정해가며 토핑의 개수를 비교하는 방법으로 코드를 짰다.   코드실패 코드def solution(topping): answer = 0 length = len(topping) a = set() for i in range(length): value = topping.pop() a.add(value) ..

✏️ 문제 문제 파악보자마자 dfs 재귀로 풀면 되겠다! 했는데 뭐 때문인 지 만든 문자열과 주어진 word가 같음에도 불구하고 리턴 값이 null로 나왔다 ㅠ 찾아보니 코드가 재귀이므로 if 만든 문자열 == word 에 해당되어도 return하면 상위 호출에 return한 값을 가져다주고 남은 반복문, 호출이 계속 진행되게 된다.그래서 값을 찾았더래도 남은 재귀 호출을 처리하는 과정에서 값이 null로 바뀌게 되어 결국 null이 출력되게 된다. ps. 목표 단어를 찾았더라도 다른 반복문에서 계속 탐색을 수행하게 되고 재귀 호출의 반환값이 상위 호출로 전달되지 않고 결국 None을 반환하게 된다. 이를 해결하기 위해서는 반환값이 부모 호출로 제대로 전달되도록 하기 위해, 재귀 호출에서 반환된 값을 ..

✏️ 문제 문제 파악이 문제도 모든 경우의 수를 다 구하는 것 같아서 dfs를 활용해 풀었다. 이때 특징은 index가 0에서 len(number)-1가 될 때까지 다음의 값을더한다.뺀다.로 두 가지 경우가 있으므로 dfs도 두 가지로 나누어서 돌아야 한다.  코드def solution(numbers, target): answer = 0 def dfs(index, total): nonlocal answer if index == len(numbers): if total == target: answer += 1 return dfs(index + 1, total + numbe..

✏️ 문제 문제 파악처음에는 in 으로 풀면 되지 않나 싶어서 했는데 역시나.. 시간 초과로 통과가 되지 않았다.찾아보니 딕셔너리와 리스트(배열)의 in 연산 시간복잡도는 다음과 같았다.자료구조딕셔너리리스트(배열)시간복잡도O(1) (평균), O(n) (최악)O(n) 그래서 딕셔너리를 생성해 이를 in 처리해서 풀었다.  코드시간 초과 코드def solution(phone_book): for i in range(len(phone_book)-1): for j in range(i+1, len(phone_book)): if (phone_book[i] == phone_book[j][:len(phone_book[i])]) or (phone_book[j] in phone_book..

✏️ 문제 문제 파악전체의 경우 수를 다 돌았을 때 최소 값을 구하므로 완전탐색을 풀 때 효율 좋은 백트래킹을 활용해 풀면 된다. max_cnt를 dfs 함수 내에 사용할 때 에러가 뜨는데 local 변수라 에러가 뜨는 것이므로 이를 global 함수로 변경해서 사용하면 된다.global 함수로 정의하기 위해선 dfs 함수 내외, 두 곳 다 정의해주어야 하는데이게 싫으면 dfs 함수 내에 nonlocal max_cnt라고 써주면 한줄로 에러를 해결할 수 있다.  코드def solution(k, dungeons): global max_cnt max_cnt = 0 visited = [False] * len(dungeons) def dfs(k, cnt): global ..

✏️ 문제 문제 파악priorities 배열 내의 값이 같아도 다 다른 프로세스이므로 값으로 구분하면 안되고 위치로 구분해야 한다. 그래서 딕셔너리를 사용해 { 인덱스 : 값 } 으로 주었고 location과 인덱스가 같으면 반복문을 그만 돌도록 코드를 짰다. 우선순위가 높은 프로세스부터 실행되기 때문에만약 딕셔너리의 값 중 최대값(max)인데딕셔너리의 인덱스 == location 이라면 프로세스 실행 변수 출력딕셔너리의 인덱스 != location 이라면 딕셔너리 값 = -1, 프로세스 실행 변수 +1로 하여 반복문을 돌리도록 하였다.  코드def solution(priorities, location): cnt = 1 dic = {} for i, p in enumerate(pri..

✏️ 문제 문제 파악각 의상들은 입는 방법이 2가지로 나뉜다.입는다.안입는다. 하지만 코니는 최소 한 개의 이상을 입으므로 전부 안입는 경우는 치지 않으므로 마지막 결과값에 -1을 해주어야 한다. 예시 1번을 보면 headgear1. 두 개 다 안쓴다.2. yellow_hat 쓰고 green_turban 안쓴다.3. green_turban 쓰고 yellow_hat 안쓴다.eyewear1. 안쓴다.2. blue_sunglasses 쓴다 경우의 수는 해당 의상의 종류 + 1(안쓴다) 인 것으로 알 수 있다.그리고 우리가 구하는 조합의 수는 3(headgear의 경우의 수) * 2(eyewear의 경우의 수) - 1(아무것도 안입는 경우) = 5 이다.이 계산식을 근거로 코드를 짜면 된다.  코드from co..