알루 코딩

오늘은 비교적 쉬운 문제를 가져와봤습니다. 하지만, 분명 배울점은 있는 문제이기에 소개해드립니다. 해당 문제는 2D 평면상의 여러 점들이 주어졌을 때, 모든 점들을 순서대로 방문하는데 필요한 최소 시간을 계산하는 것이 목표입니다. 각 이동에서는 상하좌우 또는 대각선으로 한 칸씩 이동할 수 있습니다. 이 문제에서 저는 처음에 유클리드 거리를 사용했습니다. 한 번 이동할 때마다 1초가 걸린다고 했으니, 그냥 거리계산으로 접근했습니다. 두 점이 같은 기울기에 있다면, 대각선으로 가는 것이 가장 최단이겠고, 그렇지 않다면, 유클리드 거리를 사용하는 것인 줄 알았었죠. 그래서, 처음 작성했던 코드는 아래와 같습니다. class Solution(object): def minTimeToVisitAllPoints(se..

위 문제는 그리디 문제입니다. 리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠. 맨 처음에 저는 O(n^2))의 복잡도로 문제를 풀었습니다. 그래서, 시간초과의 문제에 걸렸습니다. 제약조건을 보면 prices의 길이가 최대 100000이기 때문에, O(n^2)의 복잡도로 풀어버리면 10의 8승을 넘기 때문에 시간초과에 걸리는 것은 당연한 소리겠죠! 처음, 시간초과에 걸렸던 코드는 아래와 같습니다. class Solution: def maxProfit(self, prices: List[int]) -> int: is_reversed_sorted = all(prices[i] >= prices[i+1] for i in range(len(prices)-1)) if is_reversed_sorted: retur..

이 문제는 주어진 문자열 t 안에 s문자열이 있는지 아닌지를 판단하는 문제입니다. 예를 들어서, t가 ahbgdc 이고, s가 abc 라면, ahbgdc에서 h,g,d,를 제거하면 abc가 되므로 true를 반환합니다. 반면, 만약 t가 abcde이고, s가 aec 라면, abcde 문자열에서 어떤 수를 써서라도 aec를 만들 수 없기에 false를 반환합니다. 즉, t의 원래의 문자열에서 순서는 유지한 채 수열을 이루는 항 중에 일부만 모아 s가 만들어진다면, true를 반환하고, 그렇지 않다면 false를 반환하면 됩니다. 코드를 통해 살펴보죠. class Solution: def isSubsequence(self, s: str, t: str) -> bool: idx = 0 cnt = 0 if len..

주어진 문자열 s와 t가 동형사상이라면, true를 반환하고, 그렇지 않으면, false를 반환하는 문제인데요! 다양한 문제풀이가 있을거에요. 딕셔너리를 이용해서 풀어도 되고, 자바를 활용한다면 해시맵으로도 풀 수 있을 것 같습니다! 저도 처음에는 딕셔너리로 접근을 했다가, index의 위치만 저장하는 리스트로 풀어도 되겠다 싶어서 리스트만을 이용했습니다. 코드를 보면서 살펴보겠습니다. class Solution: def isIsomorphic(self, s: str, t: str) -> bool: answer = False if len(s) != len(t): return answer else: s_check = [] t_check = [] for i in s: s_check.append(s.index..