Coding Test (34) 썸네일형 리스트형 [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 2 3 4 5 다음