기억보다 기록을

투포인터를 이용한 문제를 풀어보자. 투포인터를 구현하는 방식에는 여러가지가 있지만, 대개는 시작점과 끝점 또는 왼쪽/오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략을 말한다. 범위를 좁혀가기 위해서는 대체로 배열이 정렬되어 있어야 한다. 투 포인터또한 배열을 순차적으로 접근한다는 점에서 브루트 포스와 비슷한거 아닌가? 라는 생각을 잠깐 했지만, 브루트 포스가 2중 포문으로 타임아웃 땅땅 내려준다면 투포인터는 훨씬 향상된 시간복잡도를 보여준다. 모든 원소에 접근하긴 하지만, On^3 의 브루트포스 결과를 On^2 으로 개선할 수 있는 것이다. 1. Trapping rain water 리트코드의 빗물트래핑 문제로, 파이썬 알고리즘 인터뷰 책을 참고했다. 처음 봤을 때 브루트포스 방식은 쉽게 이해갔지만..

two sum은 많은 사람들이 리트코드를 입문하며 처음 푸는 문제같다. 알고리즘 책에서 이 문제를 다양한 방식으로 풀어보는데, 이 중 내가 알고있으면 좋을 풀이 (==나누면 좋을 지식)을 정리하려 한다. 투포인터 사용에 대한 이야기가 나오는데, 이 문제는 인덱스 값을 리턴하기에 투포인터 자체를 사용하여 풀 수는 없다. (투포인터 관련 문제는 이 포스팅 바로 다음에 이어질 예정이라 만약 투포인터를 사용한 알고리즘 풀이가 궁금하다면 다음 포스팅을 참고해주세요👍) 그래서 1) Brute force로 풀이 2) in 을 사용한 풀이 3) 시간 복잡도를 개선해 속도를 높인 딕셔너리 사용 풀이 4) 3의 코드를 좀 더 간결하게 정리한 풀이 네가지를 공유할까 한다. 문제는 다음과 같다. Given an array o..

출처 https://leetcode.com/problems/number-of-islands/ 문제 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. 입출력 예시 Input: grid = [ ["1","1","1","1","0"], [..

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Constraints: m == grid.length n == grid[i].length 1

source: https://leetcode.com/problems/most-common-word/ Q. Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique. The words in paragraph are case-insensitive and the answer should be returned in lowercase. Idea: 문자열을 공백으로 split 하여 새로운 배..

Q. You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier. There are two types of logs: Letter-logs: All words (except the identifier) consist of lowercase English letters. Digit-logs: All words (except the identifier) consist of digits. Reorder these logs so that: The letter-logs come before all digit-logs. The letter-logs are sorte..

Q. A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. 1. 리턴타입 boolean 2. 회문을 돌면서 모두 체크할 것인지, 정규 표현식을 쓸 것인지 고민할 필요가 있습니다. 만약 회문을 돈다면 .isalnum()(영문자..