분류 전체보기

문제매일의 화씨 온도(˚F) 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라  · 입출력 예 T[73, 74, 75, 71, 69, 72, 76, 73]return[1, 1, 4, 2, 1, 1, 0, 0] 풀이1. 스택 값 비교-> 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교하여, 더 높다면 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in ..

문제괄호로 된 입력값이 올바른지 판별하라 · 입출력 예 sreturn()[]{}True풀이1. 스택 일치 여부 판별-> 파이썬 리스트는 스택 연산인 푸시와 팝이 O(1)에 동작한다.def isValid(s: str) -> bool: stack = [] table = { ')':'(', '}':'{', ']':'[' } for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0매..

문제덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. · 입출력 예 numstargetreturn[2, 7, 11, 15]9[0, 1]풀이1. 브루트 포스로 계산def twoSum(nums: list[int], target: int) -> list[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j]브루트 포스란 배열을 2번 반복하며 모든 조합을 더해 일일이 확인해보는 무차별 대입 방식으로, 비효율적인 풀이법에 해당한다. nums 배열을 이중 탐색하며 nums[i], nums..

문제가장 긴 팰린드롬 부분 문자열을 출력하라 · 입출력 예 sreturn"babad""bab""cbbd""bb"풀이1. 중앙을 중심으로 확장하는 풀이-> 이 문제는 다이나믹 프로그래밍으로도 풀 수 있지만, 이를 이용한 풀이는 직관적으로 이해하기 어렵고, 실행 속도가 늦다. 이에 투포인터가 중앙을 중심으로 확장하는 형태로 문제를 풀어보자.def longestPalindrome(s: str) -> str: def expand(left: int, right: int) -> str: while left >= 0 and right 가장 먼저 리스트 슬라이싱을 이용한 예외 처리를 해줌으로써 전체적인 풀이 속도를 향상한다. 이후 슬라이딩 윈도우가 문자열 처음부터끝까지 우측으로 이동하며, expand..

문제APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다. 이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은..

문제문자열 배열을 받아 애너그램 단위로 그룹핑하라 * 애너그램이란 ? 일정의 언어유희로, 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 뜻함 · 입출력 예 입력["eat", "tea", "tan", "ate", "nat", "bat"]출력[["ate", "eat", "tea"], ["nat", "tan"], ["bat"]] 풀이1. 정렬하여 딕셔너리에 추가-> 애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. (애너그램 관계인 단어를 정렬하면 서로 같은 값을 가짐)def groupAnagrams(strs: list[str]) -> list[list[str]]: anagrams = collections.defaultdict(list) for word in strs:..

문제전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. · 구조대: 119 · 박준영 : 97 674 223· 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. · 제한사항1. phone_book의 길이는 1이상 1,000,000이하입니다.2. 각 전화번호의 길이는 1이상 20이하입니다.3. 같은 전화번호가 중복해서 들어있지 않습니다.  · 입출력..

문제금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시한다. · 입출력 예 paragraph "Bob hit a ball, the hit BALL flew far after it was hit."banned ["hit"]return "ball"풀이1. 리스트 컴프리헨션, Counter 객체 사용def mostCommonWord(paragraph: str, banned: list[str]) -> str: words = [word for word in re.sub(r'[^\w]',' ', paragraph).lower().split() \ if word not in banned] counts = collec..

문제로그를 재정렬하라. 정렬 기준은 다음과 같다. 1. 로그의 가장 앞 부분은 식별자이다.2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.4. 숫자 로그는 입력 순서대로 한다. · 입출력 예logsreturn["dig1 8 1 5 1", "let1 art can", "dig2 3 6"]["let1 art can", "dig1 8 1 5 1", "dig2 3 6"] 풀이1. 람다 함수와 + 연산자 이용-> 이 문제는 정렬해야하는 문자 로그와 정렬하면 안되는 숫자 로그로 나누는 것이 핵심 포인트이다.def reorderLogFiles(logs:list[str]) -> list[str]: letters, digits ..

해시0) 정의-> 데이터를 다루는 기법 중 하나로, 검색과 저장에 아주 유용한 구조이다. key-value 쌍으로 데이터를 저장함1) 해시함수란 ? -> 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수  2) 해시 구현 방법 · 딕셔너리에 삽입hash = dict()hash[1] = 'apple'hash['banana'] = 3hash[(4, 5)] = [1, 2, 3]hash[10] = dict({1: 'a', 2: 'b'})위와 같은 형태로 해시 함수를 사용할 수 있지만, 집합과 배열은 해시 함수의 키 값으로 사용할 수 없다. (인덱스로 변환 불가)  ex) hash({3, 5}), hash([3, 5]) -> 사용 x  · 딕셔너리 값 추출 hash.pop(1) # '..

문제n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.  예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.1. -1+1+1+1+1 = 3 2. +1-1+1+1+1 = 33. +1+1-1+1+1 = 34. +1+1+1-1+1 = 35. +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타켓 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return하도록 solution 함수를 작성해주세요. · 제한사항1. 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.2. 각 숫자는 1이상 50이하인 자연수입니다.3. 타겟 넘버는 1이상 1000이..

문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어, 7대의 컴퓨터가 그림과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터..