LeetCode

sorted 함수 사용

관련 시간복잡도list 에서의 item in list : O(n)list 의 remove(item) : O(n)관련 시간복잡도sort() : O(nlogN)list 의 pop() : O(1)

관련 시간복잡도dict 의 get() : O(1)미리 배열을 할당해놓고 시작하기 때문에 첫 번째 풀이보다 공간복잡도가 떨어진다

비트 연산 하는 방법에 대해 알게되었다& : 비트 연산자 (bitwise)6 & 1 : 110 & 001 = 06 >>= 1 : 1111 & 001 = 1

영어 울렁증과 알고리즘 울렁증을 동시에 얻을 수 있는 리트코드. 심신의 안정을 위해 비기너를 위한 문제를 풀어보았다. 해당 문제는 본문을 읽지 않아도 해석이 가능한 아주 쉬운 문제로 제목과 Example만 봐도 알 수 있다. 누적합(prefix sum) 배열을 만드는

가장 부자인 고객의 재산을 알아보는 문제다.고객과 고객의 재산이 m X n 배열로 주어진다. 각 고객의 재산 총합을 구한 뒤 가장 부유한 고객의 재산을 반환하면 된다.함수의 시간복잡도max() : O(1) ( 배열의 경우 O(n) )sum() : O(n)포문을 돌면서

주식을 사고 팔면서 얻을 수 있는 최대 이익을 구하는 문제.다음 날의 주식 가격을 비교해서 차액을 계산해 합산하면 된다. 단순하게 차례대로 비교하는 방법이므로 O(n)이다. (O(n-1))

k번 만큼 회전 시키는 문제.새로운 배열을 만들어서 밀려서 앞으로 돌아오는 수들을 먼저 넣어준다.뒤로 들어올 수들을 넣어준다.O(k)O(n-k)단계 별 시간 복잡도가 위와 같으므로 총 시간 복잡도는 O(n)이다.최소 3가지의 다른 방법이 있다고 하던데...

0의 위치들을 저장한다.저장된 위치들을 통해 상하좌우를 0으로 만든다.O(m\*n)O(0의개수\*(m+n))이므로 총 시간 복잡도는 O(mn) 이다.지금 내 코드는 bad idea구나... 더 빠른 방법은 어떻게 해야할까

애너그램(Anagram): 일반적으로 모든 원래 문자를 한 번만 사용하여 다른 단어 또는 구의 문자를 재배열하여 형성된 단어 또는 구이다.이 애너그램의 집합을 구하는 문제.strs 배열의 한 문자를 정렬한다.정렬한 뒤 정렬한 문자를 key 값으로, 원래 문자를 valu

중복된 문자가 있으면 true를 출력하기.Set과 Dictionary로 풀면 O(n)이 나온다.Dictionary 풀이Set 풀이 둘 다 O(n). 공간 복잡도는 Set보다 딕셔너리가 10MB가 더 많이 나왔다.

모든 수는 두 번씩 나타난다, 한 개만 빼고.그 하나의 수를 찾아라.숫자를 차레대로 set에 저장한다. 만약 이미 set에 있다면 저장 대신 삭제한다.최대 등장 횟수가 두 번이므로 가능한 풀이다.모든 배열을 검사하므로 O(n)이다.

새로운 링크리스트를 만들어서 합계 중 일의 자리만 저장하고 올림수를 따로 저장한다.C언어를 풀던 습관이 남아서위의 코드도이렇게 작성하고... 파이썬 문법이 너무 눈에 안 익는다. 그렇다고 이제는 씨언어도 모르겠고... 모든 걸 다 잃어버린 느낌. 🥵링크 리스트를 돌아

Inorder Traversal (중위 순회) : L - ROOT - R재귀 함수를 사용해서 풀었다.왼쪽 노드를 방문한다.배열에 현재 노드의 값을 저장한다.오른쪽 노드를 방문한다.결국은 모든 노드를 방문하므로 O(n)가 된다.

Level Order Traversal (레벨 순회) : 각 깊이 별로 탐색하는 알고리즘deque를 사용해 해결했다.1\. 큐의 길이를 저장해(size) 레벨이 바뀐 것을 구별한다.2\. 지그재그로 저장하기 위해서레벨이 바뀔 때마다 left를 바꿔준다.3\. 순서 큐에

투포인터를 사용해 해결했다.간단하다. 앞과 뒤를 서로 체인지해주면 된다.

가장 먼저 등장하는 유일한 문자의 인덱스를 찾는 문제다.dictionary를 사용해 해결했다.1\. 딕셔너리에 각 문자의 개수를 저장한다.2\. 다시 반복문을 돌면서 문자의 개수가 1개인, 유일한 문자에 도착하면 해당 인덱스를 반환한다.dictionary의 삽입, 탐색

짝수 번째 노드들을 뒤로 보내야한다.홀수 번째와 짝수 번째 head와 tail을 사용한다.짝수 번째 노드와 그 다음 노드(홀수 번째)가 존재하지 않을 때까지 while문을 돌린다.2.1. 홀수 번째 노드를 다음 홀수 번째 노드와 연결한다.2.2. 짝수 번째 노드를 다음

배열 안의 숫자는 이동할 수 있는 거리를 뜻한다. 칸을 이동하면서 마지막 인덱스에 위치할 수 있는지를 검사하는 문제다.DP 를 사용해서 풀었다.배열을 돌면서 최대 이동 거리를 이동하면서 마지막 인덱스 위치에 도달할 수 있는지를 판별한다.1\. 0번째 숫자를 초기 점프

