본문 바로가기

Coding Test

 (8)
[백준] 17608.막대기 import sys def stick(nums): stk=[] stk.append(len(nums)-1) max=nums[-1] for i in range(len(nums)-2,-1,-1): #(len,0,-1)을 하면 0 이전까지만 포함되서 맨 처음 element엔 접근을 안함 if nums[i]>max: stk.append(i) max=nums[i] return len(stk) n=int(sys.stdin.readline()) nums=[int(input()) for _ in range(n)] #공백이 기준이 아닌 \n이 기준일 때 print(stick(nums)) stack을 써보고 싶어서 이렇게 코드를 짰는데 시간초과가 나왔다. 결과는 숫자 하나면 되는데 괜히 리스트를 하나 더 많들어서 스택연산을..
[Leetcode]125.Valid Palindrome def isPalundrome(s): strs=[] for char in s: if char.isalnum(): #영문자,숫자 여부를 판별하는 함수 strs.append(char.lower()) #대소문자 구분 안함 while len(str)>1: #홀수 고려해서 1 if strs.pop(0) != strs.pop(): #리스트의 pop은 인덱스를 지정할 수 있음 return False return True import collection def isPalundrome(s): strs=collection.deque() for char in s: if char.isalnum(): strs.append(char.lower()) while len(str)>1: if strs.popleft() != strs.p..
[Leetcode] 17. Letter Combinations of a Phone Number DFS와 백트랙킹 깊이 우선 탐색(DFS)DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다.따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다. 백트랙킹 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요..
[Leetcode] 3. Longest Substring Without Repeating Characters Solution class Solution(object): def lengthOfLongestSubstring(self, s : str)-> int: used={} max_length = start= 0 for index,char in enumerate(s): if char in used and start = Target) Left++; (2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.) if(sum < Target) Right++; (3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다. if( sum == Target) count++; Sliding Window 슬라이딩 윈도우 알고리즘은 연속되는..
[백준] 9012.괄호 처음엔 합차방식을 사용해서 푸는걸로 생각했습니다. a = int(input()) for i in range(a): b = input() s = list(b) sum = 0 for i in s: if i == '(': sum += 1 elif i == ')': sum -= 1 if sum 0: print('NO') elif sum == 0: print('YES') 답은 맞지만 정석적인 방법은 스택을 사용하는거네요. num = int(input()) for i in range(num): input_data = input() bracket = [] for j in input_data: if j == "(": bracket.append(j) elif j ..
[백준] 9935. 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 파이썬 풀이 문자열 중복 문제는 "스택"을 사용하면 매우 편리합니다. 1. 입력된 문자열(string)을 한 글자(char)씩 스택에 push 2. 현재 글자가 폭발 문자열의 마지막 글자와 일치하면 스택의 top부터 폭발문자열과 일치하는지 확인 3. 폭발문자열이 만들어진다면 폭발문자열만큼 스택에서 pop 4. 1~3 반복 5. 스택이 비어있으면 FRULA를 출력, 비어있지 않다면 스..
[LeetCode]121.주식을 사고팔기 가장 좋은 시점(Best Time to Buy and Sell Stock) [문제] 한 번의 거래로 낼 수 있는 최대의 이익을 산출하라 ·입력 [7,1,5,3,6,4] ·출력 5 ·설명 1일 때 사서 6일 때 팔면 5의 이익을 얻는다. [처음 작성한 코드] class Solution: def maxProfit(self, prices: List[int]) -> int: res=0 for i,price in enumerate(prices): for j in range(i,len(prices)): res=max(prices[j]-price,res) return res 처음 떠오르는게 브루트 포스 방법이어서 작성해보았다. 당연히 타임아웃이다. 1행 리스트 문제를 풀 때 for문이 두개 이상 나오면 대부분 타임아웃이 되는 것 같다. 참고로 시간을 줄이기 위해서 enumerate를 애용하..
[LeetCode]238.자신을 제외한 배열의 곱 [문제] 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라 (나눗셈은 사용하지 않는다) ·입력 [1,2,3,4] ·출력 [24,12,8,6] 나눗셈을 사용할 수 없기 떄문에 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱해야 한다. 먼저 자기 자신을 기준으로 왼쪽 곱셈의 결과를 구현해보자. 위 그림과 같이 1일땐 왼쪽 곱셈 결과가 1, 2일때 1, 3일때 2, 4일때 6이 된다. nums=[1,2,3,4] out=[] p=1 #왼쪽 곱셈 for i in range(0,len(nums)): out.append(p) p=p*nums[i] print(out) · 출력 [1, 1, 2, 6] 다음은 오른쪽이다. 1일땐 오른쪽 곱셈 결과가 24, ..

티스토리툴바