코테준비/Programmers
도둑질(DP이용)
스위치를 이용하여 경우의수 나눔 def solution(money): # 1,000,000개 이하 0(n)에서 끝내야한다 if len(money) ==3: return max(money) #예외처리 cur = money[:2] #[a,b] cur.append(cur[0] + money[2]) #[a,b,c] -> [0,b,c] switch = (max(cur[0],cur[1]) == cur[0]) #첫번째가 뽑혓냐 #cur[3] = max(cur[0],cur[1]) +money[3] #[0,b,c,d] -> b,c크기비교 x #cur[4] = max(cur[1],cur[2]) +money[4] # [0,0,c,d,e] #cur[5] = max(cur[2],cur[3]) + money[5] # [0,0,0..
짝지어 제거하기(Stack이용)
이 문제는 stack를 이용하냐 안 이용하냐에 따라 문제를 풀 수 있냐 없냐가 나뉜다 문제를 읽고 시간 복잡도 파악하기 (이 문제 같은 경우는 문자열의 길이가 1,000,000 라 했으므로 0(n)을 넘어가면 안된다) 2.무작정 코딩하는 습관 버리기 (어떤 걸 이용할지 생각하는 습관을 기르자) List 이용 def solution(s): #소문자로 이루어짐 길이: 1,000,000이하의 자연수 if len(s) % 2 != 0: return 0 #속도향상을 위한 예외 처리 s =list(s) switch = 1 while(switch): switch = 0 for i in range((len(s)-1)): if s[i] == s[i+1]: switch = 1 s.pop(i) s.pop(i) break i..
오픈채팅방(dict이용)
내 풀이(dict이용) #관리자 채팅방 새로운 닉네임으로 들어오는 경우 닉네임을 변경한 경우, 중복허용 [유저아이디로 변경] def solution(record): answer = [] lst = [] dic = {} #첫 단어는 Enter, Leave, Change for string in record: #길이 100,000 이하 lst.append(list(string.split())) #이중 배열로 처리한다 for words in lst: if words[0] == 'Leave': continue dic[words[1]] = words[2] #dic완성 for words in lst: if words[0] == 'Enter': answer.append(dic[words[1]]+'님이 들어왔습니다.'..
기능개발(queue이용)
Queue를 이용 (시간 복잡도가 0(n^2)이여서 조금 위험했음) from collections import deque def solution(progresses, speeds): answer = [] queue, addict = deque(progresses), deque(speeds) while(len(queue)):# queue가 빌때까지 if queue[0] >= 100: #peek count = 0 while(len(queue) != 0 and queue[0] >=100): queue.popleft() addict.popleft() #같이 빼줘야한다 count += 1 answer.append(count) else: for idx in range(len(queue)): queue[idx] +=..
타겟넘버(DFS이용)
내 풀이 (DFS 이용) count = 0 def dfs(numbers, start ,target, current): global count if start == len(numbers)-1: #종단조건 if current == target: count+=1 return 0 dfs(numbers,start+1,target,current-numbers[start+1]) dfs(numbers,start+1,target,current+numbers[start+1]) def solution(numbers, target): current = numbers[0] dfs(numbers, 0 ,target, current) dfs(numbers, 0 ,target, -current) return count Best 풀이..
소수 찾기(순열 이용)
순열을 이용한 완전 탐색 + set 이용 from itertools import permutations as P def solution(numbers): #ex) [0,1,2,5,7,9] ans_set = set() make = [] count = 0 for i in range (1,len(numbers)+1): #모든 순열의 경우의 수를 추가 make += list(P(numbers,i)) #[( , , ), ( , , ), ( , , )] for tup in make: s_num = int("".join(map(str,tup))) #숫자로 바꿔주기 if s_num == 2 : ans_set.add(s_num) #2는 예외 처리 for div in range (2,s_num): #(1,2는 위에서 처리..
더 맵게(heap 이용)
list 이용 def mix(itm1,itm2): n = itm1+itm2*2 return n def solution(scoville, K): answer = 0 while(len(scoville)>1): if min(scoville) -1 if scoville[0] < K:return -1 else: return answer 정확성은 좋지만 효율성은 떨어지는 아이..
멀쩡한 사각형(최대공배수 이용)
입출력 예 #1가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다. import math def swap(a,b): tmp= a a = b b = tmp return a,b def solution(w,h):#가로 세로 h: w ,h = swap(w,h) #세로가 긴 경우로만 코딩 하겠다 pvt = h/w #기울기로 고려해보자 upper = int(math.ceil(pvt)) drop = int(pvt) #if pvt - drop > 0.5: return (w*h)-(w+h -math.gcd(w,h)) #else: # 0.5이하인 경우 #return w*..
124나라(3진법이용)
진법 이용 #3진법으로 접근 (1,2,4) -> (0,1,2) #1 2 10 11 12 20 21 22 100 101 102 110 111 112 120
행렬 테두리 회전하기(copy매소드)
copy에 대한 고찰 행렬을 다룰때 자주쓰는 라이브러리 copy import copy deep_copy_lst = copy.deepcopy(lst) #깊은복사 shallow_copy_lst = copy.copy(lst) #얖은 복사 이것이 빨라 보이지만 이 라이브러리로 인하여 시간초과 판정을 받았다 → 즉, 편하긴 하지만 코딩테스트에서는 적합하지 않음 https://codesyun.tistory.com/198 위와 같이 코딩테스트에서는 list slicing을 이용하여서 리스트를 복사해야 한다. 1차원 배열에서의 깊은 복사 lst = [1,2,3,4,5,6] cpy_lst = lst[:] 🌟2차원 배열에서의 깊은복사 lst = [[1,2],[3,4],[5,6]] **cpy_lst = [item[:] fo..
올바른 괄호(lambda이용)
lambda 식에 if else 문을 넣는 법을 배웠다 lambda x : (if문 return) if (if문 조건) else (else문 return) 주의 점은 return ← if문 else문 → return 이런 구조라는 것이다 내 풀이 def solution(s): if len(s) % 2 == 1 or s[0] == ')' or s[-1] == '(' : return False num = list(map(lambda x: -1 if x == '(' else 1, s)) pvt,count = 0,0 for itm in num: count += 1 pvt += itm if pvt >= 0: if count % 2 == 1 or pvt > 0:return False else: count =0 if..