개발의 꿈을 개발하는 꿈을 개발하려는 꿈

목차 개요 Minimum Time to Visit a Cell In a Grid - LeetCode m*n의 배열이 주어진다. 좌상단에서 우하단으로 가고 싶은데 이때 한 칸을 이동할 때마다 1초의 시간이 지난다. 그리고 배열의 원소는 최소 몇 초부터 해당 자리를 지나갈 수 있는지를 나타낸다. 우하단으로 가는 최소 시간을 구하고, 구할 수 없다면 -1을 반환. 풀이 문제가 처음에는 방문한 위치를 재방문하면 안 된다는 말이 없어서 거기에 이상함을 느꼈다. 그렇다면 일단 한번이라도 이동을 할 수만 있다면 거기에서 계속 왔다갔다 하면서 시간을 소모한 후에 높은 시간이 요구되는 칸을 지나갈 수 있다는 말 아닌가? 아무튼 처음에는 단순 bfs로 풀 생각을 했으나 시간 초과가 났다. 그리고 솔루션을 찾아봤다. 문제의..

목차 개요 Find the Maximum Number of Marked Indices - LeetCode nums 배열이 주어진다. 이 배열에서 위 수식을 만족하는 인덱스 쌍에다 마크를 칠할 것이다. 한번도 마크되지 않은 쌍만 쌍이 될 수 있다. 이런 쌍이 최대 몇 개까지 나올 수 있는지 반환하라. 풀이 처음에는 그냥 최대 원소를 반환하라는 줄 알고 조금 헤맸다. 결국 쌍을 찾으면 되는 문제이고 그 쌍의 최대값은 nums 배열의 절반일 것이다. 그 점에서 착안해서 문제를 접근하자. 어차피 어떤 배열이 들어와도 정답의 최대값은 해당 배열의 길이의 절반이다. 위의 정렬된 배열에서 i와 j쌍(i는 j보다 작다)을 찾는다고 생각을 해보자면 c가 i가 되는 경우가 있을까? c가 i로써 한 쌍에 속하는 경우는 나올..

목차 개요 Find the Divisibility Array of a String - LeetCode 어떤 수가 주어지면 그 수를 가장 높은 자리부터 하나씩 늘려가며 수를 만들고 그 수가 m에 나눠지는지에 따라 div 배열을 만들어 반환하기. 풀이 class Solution: def divisibilityArray(self, word: str, m: int) -> List[int]: ans = [] n = len(word) i = 1 while i List[int]: ans = [] n = len(word) curr = 0 for i in word: prev_divisible = ((curr % m) * (10 % m)) % m curr = (prev_divisible + (int(i) % m)) % m..

목차 개요 Left and Right Sum Differences - LeetCode 0을 인덱스로 시작하는 배열이 있다. 이 배열에 대해 leftsum과 rightsum을 구하고 그 둘의 차의 절대값을 원소로 하는 answer 배열을 구하라. leftsum과 rightsum은 이전 원소의 누적합. 자세한 건 예시 참조. 풀이 문제에 나온 그대로 따라가면 된다. 대충 하면 3개의 반복문을 쓰게 되는데, 그렇게 해도 시간 초과는 나지 않는다(내가 이걸 썼다). 그렇지만 한번의 반복문으로 구하는 방법도 있다. 코드 class Solution: def leftRigthDifference(self, nums: List[int]) -> List[int]: leftsum = [0] rightsum = [0] for..