개발 일기

✅ 문제 ✅ 풀이 이 문제는 이전에 풀어본 괄호를 이용한 문제와 굉장히 비슷하다. 👇 괄호 문제 풀이 보기 더보기 [Leetcode] 20. Valid Parentheses ✅ 문제 - 유효한 괄호 이 문제는 s의 괄호 짝이 맞는 경우 true, 맞지 않는 경우 false 반환하는 문제이다. ✅ 풀이 코드 이 문제는 전형적인 스택 구조이다. 예를 들어, s가 {[]} 라면 [ 가 나중에 들 writtenbyrla.tistory.com [baekjoon] 9012. 괄호 ✅ 문제 💡 사용자에게 정수 하나를 입력받아 그 수만큼 문자열을 입력받고 괄호가 모두 쌍이 있는 경우 YES 출력(VPS에 해당), 괄호가 남는 경우 NO 출력 ✅ 첫 번째 시도 - 실패 # 파이썬에서 사용 writtenbyrla.tist..

✅ 문제 ✅ 풀이 이 문제는 생각보다 간단하다. 최솟값만을 이용하니 힙정렬을 이용하자 💡 Point 가장 작은 수를 지닌 카드 두 개(x, y)를 더한 값을 다시 카드 리스트에 넣어줘야 함 1) 두 카드를 제거 - heappop() 2번 2) x+y 값으로 덮어씀 - heappush() 2번 import heapq # 카드 합체 놀이 # n: 카드 개수, m=합체 횟수 n, m = map(int, input().split()) cards = list(map(int, input().split())) #리스트를 힙으로 변환 heapq.heapify(cards) for i in range(m): # 제일 작은 수 두개 뽑아내기 x = heapq.heappop(cards) y = heapq.heappop(car..

✅ 문제 예제 입력을 보면서 이해를 해보자. 첫 줄에는 터널로 진입할 차량의 수 n, 터널에 들어간 순서대로 차량 번호 n개, 터널에서 나온 순서대로 차량 번호 n개 따라서 ZG206A 말고는 들어간 순서대로 나왔으니 이 차만 추월해서 답은 1이다. ✅ 풀이 💡 Point 1. 들어가는 순서대로 딕셔너리에 담음(key = 차번호, value=들어간 순서) 2. 나오는 순서대로 리스트에 담음 3. 추월 조회 1) 나온 순서대로 2) 그 차가 몇 번째 들어갔었는지, 그 다음 차가 몇 번째 들어갔었는지 비교하여 3) 들어갈때보다 나온 순서가 크면 추월한 것으로 count 올린 후 다음 차 조회 n = int(input()) input_list = {} output_list = [] # 입구에서 들어가는 순서로..

✅ 문제 ✅ 풀이 이 문제는 하나의 커서로 이동하는 특징을 고려해서, 스택으로 풀 수 있다. 💡 Point * 일반 문자, 왼쪽 커서 이동(''), 백 스페이스('-') 네 가지 조건 나누기 1. 일반 문자: pwd 배열에 그대로 입력 2. 백 스페이스: pwd 배열에서 마지막 글자 제거 - 스택의 pop() 이용 3. 왼쪽 커서 이동 - 현재 커서가 있는 곳중간부터 입력이 들어가야 하므로 오른쪽 문자를 제거해놓아야 함 1) pwd의 마지막 글자를 제거하여 임의의 배열(cursor)에 담아 놓고, 2) 다른 연산이 끝난 후 다시 뒤에다가 붙이기(붙일 땐 거꾸로) 4. 오른쪽 커서 이동 - 임의의 배열에 담아둔 글자가 있다면 그 글자 다음에 새로운 문자를 입력받아야 함 1) cursor의 마지막 글자를 제..

✅ 문제 - 두 정렬 리스트의 병합 내부적으로 정렬된 연결 리스트 2개를 오름차순으로 병합하여 하나의 연결리스트로 만드는 문제! ✅ 풀이 💡 Point 1. 각 리스트의 노드 값을 비교하여 list1에 더 작은 수가 가도록 값을 바꿔줌 ++ list1이 비어있다면 list2를 list1으로 보내야 하기 때문에 조건문에 not list1도 함께 걸어줌 2. list1의 마지막 노드가 참조할 값은 현재 list2로 함 → mergeTwoList를 이용하여 list1의 마지막 노드가 list2의 첫 노드를 참조하게 함으로써 사실상 병합작업임 3. 정렬, 병합이 끝난 연결 리스트를 반환함 코드 class Solution: def mergeTwoLists(self, list1: Optional[ListNode],..

✅ 문제 - 역순 연결 리스트 ✅ 풀이 💡 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 ..