본문 바로가기

Problem solving70

[LeetCode] 7. Reverse Integer (C++) 문제 정수x가 주어졌을 때 정수를 역으로 출력 생각할 것 Int 범위를 잘 고려해야 한다! 계산 중간 과정에서도 항상 long long형이 되도록 생각해야 한다. res += (long long)digits.top() * place; 위 코드에서 long long을 붙이지 않으면 결괏값이 int형이 되어 범위를 초과할 수 있음 코드 class Solution { public: int reverse(int x) { int sign = 1; if(x 0){ digits.push(x%10); x/=10; } long long res = 0; int place = 1; while(!digits.empty()){ **r.. 2023. 6. 23.
[LeetCode] 5. Longest Palindromic Substring (C++) 문제 문자열 s가 주어졌을 때, 가장 긴 palindromic substring찾기 생각할 것 💡 Palindrome 회문, 거꾸로 읽어도 동일한 문자열 모든 경우의 수를 브루트포스 방식으로 확인하면 시간복잡도가 O(n^3)이다. 처음에는 현재 문자열을 앞으로 넣고, 뒤로 넣어서 비교해야하나?라고 생각했다. 하지만 이렇게하면 모든 경우 비교가 불가능하다… 결국, 최적의 코드를 위해서는 DP를 사용해야 한다. 가장 먼저 기본 조건을 설정한다. 길이가 1인 문자열은 모두 팰린드롬. 길이가 2인 문자열은 두개가 같은 문자인 경우 팰린드롬 그리고 팰린드롬 양쪽에 같은 문자가 추가되면 그 역시도 팰린드롬이라는 점을 이용하기! 시간복잡도는 O(N^2)가 된다. 예제1. babad 예제2. cbbd 예제3. cbbc.. 2023. 6. 23.
[LeetCode] 4. Median of Two Sorted Arrays (C++) 문제 두개의 정렬된 배열이 주어졌을 때, 두 배열의 중앙값을 리턴하기 이때, 시간복잡도가 O(log m+n)이 되도록 해야한다. 짝수일 경우에는 가운데 두개의 값의 평균을 출력해야 한다. 생각할 것 두개의 배열이 정렬되어 있으므로 한개씩 비교해보자. 그리고 시간복잡도에 log가 들어가 있으므로 절반만큼만 탐색할 것이다! 결과 코드 class Solution { public: double findMedianSortedArrays(vector& nums1, vector& nums2) { double prev; double res; int idx1 = 0; int idx2 = 0; for(int i=0; i 2023. 6. 22.
[LeetCode] 3. Longest Substring Without Repeating Characters (C++) 문제 문자열 s 중에서 반복되지 않는 가장 긴 문자열 개수 찾기 생각할 것 먼저 문제의 조건을 이해해보자. 예제 1. 주어진 문자열이 abcabcbb라고 했을 때 길이가 1일 때를 제외하고 ab, bc, ca, bca, cab, bc, cb와 같은 문자열이 반복되지 않는 문자열에 해당한다. abca가 불가능한 이유는 abc 이후에 다시 a가 오면 다시 반복이 시작되기 때문이다. 예제 2. bbbbb일 경우 당연히 b가 답이다. b다음 다시 b가 오면 b가 두번 반복 되기 때문이다. 예제 3. pwwkew이면 길이가 1일 때를 제외하고 pw, wk, wke, ke, ew같은 문자열이 가능하다. 따라서 가장 긴 문자열은 3이다. 이를 해결하기 위해서는 해시맵과 투포인터를 사용할 수 있다. 💡 two poin.. 2023. 6. 20.

티스토리툴바