1. python import collections import sys sys.setrecursionlimit(2000) def dfs(x): visited[x]=True print(x,end=' ') for y in sorted(dict[x]): if not visited[y]: dfs(y) def bfs(x): visited[x]=True dq=collections.deque() dq.append(x) while dq: cur=dq.popleft() print(cur,end=' ') for y in sorted(dict[cur]): if not visited[y]: visited[y]=True dq.append(y) n,m,v=map(int,sys.stdin.readline().split()) dic..
2개씩 짝을 지어 최소값들의 합의 최대값을 구하는 것은 정렬된 배열을 2개씩 묶어서 구하면 된다. 정렬된 수이므로 각 짝의 최대값은 인덱스가 짝수인 수들이며 sorted(nums)[::2]를 통해 짝수번째 수들만 구할 수 있다. class Solution: def arrayPairSum(self, nums: List[int]) -> int: print(sorted(nums)[::2]) return sum(sorted(nums)[::2]) # nums.sort() # result=0 # pair=[] # for i in range(1,len(nums),2): # pair=[nums[i],nums[i-1]] # result+=min(pair) # pair=[] # return result
* 알게 된 것 check.values()의 리턴이 배열 형태가 아닌 줄 알고 또 따로 배열을 만들어서 처리해줬었는데 배열로 리턴이 되는 것 같다. sorted는 리스트 형태로 반환한다. sorted(문자열)은 문자열의 각 단어를 정렬한 리스트를 반환해준다. from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: check=defaultdict(list) for item in strs: # print(''.join(sorted(item))) sortedWord=''.join(sorted(item)) check[sortedWord].append(item) ret..
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 순열 조합 문제인 줄 알았으나 dfs로 풀기 때문에 브루트 포스, 그리디 문제 같다. left는 넣을 수 있는 왼쪽 괄호의 개수, right는 넣을 수 있는 오른쪽 괄호의 개수이다. left,right 하나씩 넣어주지만 오른쪽 괄호는 왼쪽 괄호가 하나이상 존재할 때만 넣을 수 있다. left List[str]: def genParent(s,left,..
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000. 1. 브루트포스 풀이 (시간 초과) 처음에 이렇게 풀었더니 시간 초과가 나왔다. 배열의 길이가 O(n)인데 ..
1. python from collections import defaultdict import re class Solution: def mostCommonWord(self, paragraph: str, banned: List[str]) -> str: dict=defaultdict(int) paragraph=re.sub(r'[^\w]',' ',paragraph) # print(paragraph) for p in paragraph.lower().split(): if p not in banned: dict[p]+=1 return max(dict,key=dict.get) cnt=collections.Counter(dict) 해서 return cnt.most_common(1)[0][0]으로 가져오는 방법도 있다 ..
1. python class Solution: def reorderLogFiles(self, logs: List[str]) -> List[str]: nums=[] letters=[] for log in logs: if log.split()[1].isdigit(): nums.append(log) else: letters.append(log) # slice로 잘라서 그 후를 모두 지정할 수 있다 letters.sort(key=lambda x:(x.split()[1:],x.split()[0])) # print(nums) # print(letters) return letters+nums 2. javascript /** * @param {string[]} logs * @return {string[]} */ var..
O(n) 시간에 풀어야하는 문제이다 0 일 경우 현재 차의 개수 cur을 +1해주며 1을 만날 경우 현재까지 있던 왼쪽에 있던 차의 개수를 전체 sum에다 더하면 된다. 왼쪽에 있는 0의 개수가 1이 만나게 될 차의 개수이기 때문이다. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A): sum=0 cur=0 for i,car in enumerate(A): # print(i,cur) if car==0: cur+=1 else: sum+=cur if sum>1000000000: return -1 else: return sum o(n^2)는 효율성 통과를 못하지만 A[i+1..
* 문자열 뒤집기 [::-1] 또는 ''.join(reversed(s)) def solution(s): answer = 0 for i in range(1,len(s)+1): for j in range(0,i): if s[j:i]==s[j:i][::-1]: if len(s[j:i])>answer: answer=len(s[j:i]) return answer 2. javascript 제일 긴 문자열부터 모든 위치에 있을 수 있는 경우의 수를 검사한다. function solution(s) { for(let i=s.length;i>=1;i--){ let flag=false; for(let j=0;j
deque은 remove나 insert함수도 있다 1. 파이썬 def solution(cacheSize, cities): answer = 0 cache=[] for c in cities: c=c.lower() if c not in cache: if cache and len(cache)>=cacheSize: cache.pop(0) if cacheSize>0: cache.append(c) answer+=5 else: cache.remove(c) cache.append(c) answer+=1 return answer 2. 자바스크립트 function solution(cacheSize, cities) { const cache=[]; var answer = 0; for(let i=0;icacheSize)cache..