솧로그

https://leetcode.com/problems/count-the-hidden-sequences/description/class Solution { public int numberOfArrays(int[] differences, int lower, int upper) { long a = 0, ma = 0, mi = 0; for (int d: differences) { a += d; ma = Math.max(ma, a); mi = Math.min(mi, a); } return (int)Math.max(0, (upper - lower) - (ma - mi) + 1); }}

https://leetcode.com/problems/happy-students/description/class Solution { public int countWays(List arr) { Collections.sort(arr); int ways=0, ans=0; if(arr.get(0)>ans){ ways++; } ans++; for(int i=1;ians){ ways++; } ans++; } if(arr...

https://leetcode.com/problems/h-index-ii/description/ class Solution { public int hIndex(int[] citations) { int n = citations.length; int start = 0; int end = n-1; while(start

https://leetcode.com/problems/find-if-path-exists-in-graph/description/class Solution { boolean[] vis; List> gr; void dfs(int node) { if (vis[node]) return; vis[node] = true; for (int child : gr.get(node)) { if (!vis[child]) dfs(child); } } public boolean validPath(int n, int[][] edges, int source, int destination) { vis..

https://school.programmers.co.kr/learn/courses/30/lessons/49190 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 주의할 점은 다음과 같다.방이 되기 위해선 다음 두 조건을 모두 만족해야 한다.이미 방문한 노드를 재방문 하는 경우해당 간선이 처음 생성된 간선인 경우이차원 배열을 사용하려면 new int[200,001][200,001]의 크기의 배열이 필요하다. 따라서 이차원 배열을 사용할 수 없으며, 대신 Map을 사용한다. 다음과 같이 교차점이 있을 경우 위 로직대로 생각하면, 방이 1개인 것으로 계산된다. 즉..

https://leetcode.com/problems/k-th-smallest-prime-fraction/submissions/1284723688/ class Solution { public int[] kthSmallestPrimeFraction(int[] arr, int k) { int len = arr.length, numerator = -1, denominator = -1, fractionPosCovered = 0; double left = 0, right = 1; while(fractionPosCovered != k) { fractionPosCovered = 0; doubl..

https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 완전탐색으로 풀 경우, 50,000개의 바위 중 n개를 고르고(50,000 ^ n) 선택된 n개의 바위 간 간격을 구하므로(n) 약 50,000 ^ n * n의 시간복잡도를 갖는다. 따라서 시간 초과가 날 것이므로 다른 방법으로 풀어야 한다.우선, 문제가 요구하는 것은 바위 간 간격의 최솟값 중 최댓값을 구하는 것이다.이 문제는 이분 탐색으로 풀어야 하는데, 이분 탐색은 어떤 값을 left와 righ..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dp로 풀 수 있는 문제로, 주요 포인트는 다음과 같다.인접한 두 집을 털 수 없다. 따라서 i번째의 집까지 훔칠 수 있는 최대 금액을 dp[i]라고 했을 때, dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])이다.그런데 마지막 집에서 문제가 발생한다. 만약 첫 번째 집을 털었으면 마지막 집을 털 수 없고, 그렇지 않으면 마지막 집을 털 수 있다. 따라서 dp에 채워진 최대..

https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 주어진 식에 대한 연산의 최댓값을 구하는 문제이다. 예를 들어 1 - 3 + 5 - 8라는 식이 주어졌을 때 괄호의 위치에 따라 여러 연산 결과가 나오는데 그 중 최댓값을 구하면 된다.이때 다음과 같은 dp 개념이 사용된다.A + B의 최댓값을 구하려면, A와 B 둘 다 최댓값이어야 한다.A - B의 최댓값을 구하려면, A는 최댓값, B는 최솟값이어야 한다.위와 같이 - 연산자의 뒤에 있는 수는 최솟값..

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dp 기본 문제이다. 다음과 같이 한 숫자를 기준으로 봤을 때 왼쪽과 합쳐질 수도 있고 오른쪽과 합쳐질 수도 있다. 그리고 더 큰 값으로 합치면 된다. dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j] 이를 코드로 구현하면 다음과 같다. import java.util.*;class Solution { public int solution(in..