전체 글

https://leetcode.com/problems/count-commas-in-range/description/ 문제 파악1 부터 n 까지 모든 정수를 '표준 숫자 형식' 으로 썼을때 사용되는 '쉼표' 의 총 개수를 구하는 문제다.표준 숫자 형식을 이해하기 위해 예시를 참고해보면 '1,000', '2,000,000' 같은 형태임을 알 수 있다. 접근 방법숫자를 문자열로 바꾼후, 쉼표의 갯수를 카운팅해서 반환한다. 문제 풀이class Solution: def countCommas(self, n: int) -> int: answer = 0 for num in range(1, n + 1): formatted = f"{num:,}" ans..

https://leetcode.com/problems/node-with-highest-edge-score/문제 파악방향 그래프가 주어진다(각 노드는 0~n-1 이고, 하나의 간선만 가지고 있다)edge score 는 i 를 가르키는 모든 노드 번호의 합이다.edge score 가 가장 큰 노드 번호를 반환해야 한다. (점수가 같다면 번호가 작은 노드를 반환한다) 접근 방법edge 를 순회하면서 각 edge(i) 를 가르키는 엣지들의 누적합이 제일 큰 노드 번호를 반환한다. 문제 풀이def edgeScore(self, edges: List[int]) -> int: n = len(edges) scores = [0] * n # 각 노드로 들어오는 index 합 누적 for i, targe..

https://leetcode.com/problems/harshad-number/description/ 문제 파악정수 x 가 주어졌을때 x 의 각 자리수 합을 구한다.주어진 정수의 각 자리수 합으로 해당 정수가 나누어 떨어진다면 : 해당 정수를 반환하고, 아니라면 -1을 반환한다. 접근 방법누적합을 구해서 비교하는 문제1 문제 풀이def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int: sum = 0 for ch in str(x): sum += int(ch) if x % sum == 0: return sum return -1

https://leetcode.com/problems/count-commas-in-range/description/문제 파악정수 배열이 주어질때, 합이 0되는 세 숫자의 조합을 모두 찾는 문제이다. 접근 방법반복문으로만 풀 수도 있지만 그러면 시간 복잡도는 O(n^3)이 된다.2sum 을 문제를 풀때 시간복잡도를 줄이기 위해 사용하는 방식으로 해시 풀이(java map/python dictionary), two pointer 두 가지 방법이 있었는데 여기서는 투포인터를 활용해 본다.흐름1. nums[i] 하나 고정2. 나머지에서 두 개 찾기 (투포인터)3. left = i+1, right = 끝4. 숫자의 합을 비교하면서 좁혀간다.# cursor 이미지(i, left, right) [-4, -1, -1,..

깔끔하게 결과 부터 정리해두고 느낀점을 적어볼까 합니다. 정리시작전 상태1. 코테 경험 없음2. 자료구조 이론만 아는 상태3. 시간복잡도 계산 가능 4. 실무 경력 있음 문제 풀이 프로그래머스 0~1단계 : 200문제기출 문제 위주 : 30문제 (플랫폼: leetcode / BOJ / 프로그래머스, 공부 방법: 인프런 강의(스터디) 참가) 시간투자하루 평균 4시간 미만 결과프로그래머스 1단계 수준 흔히 대기업 코테도 문제 없이 통과할 수준이 프로그래머스 2~3단계 사이 정도라고 하니 부족한 레벨에서 멈춘것 같습니다. 물론 더 시간을 투자하면 투자할 수록 능력은 올릴수 있겠지만 일본에 거주하며 꾸준히 나가는 월세와 생활비를 생각하면 코테 준비는 지금 레벨에서 일단락 짓고 취업을 하는게 맞다고 판단해서..

LeetCode - The World's Leading Online Programming Learning Platform문제 파악m x n 격자시작: (0,0)도착: (m-1,n-1)이동: 오른쪽 / 아래 만 가능 (중요)서로 다른 경로의 개수 구하기접근 방법어떤 칸 (i, j) 에 도달하는 방법은 아래 두개 뿐이다.위 (i-1, j)왼쪽 (i, j-1)점화식으로 표현하면 dp[i][j] = dp[i-1][j] + dp[i][j-1]초기값은첫 행은 전부 1 (오른쪽으로만 이동)첫 열은 전부 1 (아래로만 이동)코드 구현class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; // 첫..

LeetCode - The World's Leading Online Programming Learning Platform문제 파악cost[i]는 i번째 계단을 “밟을 때” 내는 비용이다 (주의: 마지막 계단은 밟지 않기 때문에 갈때 드는 비용은 없다)한 번에 1칸 또는 2칸 이동 가능하다.시작은 0 또는 1에서 가능하다.목표는 “top”(마지막 인덱스 다음 칸)까지 가는 최소 비용 구하기접근 방법LeetCode 70과 동일하게 현재 상태가 i-1, i-2에 의해 결정되는 계단 DP 패턴이다.코드 구현import java.util.Arrays;class Solution { private int[] cost; private int[] memo; public int minCostClimbin..

LeetCode - The World's Leading Online Programming Learning Platform문제 파악n개의 계단이 있음한 번에 1칸 또는 2칸 이동 가능n번째 계단에 도달하는 총 경우의 수 구하기전형적인 dp 문제이다 (키워드 접근. 배우게 된 점에서 추가 정리 예정)접근 방법마지막 계단에 갈 수 있는 방법은 결국 두가지 뿐이다.마지막 계단의 -1번째 계단에서 가는 방법마지막 계단의 -2번째 계단에서 가는 방법dp[i] = i번째 계단에 도달하는 방법의 갯수라 할때 아래처럼 base case 를 표현할 수 있다.dp[i] = dp[i-1] + dp[i-2]코드 구현import java.util.Arrays;class Solution { private int[] memo;..

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/문제 파악문자열 s가 주어진다.중복 문자가 없는 substring 중에서 가장 긴 길이를 반환한다.접근 방법길이 최대 5만 : O(n²) 불가 (선형 시간 필요)문자 종류는 제한적 : Set 사용 가능‘연속구간’, ‘중복제거’, ‘최대길이’ 란 키워드들 : 슬라이딩 윈도우 패턴을 떠올려야한다.윈도우란? [l ... r] = 현재 중복 없는 substring 구간흐름오른쪽 포인터 end 확장(새로운 문자 s[end]를 윈도우에 포함시키려 시도한다)중복 검사 (중복이 사라질때까지 왼쪽 포인터 start 이동, s[start]를 Set에서 제거한다)현재..

https://leetcode.com/problems/network-delay-time/description/문제 파악노드 1..n 이 있고, times[i] = [u, v, w] 는 유향 간선 그래프 u -> v 와 가중치(시간) w 를 의미한다.시작 노드 k 에서 신호를 보낼 때, 모든 노드가 신호를 받는 데 걸리는 최소 시간을 구해야한다.어떤 노드는 도달 불가능하면 -1 을 반환한다.시작점 k에서 모든 노드까지의 최단거리를 구한 뒤, 그 중 가장 큰 값(max dist) 이 정답이다.접근 방법가중치 w가 0 이상(양수) 이므로 전형적인 다익스트라(Dijkstra) 문제이다.times : 인접 리스트 그래프 구성 (u -> (v, w))다익스트라로 dist[1..n] 계산 (dist[k]=0, 나머지..