오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 나의 풀이 처음엔 그냥 2중 for문을 써서 각 시작점마다 보석 종류를 모두 포함하는 끝지점을 검출하면 break하고 다음 시작점부터 탐색하는 알고리즘을 짰는데 역시나 시간초과에 걸렸다. 개선한 풀이는 다음과 같다. start, end의 투포인터를 사용한다. 처음엔 둘다 0번째 인덱스로 초기화 한다. start부터 end까지의 보석이 전체 보석 종류를 포함하면 start를 증가시키고, 모자라면 end를 증..

문제 https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 나의 풀이 n(총 버스 수)과 t(버스 간격)를 사용해 버스가 정차하는 시간 저장 timetable의 시간 모두 분으로 변환 후 오름차순으로 정렬 m(버스 수용 가능 최대 인원)을 이용해 각 버스가 정차하는 시간마다 탈 수 있는 사람 저장 가장 늦..

트리를 순회하는 방법은 preorder, inorder, postorder로 크게 3가지가 있다. 여기서 소개하려고 하는 내용은 이러한 순회를 "어떻게" 구현하는지에 관한 것이다. 가장 보편적인 것은 물론 재귀를 이용하는 것이나, 반복문을 통해서도 얼마든지 구현 가능하다. 참고로 트리노드의 정의는 아래와 같다고 하자. # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right 편의상 inorder를 구현하는 것으로 한다. 재귀(Recursive)를 통한 구현 class Solution: # ..

파이썬에서 사전순으로 문자열들을 정렬하기는 쉽다. sort()를 사용하면 정렬이 된다. sorted()를 사용하면 원본 리스트를 변경하지 않고 정렬이 가능하다. a = ['cd', 'ef', 'ab'] a.sort() print(a)# ['ab', 'cd', 'ef'] 하지만 만약 문자열 자체를 정렬할 필요가 있는 경우 파이썬에서는 어떻게 해야할까? 예컨대, s="adfe"라는 문자열을 정렬해서 "adef"로 만들려고 한다. s = "adfe" s1 = s.sort()# wrong s2 = sorted(s)# ['a','d','e','f'] s3 = ''.join(sorted(s))# "adef" 먼저 그냥 s.sort()를 쓰면 안된다. - str type에 sort()라는 메소드가 없기 때문(이유는 ..

linked list를 정렬하는데 추가적인 메모리를 쓰지 않고 O(nlogn)의 시간복잡도로 하기 위해선 어떻게 해야할까? 답은 merge sort를 쓰면 된다!!!! 그런데 조금 복잡한 부분이 일반적인 array의 경우 index로 분할하여 정렬하면 되는데 linked list의 경우 어떻게 나누어야 하는지이다. 이를 위해선 3개의 포인터를 쓰면 된다. 그 세 포인터를 각각 p,slow,fast라 해보자. p,slow,fast가 차례로 한 칸씩 전진하는데 p->slow->fast의 순서대로 나아간다. 이 때, fast가 None이거나 fast.next가 None이 되면 p.next를 None으로 만들어주고 p와 slow로 linked list를 분할한다. 그럼 p가 가리키는 연결리스트가 l이 되고, s..

nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까? 답은 (1,2), (2,1)로 2개이다. 그렇다면 이를 구하기 위한 알고리즘은 무엇일까? 이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자! 가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다. 이를 풀기 위해선 dp를 사용하면 된다. 위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다. 관련 문제 leetcode.com/problems/target-sum/ Target Sum - LeetCode Level up y..

"abc"와 "bca"는 Anagram이다. anagram이란 이처럼 size가 같고, 같은 알파벳으로 이루어진 문자열을 말한다. 그럼 이러한 anagram을 찾으려면 어떠한 알고리즘을 써야할까? 가령 s="abcdebacb", p="cab"일 때, s에서 p와 anagram인 문자열의 인덱스를 찾는다고 해보자. 그럼 어떠한 것이 같아야 anagram이라고 할 수 있을까? size - p의 사이즈만큼 s를 slicing하면 되므로 간단!! 사용하는 알파벳 종류 등장하는 알파벳의 빈도수 이 땐, 2와 3을 비교하기 위해선 비트마스크를 사용하면 된다. 알파벳은 총 26개이므로 26개의 array를 만들고 각 알파벳의 등장 빈도수만큼 + 해준다. p="cab"이므로 p의 비트마스크 p_mask=[1,1,1,0..

문제설명 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 순위를 확실히 알기 위해선 해당 사람이 이기고 진 정보의 갯수 합이 n-1개가 되어야 한다. 여기서 중요한 점은 A를 이긴 사람은 A에게 진 사람을 이기고 A에 진 사람은 A에게 이긴 사람에 진다 는 것이다. def solution(n, results): answer = 0 # win[i] : i가 이긴 사람의 집합 # lose[i] : i가 지는 사람의 집합 win, lose = {}, {} for i in range(1, n+1): win[i], lose[i] = ..