old/Algorithm Solving (58) 썸네일형 리스트형 LeetCode 215. Kth Largest Element in an Array 자바 문제 풀이 문제 Kth Largest Element in an Array - LeetCode 문제 해결 방법 -k번쨰로 큰 수를 찾는 문제 -내림차순(큰수부터 작은수)으로 정렬을 한다음, k번째 수를 리턴하면 된다. -Arrays.sort와 comparator를 사용하면 쉽다. 어레이를 정렬한다 k번쨰 수를 리턴한다 -PriorityQueue를 사용하는 방법도 있다. PriorityQueue에 k만큼 넣는다. k보다 많이 입력되면 가장 작은 수를 제거한다 모두 입력되고 나면 가장 작은 수가 바로 k번째 수이다. -만약 위 메서드들을 사용해서는 안된다고 한다면, 퀵솔트를 구현하라는 문제이다. -퀵솔트는 엄밀하게 따지면, O(n log n)이지만, 평균적으로 O(n)이라고 표현한다. 즉, 위 문제는 퀵솔트를 구현할수 .. LeetCode 1108. Defanging an IP Address 자바 문제 풀이 문제 Defanging an IP Address - LeetCode 문제 해결 방법 입력받은 ip address에서 .을 [.]으로 바꾸는 문제입니다. 스트링의 replace 메서드를 알고 있으면 쉽게 바꿀수 있습니다. replace메서드를 알고 있냐고 묻는 문제 입니다. Github Link https://github.com/eunhanlee/LeetCode_1108_DefanginganIPAddress_Solution.git replace 시간복잡도: O(n), 공간복잡도: O(1) class Solution { /** * 주어진 IP 주소에서 마침표를 지정된 대체 문자열로 대체하여 수정합니다. * * @param address 주소를 수정할 IP 주소 * @return 수정된 IP 주소 */ pub.. LeetCode 2011. Final Value of Variable After Performing Operations 자바 문제 풀이 문제 Final Value of Variable After Performing Operations - LeetCode 문제 해결 방법 전위연산자와 후위연산자를 주는것은 함정입니다. 이 문제는 스트링을 비교하는것과 숫자를 비교하는데 차이점을 알고 있느냐고 묻는 문제입니다. 하지만 이와 동시에 여러가지 최적화할 여지를 남겨두었기에 유저가 최적화를 얼마나 할수 있는지, 논리적으로 얼마나 할수있는지 시험하는 문제이기도 합니다. 기본적으로 자바에서 스트링을 비교할떄는 반드시 equal을 써야합니다. 문제에서는 피라미터가 반드시 "++X", "X++", "--X", or "X--" 중 하나라고 말했기 때문에 굳이 equalsIgnoreCase같은 메서드를 사용할 필요가 없다. 여기서 조금더 최적화를 하자면, 전부 .. LeetCode 169. Majority Element 문제 풀이 문제 Majority Element - LeetCode 문제 해결 방법 -O(n),O(1)으로 풀어야합니다 -언제나 majority element가 존재합니다. -majority element의 정의는 list length/2 < element입니다 -아래 방법은 공간복잡도가 O(n)이므로 HashMap은 사용할수 없습니다. 해쉬맵으로 모든 숫자개수를 카운트하며 어레이를 iterate합니다. 카운트된 숫자가 가장 높은수를 찾아서 리턴합니다. -아래방법은 시간 복잡도가 O(n log n)이므로 사용할수 없습니다. 어레이를 정렬합니다.(Arrays.sort(nums);) 어레이에서 nums[nums.length/2]를 리턴합니다. 과반수 이상인 숫자가 존재하므로, 중간값은 반드시 과반수에 해당하는 값입니다... 136. Single Number 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 a linear runtime complexity =O(n) use only constant extra space=O(1) 처음 생각했던 방법은 해쉬맵을 만들어서 두번 나오지 않는것을 생각했으나, 공간복잡도를 O(1)이여야 하므로 사용할수 없음. O(n) 이나 O(2n)이나 같은 O(n)이므로, 정렬을 하고 비교하는 방식으로 가능함 정렬을 한다 다음에 나오는 수가 같지 않다면 리턴 시간복잡도: O(n), 공간복잡도: O(1) https://github.com/eunhanlee/leetcode_136_Single_Number import java.util.*; class Solution { /** * 배열에서 single number를 찾는 메소드입니다. * * @.. 118. Pascal's Triangle 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 가능한 케이스 if startpos or endpos, add end else currpos = lastList[prevpos+currpost] 필요한것= 전단계 리스트, 전단계 리스트 길이 or 현재 길이 조심해야 할것, list에서 add()는 기본적으로 shallow copy임. 즉, 모든 리스트를 돌면서 첫번째와 마지막은 무조건 1을 넣고, 아니라면 전에 넣은 리스트를 참고삼아 더해서 현재리스트에 넣으면 파스칼의 삼각형이 나온다. 시간복잡도: O(n), 공간복잡도: O(n) https://github.com/eunhanlee/leetcode_118PascalsTriangle import java.util.*; class Solution { /** * 입력된.. 48. Rotate Image 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 자리를 로테이션 한다는 뜻은, 각 자리에서 옮길 자리가 정해져 있다는 뜻이다. n이 3일 경우 예를 든다면 아래와 같다 (0,0)->(0,2) (0,2)->(2,2) (2,2)->(2,0) (2,0)->(0,0) (0,1)->(1,2) (1,2)->(2,1) (2,1)->(2,1) (1,0)->(0,1) 위 규칙은 n에서 멀어진 만큼으로 계산이 가능하다. 첫번쨰 루프 n=3 y축 멀어진 만큼의 거리 = i = 0 x축 멀어진 만큼의 거리 = j = 0 시작점 = (i,(i+x축 멀어진 만큼의 거리)) = (0,0) ((n-1-x축 멀어진 만큼의 거리-y축 멀어진 만큼의 거리),i)=((3-1-0-0),0)=(2,0) ((n-1-y축 멀어진 만큼의 거리),(n-1-.. 22. Generate Parentheses 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 all combinations 조합 = 대부분의 경우, 재귀함수 DFS 반드시 ( 가 open한 다음 ) close 해야함 (조건에 맞는 조합만=백트래킹 알고리즘) if(open 이전 1 ··· 3 4 5 6 7 8 다음 목록 더보기