본문 바로가기

Algorithm

(120)

[BOJ] 비슷한 단어 해설 코드 N = int(input()) compare = list(input()) ans = 0 for _ in range(N-1): compare_word = compare[:] check_word = list(input()) for _ in range(len(check_word)): a = check_word.pop(0) if a in compare_word: compare_word.remove(a) else: check_word.append(a) A = len(compare_word) B = len(check_word) if (A==0 and B==0) or (A==1 and B==0) or (A==0 and B==1) or (A==1 and B==1): ans += 1 print(ans) 분석 ..

[Leetcode] Group Anagrams 해설 코드 class Solution(object): def groupAnagrams(self, strs): d = {} for str in strs: key = ''.join(sorted(str)) if key not in d: d[key] = [str] else: d[key].append(str) return d.values() 분석 > 이런 방식으로 풀려고 했지만, value값에 리스트가 추가가 안되어서 계속 풀지 못했다. 애너그램 관계에 있는 단어들은 정렬했을 때 같다는 것을 이용하여 해시맵의 key값에는 이들을 정렬하여 문자열로 만든 것을 넣고, value값에는 같은 key를 가진 단어들을 배열로 append하면 내가 원하는 해시맵을 만들 수 있었다. Group Anagrams - LeetCod..

코딩테스트 스터디 4주차 1. 2016년 def solution(a, b): date = ['FRI','SAT','SUN','MON','TUE','WED','THU'] month = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] cnt = 0 for i in range(a-1): cnt += month[i] ans = (cnt + b) % 7 return date[ans-1] 2. 문자열 다루기 기본 def solution(s): if len(s) == 4 and s.isdigit(): return True elif len(s) == 6 and s.isdigit(): return True else: return False 3. 문자열 내림차순으로 배치하기 def solution(s): s..

코딩테스트 스터디 3주차 1. 다트게임 def solution(dart): ans = [] for i in range(len(dart)): if dart[i] =='S': if dart[i-1] == '0' and dart[i-2] == '1': ans.append(10) else: ans.append(int(dart[i-1])) elif dart[i] == 'D': if dart[i-1] == '0' and dart[i-2] == '1': ans.append(10**2) else: ans.append(int(dart[i-1])**2) elif dart[i] == 'T': if dart[i-1] == '0' and dart[i-2] == '1': ans.append(10**3) else: ans.append(int(dart[i-..

[BOJ] 랜선 자르기 나의 코드 a,b = map(int,input().split()) arr = [int(input()) for _ in range(a)] k = 1 ans = [] while True: imp = [] for num in arr: t = num // k imp.append(t) k += 1 if sum(imp) == b: break while True: ans = [] k += 1 for num in arr: ans.append(num//k) if ans != imp: break print(k-1) 분석 > 시간초과 날 것을 알고 있었지만, 효율성을 제외하고 일단 문제를 풀어보기 위해서 풀어보았다. 당연히 결과는 시간초과. 해설 코드 a,b = map(int,input().split()) arr = [in..

[BOJ] 가장 긴 증가하는 부분 수열 코드 t = int(input()) num = list(map(int,input().split())) dp = [1] * t for i in range(t): for j in range(i): if num[i] > num[j]: dp[i] = max(dp[i],dp[j]+1) # 현재의 dp값과 이전 수의 dp값에 1을 더한 값을 비교 후 더 크면 갱신 print(max(dp)) 분석 > LIS(Longest Increasing Subsequence) 알고리즘으로 원리는 간단하다. 현재의 수 (num[i]) 가 비교대상이 되는 이전의 수 (num[j]) 보다 클 때만, 비교 대상이 되는 수의 dp값에 1을 더한 값을 갱신하는 것이다. 그렇게 이전의 수들을 모두 탐색하면, 최종적으로 현재 수의 dp값은 이..

[BOJ] 올림픽 코드 a,b = map(int,input().split()) world = [] for _ in range(a): num = list(map(int,input().split())) world.append(num) world.sort(key = lambda x: (x[1],x[2],x[3]),reverse=True) for i in range(len(world)): if world[i][0] == b: index = i for i in range(len(world)): if world[index][1:] == world[i][1:]: print(i+1) break 분석 > 새롭게 알게 된 개념 중 하나는, 배열을 순서대로 기준을 정해서 정렬을 할 때 (x[1],x[2],x[3]) 와 같이 람다함수를 이용해..

[BOJ] 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공..

이전 1 2 3 4 5 6 ··· 15 다음

티스토리툴바