Algorithm
-
[프로그래머스] - 괄호 회전하기 # StackAlgorithm 2024. 9. 9. 23:30
문제 링크1. 문제 설명 대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 매개변수로 주어질 때, s를 왼쪽으로 x칸만큼 회전시켰을 때, s가 올바른 문자열이 되도록 하는 x의 개수를 반환하라. 올바른 괄호 문자열이란 (), {}, [], {()}, {}[()], ... 와 같이 여는 괄호 뒤에 반드시 닫는 괄호가 오는 형태를 말한다. 2. 제한 사항0 1 3. 입출력 예 4. 첫 번째 풀이 - Python 스택의 LIFO 특성을 활용한다. 여는 괄호가 나오면 스택에 넣고, 그에 맞는 닫는 괄호가 나오면 스택에서 빼 줄 것이다.먼저, stack에 빈 리스트를 할당하고, opens 리스트에 {, (, [를 담아준다. closes에는 여는 괄호를 키로 갖고, 여는 괄호에 매칭되는 닫는 괄호를 값으로 갖..
-
[LeetCode] 436. Find Right Interval # Binary SearchAlgorithm 2024. 9. 8. 23:53
문제 링크1. 문제 설명 이중 배열 intervals가 주어진다. intervals의 요소 interval은 [start, end]로 구성되어있다. 반환해야할 answer의 i번째 요소는 현재의 end 값이 또 다른 interval의 start 값보다 작거나 같을 때, 최소값의 start를 가진 interval의 인덱스이다. 조건을 만족하는 start 값이 없다면 -1이 answer의 i번째 요소로 들어간다. 2. 제한 사항1 intervals[i].length == 2-10^6 각 interval의 start 값은 고유하다 3. 입출력 예 4. 첫 번째 풀이(시간 초과) - Python 문제의 조건을 그대로 구현했다. 결과는 시.간.초.과. 🤧 효율적으로 푸는 아이디어가 안 떠오른다..class..
-
[프로그래머스] 전화번호 목록 # HashAlgorithm 2024. 9. 8. 01:19
문제 링크1. 문제 설명전화번호를 담은 배열 phone_book이 파라미터로 주어질 때, 전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있으면 False를, 그렇지 않으면 True를 반환한다. 2. 제한 사항1 1 같은 전화번호가 중복해서 들어있지 않음 3. 입출력 예 4. 첫 번째 풀이(시간 초과) - Python 냅다 for문 두 번 돌려버렸다. 이중 중첩 반복문을 순회하면서 현재 전화번호가 비교 대상 전화번호와 다르고, 자신의 전화번호가 비교 대상 전화번호로 시작하는지 판단한다. 리스트를 동시에 두 번 조회하므로 시간복잡도 O(n^2)이다. 그리고 현재 전화번호가 비교 대상 전화번호와 다른지 판단해야한다는 의미는 자기 자신과의 비교를 불필요하게 수행하고 있다는 의미이다..
-
99클럽(3기) - 코테스터디 9일차 TIL # DPAlgorithm 2024. 8. 13. 00:22
프로그래머스 - 피보나치 수1. 문제 설명n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수 solution을 완성하라. 2. 제한 사항2 3. 입출력 예 4. 첫 번째 풀이(런타임 에러) - Python런타임 에러가 발생했다. 재귀를 사용했기 때문에 n이 100,000에 가까운 숫자일 경우 스택 오버플로우가 발생했을 것이다. 1) 메모이제이션과 피보나치 수 계산을 위한 F 클래스 생성초기화 함수 __init__에서 F(0) = 0, F(1) = 1로 메모이제이션을 위한 딕셔너리를 초기화한다. 피보나치 수열을 계산하기 위한 함수 fibo에서는 self.memo에 있는 키인지 먼저 확인 후 없으면 피보나치 수를 재귀적으로 계산한다. 이 때, n이 충분히 커졌을 경우 발생 가능한 오..
-
99클럽(3기) - 코테스터디 6일차 TIL # 이분탐색Algorithm 2024. 8. 4. 16:03
프로그래머스 - 18016. 숫자 카드 21. 문제 설명 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 포함 개수를, 아니면 0을 공백으로 구분해 출력한다. 어제 문제는 상근이가 가지고 있는 숫자 카드 N개에 M개의 수 중에 하나라도 포함되어 있으면 1을 반환했다면, 오늘 문제는 포함 개수를 구해야 한다. 첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 2. 제한 사항1 1 10,000,000 3. 입출력 예 4. 첫 번째 풀이 (시간초과)ns.count(val)의 시간복잡도가 O..
-
99클럽(3기) - 코테스터디 5일차 TIL # 이분탐색Algorithm 2024. 8. 4. 14:38
프로그래머스 - 10815. 숫자 카드1. 문제 설명 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 1, 아니면 0을 공백으로 구분해 출력한다. 첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 2. 제한 사항1 1 10,000,000 3. 입출력 예 4. 첫 번째 풀이 - Python1) 4줄의 입력을 처리한다. 4줄에 걸쳐 정수 N, N개의 숫자들, 정수 M, M개의 숫자들을 입력받는다. ns 생성에 O(N), ms 생성에 O(M)의 시간복잡도가 소요된다. 2) N개의 숫자들(..
-
99클럽(3기) - 코테스터디 4일차 TIL # 정렬Algorithm 2024. 8. 3. 10:55
프로그래머스 - H-Index1. 문제 설명어떤 과학자가 발표한 논문 n편이 인용된 횟수를 담은 배열(citations)이 주어진다. 논문 n편 중 h번 이상 인용된 논문이 h편 이상 인용되고, 나머지 논문이 h편 이하 인용되었다면 h의 최댓값을 H-Index라고 하며, H-Index를 구해서 반환해야 한다. 2. 제한 사항1 0 3. 입출력 예 4. 첫 번째 풀이 - Python 'h번 이상 인용된 논문이 h편 이상 인용되었는지 판단하는 기준'을 설정하는 것이 핵심이었다. 이 말 자체를 이해하고 어떻게 문제 풀이에 적용할까 고민하는 시간이 제일 많이 소요된 것 같다. h의 최대값을 구해야하기 때문에 citations를 내림차순으로 정렬해서 가장 많이 인용된 논문부터 몇 편의 논문에 인용되었는지 ..
-
99클럽(3기) - 코테스터디 3일차 TIL # 정렬Algorithm 2024. 8. 1. 22:56
프로그래머스 - 카드 뭉치1. 문제 설명문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 파라미터로 주어질 때, cards1과 cards2에 적힌 단어들로 goal을 만들 수 있다면 "Yes", 만들 수 없다면 "No"를 반환해야 한다. 2. 제한 사항1 1 cards1과 cards2에는 서로 다른 단어만 존재함 2 1 goal의 원소는 cards1과 cards2의원소들로만 구성됨 cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 구성됨 3. 입출력 예 4. 나의 풀이1) cards1과 cards2의 인덱스를 추적하기 위한 변수 할당cards1의 인덱스를 추적할 idx1, cards2의 인덱스를 추적할 idx2를 각각 0으로 초기화한다. 2) g..