3개의 수의 합이 0이 되는 부분 집합을 찾는 문제다.투 포인터 를 사용했다. (left, right)1\. 우선 배열을 정렬한다. 3개 수의 합이 0이 되려면 0, 0, 0 인 경우를 제외하고는 최소 하나의 수가 음수여야하기 때문에 오름차순으로 배열을 정렬해 투 포인

단순 연결 리스트에서 노드를 삭제하는 함수를 작성하는 문제다.head에 대한 접근 권한 대신에 삭제할 노드에 대한 접근 권한을 가지며 삭제할 노드가 마지막 노드가 아니라는 것이 보장된다.보자마자 엥? 제거면 그냥 node = node.next 하면 되는거 아님? 하면서

뒤에서 n번째 노드를 삭제하는 문제다.투 포인터를 사용해 해결했다.투 포인터는 두 개의 포인터를 사용하여 배열, 연결 리스트 또는 기타 자료 구조에서 문제를 해결하는 데 사용된다. 일반적으로 배열 또는 리스트가 정렬되어 있거나 어떤 특정한 패턴을 갖고 있을 때 유용하다

연결 리스트를 반대로 뒤집는 문제다.투 포인터를 이용해서 해결했다.dummy까지 쓰리 포인터인가?ㅎ temp도 포인터도 쳐주나?first의 다음 노드를 dummy에 임시 저장한다.first의 next에 이전 노드를 저장해 방향을 바꾼다.이전 노드(second)를 한 칸

각 색상의 개수를 저장하는 배열을 만든다.만든 배열을 사용해서 nums의 내용을 바꾼다.이 방법은 색상의 종류가 0, 1, 2로 한정되어있기 때문에 통하는 방법 아닐까? 이게 좋은 코드인가?nums의 길이 만큼 돌면서 색상의 각 개수를 저장하고, 그 저장값을 사용해 n

가장 빈도가 잦은 숫자를 K순위까지 뽑는 문제이다.딕셔너리를 사용해 각 숫자의 개수를 저장한다.딕셔너리를 value 값을 기준으로 내림차순 정렬한다.k번째 값까지 꺼내온다.딕셔너리에 숫자를 저장하는 과정에서 O(n)sorted() 함수를 사용할 때 O(nlogn)k위

중복을 허용하는 교집합을 구하는 문제다.set에 넣어 교집합 연산을 수행한다.교집합 set에 들어간 요소의 개수를 두 배열 중 최솟값으로 추가한다.extend() : 각각의 원소들을 추가한다.append()는 x 그 자체를 원소로 넣고 extend()는 각 항목들을 넣

배열은 하나의 숫자를 의미한다. 해당 수에 1을 더하는 문제다.배열의 수를 하나씩 꺼내 문자열에 저장한다.해당 문자열을 숫자로 바꿔 1을 증가시킨다.배열에 한 자리 씩 다시 담는다.각 요소를 문자열로 변환해서 이어 붙이는 데에 O(n)문자열을 정수로 변환하는데에 O(n

0을 맨 뒤로 이동시키는 문제다.0이 아닌 숫자를 앞으로 이동시키면서 수를 센다.0이 아닌 숫자의 갯수를 시작할 인덱스로 두면 나머지가 된다. 나머지는 0으로 변경한다.리스트의 길이만큼 반복문이 실행되므로 O(n)나머지 배열을 변경하므로 최악의 경우 O(n)전체적으로

연결 리스트의 교차점을 찾는 문제다.교차점을 하나 찾으면 그 뒤의 노드들도 모두 같음이 보장된다.skipA, skipB 같은 수들을 줘서 문제 이해가 더 어려웠다.얘를 사용해야 한다는거야 뭐야 왜 주는거야두 리스트의 순서를 반대로 이어 붙인 두 리스트를 비교하면 길이를

문제 자체는 간단하다. k번째로 큰 수를 찾는 문제다.sort()를 사용하면 바로 해결할 수 있지만, 이 문제에서 바라는 해답은 정렬을 사용하지 않고 해결해보는 것이다.문제에서 정의한 숫자의 범위 만큼 배열을 할당해 배열 안의 숫자의 개수를 저장한다.개수를 저장한 배열

딕셔너리를 사용해 해결했다.배열을 처음부터 끝까지 순회하면서 아래 과정을 거친다.타겟에서 자기 자신을 뺀 수, 합치면 타겟이 되는 수가 딕셔너리에 있는지를 검사한다.1.1. 있다면 해당 수의 인덱스와 자신의 인덱스를 반환하고 종료한다.자기 자신을 key로, 인덱스를 v

글자의 순서를 바꾸면 동일한 단어가 되는지를 검사하는 문제다.sorted() 함수를 사용해 해결했다.보자마자 가장 처음으로 생각난 방법.두 문자열을 정렬한 뒤 같은 문자열이 되었는지를 검사한다.sorted() 함수의 시간 복잡도는 O(2(nlogn))이다.딕셔너리 를

문장이나 단어를 뒤집어도 동일한 것을 펠린드롬이라고 한다.이번 문제는 대소문자 구별이 없고 알파벳과 숫자를 제외한 문자들이 펠린드롬을 충족하는지 검사하는 문제다.lower() 를 사용해 소문자로 변환한다.isalnum() 을 사용해 알파벳 혹은 문자만 남긴다.투 포인터