알루 코딩

이 문제는 비교적 간단하지만, 간단하게 풀면 시간초과에 걸리기 때문에 조금은 생각을 해야 하는 문제입니다. 문제에서는 정렬된 정수 배열 nums가 주어집니다. 배열의 각 요소 'i' 에 대해, 해당 요소와 배열 내 다른 모든 요소 'j' 들과의 절대 차이인 |nums[i] - nums[j]| 의 합을 구하는 것이 목표입니다. 이 문제에서 각 원소를 순회하면서 절댓값 계산을 하면 nums의 길이가 10**5 까지 있기 때문에 시간초과가 날 수 밖에 없습니다. 이 문제를 효율적으로 해결하기 위해서는 누적합(prefix)와 역누적합(suffix)를 사용해야 합니다. 누적합(prefix sum)과 역누적합(suffix sum)의 사용은 꼭 알아야 하는 알고리즘 중에 하나입니다. prefix sum에 대해 잠시 ..

해당 문제 'Count Nice Pairs in an Array'는 nums 라는에서 'nice pair'의 수를 찾는 문제입니다. 배열 안의 두 숫자 'i'와 'j' ('i' < 'j') 가 'nice pair'로 간주될 때, "nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])" 이 성립해야 합니다. 여기서 rev(x)는 숫자 x의 자릿수를 반전시킨 결과입니다. 문제의 핵심은 각 숫자와 그 숫자의 반전된 형태의 차이를 이용하는 것입니다. 이 차이가 동일한 숫자들의 쌍이 'nice pair'를 형성합니다. 우선 코드부터 살펴보겠습니다. class Solution(object): def countNicePairs(self, nums): mod = 10 ** 9 + 7 ..

문제를 먼저 해석해봅시다! 문제에서는 직사각형 모양의 판에 치즈가 표시되어 있습니다. 치즈는 1로 표시되며, 치즈가 없는 부분은 0으로 표시됩니다. 각 시간 단위마다 외부 공기와 접촉한 치즈가 녹아 없어지는데요, 이 때, 치즈의 내부에 있는 공기는 외부 공기로 간주되지 않는게 핵심입니다! 문제의 목표는 모든 치즈가 녹는 데 걸리는 시간과 마지막으로 녹기 전의 치즈 조각의 수를 찾는 것입니다. 이를 위해 BFS 알고리즘을 사용합니다. BFS는 주로 그래프의 최단 경로를 찾거나, 2차원 배열에서 특정 조건에 따라 요소를 탐색할 때 사용되는 알고리즘입니다. 이 문제에서는 BFS를 이용해 보드의 가장자리부터 시작하여 외부 공기를 탐색하고, 이를 통해 치즈의 녹는 경계를 식별합니다. 외부의 공기와 내부의 공기를 ..

이 문제는 DFS와 BFS를 결합한 흥미로운 접근 방식을 요구합니다. 이 문제의 핵심은 "가능한 한 많은 영역을 안전하게 보호하는 벽의 배치를 찾는 것" 입니다. 여기서 주목해야 할 점은 "모든 벽의 조합을 시도"해보고, "각 경우에 대해 바이러스가 얼마나 퍼지는지를 시뮬레이션"해야 한다는 것입니다. 이를 위해서 DFS를 사용해 벽을 세우고, BFS로 바이러스의 확산을 시뮬레이션합니다. 초기 접근 방법은 아래와 같습니다. from collections import deque import sys input = sys.stdin.readline # 벽을 3개를 세운다. -> 모든 경우의 수를 다 세어본다 : dfs # 바이러스를 퍼뜨려본다. # 0의 개수를 구한다. # 이 값을 max값과 계속 비교하면서 최..

해당 문제는 NBA 농구 경기에서 특정 팀이 얼마나 오랫동안 리드했는지를 계산하는 문제입니다. 이 문제를 풀 때는 득점 순서, 득점 시간, 현재 리드 상태를 정확히 추적하는 것이 중요합니다. 문제를 딱 봤을 때, 뭔가 "득점이 성공된 시간 순서"대로 "1팀과 2팀 중에 어떤 팀이 넣었는지" 알아야 할 것 같습니다. 그리고, 득점을 함으로써 앞서가는지 혹은 동점이 됐는지도 체크"해야 하는 것이 중요합니다. 동점이 된 순간부터는 어느 팀도 리드하지 않는 상태가 되기 때문입니다. 이렇게, 주의할 점은 아래와 같이 요약할 수 있겠습니다. 경기 시간 처리 : 경기 시간은 "시:분" 형식으로 주어지며, 이를 총 분으로 변환해야 합니다. 상태 관리 : 경기의 현재 상태(동점, 팀1 리드, 팀2 리드)를 추적해야 합니..