하이 나윤

Valid Palindrome https://leetcode.com/problems/valid-palindrome/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 방법 replaceAll을 사용해서 공백, 특수문자 제거 후 대문자로 변환하였다. 그리고 앞에서부터 하나씩 비교하는 방법 선택 다 해도 O(n)이고 문자열의 최대 길이가 2 * 10^5 라고 ..

https://leetcode.com/problems/permutations/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 배열이 주어지면 순열을 아무 순서로나 반환하면 되는 문제였다. 통과 코드 풀이: Back-tracking 백트래킹을 이용해서 이미 사용한 인덱스인지 체크했고 체크해야하는 인덱스 순서를 파라미터로 보내서 ..

https://leetcode.com/problems/jump-game-ii/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 점프 게임을 할 건데 게임 종료 조건은 배열의 맨 끝에 가장 적게 뛰어서 도착하는 것이고 배열에 나와있는 숫자보다 작거나 같게 뛸 수 있다. 예를 들어 nums = [2, 3, 1, 4, 4] 라는 배열..

Start Ladder 문제 정답 코드 Queue에 0부터 넣고 1, 2를 더해가며 가짓수를 찾는 방법을 생각해냈다. 결과는 시간초과 왜 이 문제가 피보나치에 있는 건지에 대해 고민했는데, 사다리를 오르는 방법이 F[n] = F[n - 1] + F[n - 2]를 따르고 있었다. 아래와 같이 피보나치 방법을 적용해서 문제를 풀었다. 똑같은 결과처럼 보이지만.. 아예 똑같은 결과는 아니다. 시간 안에 문제는 풀렸지만 답이 틀린 경우이다. got 0으로 나온 것들이 있는 것을 보면 구해야하는 피보나치 수보다 적게 구한 것 같다. 그.. modulo 법칙 중에 이런 것이 있다. 위의 법칙을 적용해서 문제를 다시 풀어보았다. 정확도는 100%로 맞았지만 timeout이 발생했다. 피보나치 수열을 만드는 횟수를 줄..

Start FibFrog에서 다시 시작.. FibFrog 문제 정답 코드 1. array A의 크기가 100,000이라는 것을 알고 피보나치 수열을 27개만 구함. 0부터 26까지 구했고 26번째 피보나치 수가 아마 123,000쯤..? 되었던 것 같다. 2. 큐를 쓰든가 해서 시간복잡도를 줄여야하고 array A를 for문으로 반복하며 이전 출발 index와 가려고 하는 index의 차이가 피보나치 수만큼인지를 파악하는 방법보다는 1번에서 구해놓은 피보나치 수 배열을 for문으로 돌려서 이전 출발 index에서 피보나치 수를 더한 수가 array A에서 1인지를 파악하는 방법으로 접근해야한다. 이렇게 하면 시간복잡도의 늪에서 벗어날 수 있다. 아래는 FibFrog를 풀기 위한..생각의 늪이었다.. 이렇..

Start FibFrog 문제 현재 시간복잡도로 인해 문제 해결이 안 나고 있는 상황인데 이 상황을 해결해보겠습니다.. 큐를 적용하는 방식을 참고해서 문제를 풀었는데, 동일하게 58%가 나왔다.. 뭘까..

Start 이전 포스팅인 [2023-02-15] 마지막에 이런 말을 하면서 사라졌는데 코딜리티 안에서는..어차피 도망쳐봤자 지옥밖에 없어서 해당 문제를 부수고 넘어갈 예정이다. CommonPrimeDivisors 문제 정답 코드 1. 유클리드 호제법을 이용해서 A와 B의 최대공약수를 구한다. 2. A와 1에서 구한 최대공약수의 최대공약수를 구한다. 3. 2에서 구한 최대공약수가 존재한다면 A를 2의 최대공약수로 나눠 몫을 구한다. 4. 몫이 1에 도달한 경우 최대공약수에 나타난 소수 외 다른 prime divisor는 존재하지 않는다는 의미이다. 5. 최대공약수가 1인 경우 최대공약수가 없다는 의미이다. -> 추가 소수가 존재한다는 의미이다. 2~5 과정을 반복한다. A와 B 모두 몫이 1이 되면 1에서..

Start CommonPrimeDivisors 문제 어제 답을 보고도 이해하지 못했기 때문에 다시 이해하는 시간을 가질거다.. 틀린 답을 내놓고 있다는데 이해가 잘 가지 않는다..

Start CommonPrimeDivisors 문제 풀다가 못 풀어서 다른 사람의 풀이를 봤는데 이것도 이해를 못했다.. 일단 gcd(a, b) = gcd(b, a%b)는 이해했고 gcd(a, b) = 1이면 공유하는 소수가 없다는 것도 이해했다. FibFrog 문제 끄엉

Start ChocolatesByNumbers 문제 N과 M의 최대 공약수를 구해야하는 문제였다. 유클리드 호제법을 이용해서 빠르게 최대 공약수를 구했다. CommonPrimeDivisors 문제 각각 나눠지는 소수가 같은지 파악하는 문제이다. 아니 근데..왜이렇게 풀었는지 이해가 안간다.. // you can also use imports, for example: import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int solution(int[] A, int[] B) { int resul..