Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.You must write an algorithm that runs in O(n) time and without using the division operation.division 연산 없이 O(n)의 시간 복잡도로 계산하라고 제약 조건이 주어진 문제였다! 풀이class Solution: def produ..
⚙️ Problem Solving
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.빈도수가 높은 순서대로, 상위 k개의 elements를 출력하는 문제다. 풀이 1class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = defaultdict(int) for i in nums: count[i] += 1 result = sorted(count, key=count.get, reverse=Tr..
anagram은 일단 sort 후 비교를 떠올리자! 풀이1: 리스트 활용class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: result = [] visited = [False] * len(strs) for i in range(len(strs)): if visited[i]: continue tmp = [] tmp.append(strs[i]) visited[i] = True for j in range(len(strs)): if so..
내 풀이: 브루트포스class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: result = set() for i in range(len(nums)): for j in range(len(nums)): if nums[i] + nums[j] == target and i != j: result.add(i) result.add(j) result = list(result) return sorted(result)set에다가 추가하고 리스트로 바꾸고 sor..
풀이1: 리스트 사용class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False letters = [] for i in s: letters.append(i) for i in t: if i in letters: letters.remove(i) else: return False return True리스트를 사용하여 단순하게 구현한 풀이 풀이2: sorted 후 ..
풀이 1 : 리스트와 in 문법 사용class Solution: def hasDuplicate(self, nums: List[int]) -> bool: count = [] for i in nums: if i not in count: count.append(i) else: return True return FalseNeetCode에서 통과한 코드다.하지만 LeetCode에서는 nums 배열이 아주 큰 테스트케이스에서 시간 초과로 통과하지 못했다. 풀이 2 : set과 in 문법 사용class Solution: def containsDuplicate(se..
이진 트리를 입력 받아 preorder traversal, inorder traversal, postorder traversal한 결과를 출력하는 프로그램 풀이 1: tree를 딕셔너리로 표현, 재귀 이용import sysinput = sys.stdin.readlinen = int(input().strip())tree = {}for _ in range(n): parent, left, right = input().split() tree[parent] = (left, right)root = 'A'def preorder(tree, node): if node == '.': return "" return node + preorder(tree, tree[node][0]) + pre..
각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집들이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 최소 비용을 구하는 문제-> DP 테이블을 2차원 리스트로 정의하여 풀 수 있다. 풀이동적 프로그래밍 테이블 정의:dp[i][j]: i번째 집을 j색으로 칠하는 최소 비용 (j = 0: 빨강, 1: 초록, 2: 파랑)점화식 설정:dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) (i번째 집을 빨강으로 칠하는 경우)dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) (i번째 집을 초록으로 칠하는 경우)dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) (i번째 ..
문제 요약MBTI 성격 유형을 가진 학생들 사이의 심리적인 거리를 계산하는 문제이다. 주어진 학생들 중 가장 가까운 세 학생의 심리적인 거리를 구하는 것이 목표이다.입력첫 줄에는 테스트 케이스의 수를 나타내는 정수 ( T )가 주어진다.각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 정수 ( N )이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 공백을 두고 주어진다.출력각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. 풀이 설명이 문제는 세 학생의 MBTI 유형 간의 심리적 거리를 구하는 문제이다. MBTI는 4개의 척도로 구성되어 있으므로 총 16개의 유형이 있다. 세 학생 간의 심리적 거리는 세 유형 간의 심리적 거리의 합으로 정의된다.문제에서..
문제 요약도연이는 캠퍼스에서 만날 수 있는 친구의 수를 알고 싶어한다. 캠퍼스는 ( N \times M ) 크기이며, 도연이는 빈 공간('O')과 사람('P')이 있는 곳으로 이동할 수 있다. 벽('X')은 이동할 수 없다. 도연이가 시작하는 위치는 'I'로 주어진다. 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성하는 문제이다.입력첫 번째 줄에 캠퍼스의 크기를 나타내는 두 정수 ( N )과 ( M )이 주어진다.다음 ( N )개의 줄에 캠퍼스의 정보가 주어진다. 'O'는 빈 공간, 'X'는 벽, 'I'는 도연이의 시작 위치, 'P'는 사람이다.출력도연이가 만날 수 있는 사람의 수를 출력한다. 만약 아무도 만나지 못한 경우 "TT"를 출력한다. 풀이 설명이 문제는 BFS(너비 우선 탐색)를..
