Coding Test/String (5) 썸네일형 리스트형 [Leetcode] 647번 - palindromic substring 문제 링크: https://leetcode.com/problems/palindromic-substrings/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 좌우 대칭되는 개수 구하기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring을 카운트 하기시간잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상 2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring중에서 좌우 대칭되는 것을 카운팅해야되기 때문에, 모든 문자를 중앙값으로 두고 좌.. [Leetcode] 49번 - 그룹 애나그램(Anagrams) 문제 링크: https://leetcode.com/problems/group-anagrams/description/ 1. 문제 파악 애나그램(Anagram): 동일한 문자의 조합으로 이루어진 문자열이면 동일한 값으로 치부문제를 나눠서 정의: 주어진 문자열 배열에서 애나그램인 문자열 끼리 리스트로 묶어서 반환해라.문자열끼리 애나그램 판별애나그램인 문자열끼리 리스트에 추가시간복잡도 파악:1 -> 문자열 배열의 길이: 10000 -> O(nlogn)0 -> 문자열의 길이: 100 -> O(n)시간 복잡도 총합: O(n x nlogn) 2. 핵심 문제 풀이 도출 문제를 나눈것에 대해 풀이를 도출해본다.애나그램 판별은 어떻게 할까? -> 문자열에서 문자의 개수가 동일한지 확인 -> 너무 복잡 -> 정렬을 하면.. [Leetcode] 5번 - 최대길이 palindromic 부분 문자열 문제 링크: https://leetcode.com/problems/longest-palindromic-substring/description/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 대칭되는 것중에서 가장 긴것 찾기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring 중에서 제일 긴 것 찾기시간복잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값 부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring에서 가장 긴 좌우 대칭 문.. [LeetCode] 424번 - 가장 긴 반복 문자 교체 (Java, 슬라이딩 윈도우 풀이) 문제 링크: 424. Longest Repeating Character Replacement문제 풀이1단계: 문제 이해목표: 주어진 문자열 s에서 k번 이하의 문자 변경을 통해, 같은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 구하라.제한: 문자열 길이 최대 10⁵ → 선형 알고리즘이 필요.2단계: 어떤 알고리즘을 써야할까?문자 배열에 저장된 연속된 문자에 대해서 탐색이 필요 -> 탐색 범위를 지정해서 결과값을 도출해야한다. -> 슬라이딩 윈도우 필요왼쪽 포인터를 이동: 조건이 불일치해서 다음 범위를 지정하기 위해서이다.오른쪽 포인터를 이동: 조건이 일치해서 탐색 범위를 확장하기 위해서이다.조건 만족: 최대값 혹은 최소값을 계산하여 결과값을 업데이트한다.3단계: 핵심 아이디어 도출조건을 위반하는 경.. [LeetCode] 3번 – 중복 없는 가장 긴 부분 문자열 (Java, 슬라이딩 윈도우 풀이) 1. 문제 파악해당 문제 유형은 단순히 구현이나 자료구조와 알고리즘을 아는 것보다 동작을 추상화해서 수식 또는 알고리즘으로 모델링하는 것이 핵심이다.문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters문제 정의:주어진 문자열의 substring에서 알파벳이 중복되지 않는 문자열 찾기중복되지 않는 substring 중에서 제일 긴거를 찾기문제의 제약 파악 (입력값 크기, 상수 조건)0 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출중복 문자가 없는 substring을 찾을려면, 중첩 반복문으로 하나의 문자를 지정하고 나머지 문자들을 확인해야한다. 그러면 n + n-1 + n-2 + ... = n(n+1)/2 .. 이전 1 다음