살림하는 개미와 개발하는 배짱이

안녕하세요. Ruk 입니다. Medium난이도의 Next Permutation 문제에 대하여 접근과 풀이를 한번 해보려고 해요. 문제를 보면 조건은 단간합니다. 배열로 숫자를 입력 받았을 때 그다음 큰 수로 변환, 최대값이면 정렬 입니다. 1,2,3,4,5,6,7 -> 1,2,3,4,5,7,6 인 것 이죠. 어떻게 알고리즘을 짜볼지는 간단하게 정했습니다. 1. for문으로 length의 길이부터 숫자가 커지는지 체크합니다. (7번 라인) 2. 커지지 않는 부분이 있다면 point를 체크, 없다면 정렬 후 리턴. (14번 라인) 3. for문을 다시 돌며 point 보다 큰 숫자를 찾습니다. (18번 라인) 4. 해당 숫자를 스왑 시켜주고(20번 라인), 뒷부분을 정렬하여 가장 작을수로 만들어줍니다.(21..

안녕하세요. Ruk 입니다. LeetCode medium난이도의 Integer to Roman 의 풀이과정을 한번 작성해보려고 해요. 해당 문제는 미디움이지만 이지난이도라고 생각하는데요. 이유는 알고리즘이 복잡하기보단 문제의 해석이 더 중요한 문제였다고 생각하기 때문이에요. (사실 로마숫자에 대한 이해?) 조건은 간단합니다. Simbol 우리가 아는 그 로마문자 숫자값과 동일합니다. 숫자를 주워졌을 때 해당 로마문자를 반환하는 것이 문제의 핵심입니다. 여기서 숫자를 그냥 1, 5, 10, 50 등으로 나누면 쉽겠지만 이 문제는 로마문자라는 함정이 있죠? 네 IV, IX. XL, XC 등 4, 9, 40, 90 등 숫자에 대한 예외가 발생하는 것 입니다. 하지만 IV를 하나의 문자라고 생각하고 숫자 크기별..

안녕하세요. Ruk 입니다. Median of Two Sorted Arrays 문제에 대하여 풀이를 한번 써보려고 해요. 이번 문제는 난이도가 Hard이지만 easy처럼 느껴지는 이상한 문제였내요. 문제의 조건은 조건은 입력받은 두 배열을 머지하여 중앙값의 평균을 구하는 문제였습니다. nums1.length == m nums2.length == n 0

안녕하세요. Ruk 입니다. LeetCode의 Add Two Numbers Longest Palindromic Substring 문제를 풀어본 내용 공유하려 해요. 문제의 조건은 거꾸로해도 똑같으면서 가장 긴 문자열을 찾는 문제 입니다. 과거에 푼 적이 있는데 오랜만에 다시 풀어보았습니다. 네,,,,,, 약 100배나 속도가 더 걸리는 알고리즘을,,,,,,,, 같은 메모리를 사용하여 같은 결과물을 만들지만 속도차이가 이렇게 심하게 날 수도 있네요. 1030ms가 걸린 코드 입니다. b(n^3)을 ㅎㅎㅎㅎ 당당하에 for문 중첩하여 돌렸고, checker에서도 1번 돌게되니 총 3번이 중첩된 최악의 코드 입니다. 퇴근하고 23시에 풀면 그럴수 있다고? 생각되네요 앜ㅋㅋㅋㅋㅋ 과거에 제가 어떻게 풀었는지 바..

안녕하세요. Ruk 입니다. LeetCode의 Longest Substring Without Repeating Characters 문제에 대하여 어떻게 접근하였고 풀어보았는지 풀이과정을 공유해보려 해요. 주어진 문자열을 입력받았을 때 해당 문자열에서 중복없이 가장 긴 문자열을 찾는 문제로 보이내요. 알고리즘에서 아래와 같은 조건을 걸어 보았습니다. 1. Set 인터페이스를 활용하여 중복을 체크하자. 2. 중복이 발견되면 길이를 저장 ( length비교 해야겠죠? ) 3. 중복이 사라질 때 까지 Set에서 문자열 제거 위 조건을 구현한 코드입니다. 하지만 속도와 메모리가 너무나도 아쉽습니다. b(n^2)의 복잡도를 가지게 되는데 while문을 사용하지 않고 최대길이를 구할 방법을 더 궁리해봐야 겠내요. 뭔..

안녕하세요 Ruk 입니다. 오늘은 LeetCode의 Add Two Numbers 문제를 풀어본 내용을 공유하려 해요. 2개의 ListNode가 주어졌을 때 10진법의 숫자 합산 연산을 하여 ListNode를 다시 반환하는 문제내요. 예시를 보면 각 노드의 첫번째 자리는 1의 자리로 정의가 되어있습니다. 해결 방법으로는 아래와 같이 정리하습니다. ( 개인적으로 알고리즘을 풀 때 해당 문제에서 처리해야할 요건을 정리 후 풀이에 들어가는게 코드 짜기에 전 더 편하더라고요. ) 1. 각 노드가 null인지 확인 후 합산한다. 2. 2개의 노드중 하나라도 next노드가 존재하면 반복한다. 3. 10이 넘어가면 carry를 체크한다. 4. 2개의 노드가 null이더라도 carry가 존재하면 자리수 1을 올려준다. ..