개발 일기

✅ 문제 - 역순 연결 리스트 ✅ 풀이 💡 Point 이 문제는 연결리스트를 역순으로 연결하는 것이다. 연결리스트란? 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않으며 각 노드마다 포인터를 통해 다음을 참조할 주소를 가진다. 따라서 이 문제의 포인트는 이전 노드의 주소를 참조하게끔 바꾸는 것이다. 연결리스트 head = [1, 2, 3, 4, 5] 일 때를 생각해보자. 배열처럼 순서가 있어보이지만 사실은 물리적인 순서가 아닌 포인터로 다음에 올 노드를 참조하는 것이다. 연결리스트는 주소를 참조하고 있다는 것만 알고 있으면 포인터를 이전 노드로 참조하도록 바꾸어주면 역순으로 연결이 된다. class Solution: def reverseList(self, head: ..

✅ 문제 ✅ 나의 풀이 import heapq class Solution: def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]: # 리스트에 1이 나온 개수를 카운트해서 순서대로 담음 min_heap = [(row.count(1), i) for i, row in enumerate(mat)] # 리스트 -> 힙 heapq.heapify(min_heap) # 답을 반환할 리스트 선언 answer = [] for i in range(k): answer.append(heapq.heappop(min_heap)[1]) return answer collections.Counter를 이용할까 하다가 row.count를 이용해보았다. mat 리스트에 담긴..

✅ 문제 - 가장 큰 두 수 곱하기 주어진 리스트에서 가장 큰 수 2개를 뽑아 -1씩 해주고 곱해주는 문제다. ✅ 나의 풀이 처음에는 리스트를 이용한 풀이법을 생각해 보았다. 하지만 이렇게 될 경우 리스트 전체를 순회해야 해서 최악의 경우 시간복잡도가 올라갈 것이라고 생각했다. 최댓값을 이용해서 간단하게 풀 수 있는 문제라 직전에 배운 힙을 이용해서 풀어봤다. 💡 힙이란? 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 1) 힙 이용 - 런타임 42ms 메모리 17.4MB import heapq class Solution: def maxProduct(self, nums: List[int]) -> int: # 최소힙으로 변환되는 것이 기본이므로 최대힙으로 heapify를 해야함 # nu..

✅ 문제 - 중복 문자가 없는 가장 긴 부분 문자열 주어진 문자열에서 중복 문자가 없는 문자열의 길이를 구하는 문제 ✅ 풀이 💡 슬라이딩 윈도우와 투 포인터 이용 1. char_list에 현재 담긴 문자의 위치를 지정해서 범위를 설정 2. 투 포인터(start, index) 이용하여 그 차이로 max값 구하기 3. char_list에 해당하는 문자가 있는지 확인하여 3-1) 중복되는 문자가 없으면 현재범위에 추가 3-2) 기존에 있는 문자일 경우는 index를 통해 위치만 갱신시켜 현재 위치 범위를 옮겨주면서 start 포인터 오른쪽으로 이동 현재 문자열의 범위를 해시 테이블 구조를 이용해 인덱스를 찍고 범위설정을 하는 것이 놀라웠다. 그저 문자열로 for문만 돌릴 궁리를 했었는데, 다른 사람들의 풀이와..

✅ 문제 - 보석과 돌 이 문제는 두 문자열을 비교하여 jewels에 있는 문자들이 stones에서 몇 번 나왔는지 카운팅하는 문제이다. ✅ 풀이 여러 가지 방법을 생각해 봤는데, 1차원적으로는 각각 반복문을 돌면서 일치여부를 확인해서 카운팅을 하는 방법이다. 이 경우에는 중첩for문이 들어가게 돼서 시간복잡도가 증가한다. stones에 나온 문자들만 카운팅을 따로 해서 해시 테이블 구조로 만들어 주면 key값으로 해당하는 문자가 몇 번 나왔는지 조회할 수 있어 훨씬 간단해진다. 방법1) 💡 Point 1. 딕셔너리 이용하여 stones의 문자를 key로 묶어 해싱 2. jewels의 문자를 key값으로 가지는 value(몇 번 나왔는지)를 answer에 더하여 반환 class Solution: def ..

