개발 일기

✅ 문제 - 보석과 돌 이 문제는 두 문자열을 비교하여 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..

✅ 문제 💡 사용자에게 정수 하나를 입력받아 그 수만큼 문자열을 입력받고 괄호가 모두 쌍이 있는 경우 YES 출력(VPS에 해당), 괄호가 남는 경우 NO 출력 ✅ 첫 번째 시도 - 실패 # 파이썬에서 사용자로부터 정수를 입력받아 변수 T에 할당하는 코드 # 예를 들어 사용자가 3을 입력하면 T는 3이 됨 T = int(input()) # () 괄호 한 쌍 딕셔너리 방식으로 지정 # key ')', value '(' pair = {')': '('} for i in range(T): # T번 for문 돌림 stack = [] # 괄호를 담아둘 리스트 s=input() #T가 3이라면 문자열을 세번 입력받아 s에 할당 for char in s: # pair의 key값에 해당하는게 없을 경우(열림 괄호일 경우..

✅ 문제 - 유효한 괄호 이 문제는 s의 괄호 짝이 맞는 경우 true, 맞지 않는 경우 false 반환하는 문제이다. ✅ 풀이 코드 이 문제는 전형적인 스택 구조이다. 예를 들어, s가 {[]} 라면 [ 가 나중에 들어갔기 때문에 ] 가 먼저 나와야하고, 그다음에 처음 들어간 { 에 맞는 } 가 나와야 한다. 방법1) class Solution: def isValid(self, s: str) -> bool: # 괄호 짝 dict로 만들기(key-value) pair = { ')' : '(', '}' : '{', ']' : '[', } #opener를 담을 리스트 stack = [] opener = "({[" for item in s: # opener는 stack에 넣기 if item in opener:..

✅ 문제 - 세 수의 합💡 숫자로 이루어진 리스트의 값 3개를 더했을 때 0이 되는 세 수를 구하는 문제 ✅ 첫 번째 시도 - 런타임 초과class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: results = [] nums.sort() #i,j,k 세 수의 합 for i in range(len(nums)-2): # 중복값 제외 if i>0 and nums[i] == nums[i-1]: continue for j in range(i+1, len(nums)-1): if j > i+1 and nums[j] == nums[j-1]: continue for k in range(j+1, len(nums)): if k > j+1 and num..

✅ 문제 - 가장 긴 팰린드롬 부분 문자열 구하기💡 팰린드롬이란? 토마토 기러기 스위스처럼 앞으로 읽어도 거꾸로 읽어도 같은 문자열을 지닌 단어를 말한다. 주어진 문자열 s에서 앞뒤가 똑같은 문자열을 추출하여 가장 긴 것만 반환하는 것이 이 문제의 포인트이다. 주어진 문자열의 길이가 짝수인 경우 연달아 겹쳐있는 문자도 팰린드롬에 포함된다. ✅ 첫 번째 시도 - 실패class Solution: def longestPalindrome(self, s: str) -> str: #한 글자일 경우, s를 뒤집었을 때 s와 같은 경우 s 그대로 반환 if len(s) == 1 or s == s[::-1]: return s #팰린드롬 담을 리스트 선언 p_list = [] for i in range(len(s)): f..