📌 해시테이블이란? 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조로 시간 복잡도가 O(1)로 빠른 성능을 지니고 있다. 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 로드팩터 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것, 키들을 잘 분산해 주는지 효율성 측정에도 사용 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 해시 테이블의 크기를 조정해야 할지 결정한다. 자바 0.75 파이썬 0.66 루비 0.5 → 일반적으로 로드 팩터가 증가할수록 성능 감소, 로드 팩터를 넘어설 경우 동적 배열처럼 해시 테이블 공간 재할당 충돌 해결 방법 1. 개별 체이닝 충돌 발생 시 연결 리스트로 연결 보통 O(1)이지만 해시 충돌이 모두 발생하..

✅ 문제 - 일일 온도 현재 기온보다 더 높은 기온의 날을 며칠 더 기다려야 하는지 구하는 문제다. ✅ 풀이 def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0]*len(temperatures) #[0,0,0,0] stack = [] #enumerate: 인덱스와 값의 쌍 생성 for i, cur in enumerate(temperatures): # stack에 값이 있고, 현재 온도가 스택에 담긴 인덱스에 해당하는 온도보다 높은 경우 while stack and cur > temperatures[stack[-1]]: last = stack.pop() answer[last] = i - last stack.append..

✅ 문제 문제 해석부터 해보자 1. 일반 프린터와 달리 중요도가 높은 순으로 문서 출력 2. 중요도가 높은 문서를 제일 앞에 배치 3. 앞에 있던 문서들은 순서대로 뒤에 배치 4. 주어진 인덱스에 위치한 문서의 출력 순서를 리턴함 그림을 그려서 이해해 보자면, 아래와 같다. 입출력 예시를 보면 첫 줄은 테스트 케이스 수로 3이다. 아래에는 두 줄씩 조건이 각 테스트케이스마다의 조건이 주어져있다. 예를 들어, 두번째 케이스는 아래와 같이 설명할 수 있다. ✅ 풀이 from collections import deque # 사용자에게 숫자 하나 입력 받아서 그 횟수만큼 테스트케이스 돌림(3) T = int(input()) for i in range(T): # 사용자가 입력한 수를 공백으로 나누어 N, M값 지..

✅ 문제 - 스택를 이용한 큐 구현 ✅ 풀이 💡 문제 이해하기 이 문제는 스택을 이용해서 큐를 구현해야 한다. 큐는 FIFO(First In First Out) 방식으로 먼저 삽입된 요소가 먼저 제거되며 쉽게 말해 선입선출의 개념이다. 요소를 가로로 놓고 봤을 때 삽입은 오른쪽으로, 제거는 왼쪽에서부터 된다. 스택은 LIFO(Last In First Out) 방식으로 삽입되는 방향은 큐와 같지만, pop연산에 있어서 방향이 반대다. MyQueue 클래스의 구현 내용 정의한 것을 보면 알고 있는 스택이 연산하는 방식과 조금 다르다. 1. push: 큐의 가장 끝에 요소 x를 삽입해야 한다. 2. pop, peek: 가장 첫 번째 자리 요소를 제거하거나 조회해야 한다. → 스택 방식으로 큐를 구현하여야 하기..

✅ 문제 - 큐를 이용한 스택 구현 ✅ 풀이 코드 💡 문제 이해하기 이 문제는 큐를 이용해서 스택을 구현해야 한다. 스택은 LIFO(Last In First Out) 방식으로, 요소를 가로로 놓고 봤을 때 사실상 마지막 요소만 가지고 연산을 한다. MyStack 클래스의 구현 내용 정의한 것을 보면 알고 있는 스택이 연산하는 방식과 조금 다르다. 1. push: 스택의 가장 첫 번째 자리에 요소 x를 삽입해야 한다. → stack은 요소 삽입 시 가장 마지막 자리에 요소가 삽입되므로 삽입 후 첫 번째 자리로 보내야 한다. 2. pop, top: 가장 첫 번째 자리 요소를 삭제하거나 반환해야 함 따라서 양 방향으로 연산이 가능하게끔 스택과 큐의 결합구조인 데크를 이용해서 이 문제를 풀어야 한다. class..