리트코드 문제 정리

리트코드에서 해결한 문제 정리

문제 / 풀이

*의 경우 개선해야 함

#	문제	정답	정리
1	Two Sum	Java (Easy) Java (Hard)	- 완전탐색의 경우 O(n^2) - 해쉬 맵 을 활용하여 숫자를 찾는 방식으로 O(n)에 구현 가능
2	Add Two Numbers	Java	- 링크드 리스트를 한 노드 씩 탐색하며 더하기
3	Longest Substring Without Repeating Characters	Java	- 투 포인터 알고리즘
8	String to Integer (atoi)	Java	- 주어진 알고리즘을 그대로 구현 - int자료형의 오버플로우를 고려하여 스트링 상태에서 숫자의 크기를 비교
9	Palindrome Number	Java	- 스트링으로 변환 후 뒤집에서 비교
10	Regular Expression Matching	Java	- dfs/백트래킹 활용
11	Container With Most Water	Java	- 투 포인터 알고리즘 - 양 끝에서 더 낮은 벽을 줄여오는 방식으로 탐색
12	Integer to Roman	Java*	- 규칙 & 재귀함수를 활용
13	Roman to Integer	Java	- 심볼 가치가 큰 순서대로 비교하며 반복
14	Longest Common Prefix	Java	- 각 스트링에 글자들을 비교하여 구함
15	3Sum	Java	- 정렬 후 첫 숫자를 정한 뒤 투 포인터 알고리즘. - O(n^2)
16	3Sum Closest	Java	- 15번과 동일
17	Letter Combinations of a Phone Number	Java	- dfs를 활용하여 완전탐색 - O(4^n)
18	4Sum	Java	- 정렬 후 두 숫자를 투 포인터 알고리즘을 사용 - 해쉬맵을 활용하여 중복 체크
19	Remove Nth Node From End of List	Java	- 링크드 리스트의 길이 계산 후
20	Valid Parentheses	Java	- 스택을 활용하여 유효성 체크
21	Merge Two Sorted Lists	Java	- 새 링크드 리스트 생성 후 두 리스트의 해드를 비교하며 붙임
22	Generate Parentheses	Java	- dfs/백트래킹 활용
23	Merge k Sorted Lists	Java	- 21과 원리 비슷 리스트들 중 가장 작은 수를 붙임
24	Swap Nodes in Pairs	Java	- 링크드 리스트를 따라가며 2 노드씩 바꿈
25	Reverse Nodes in k-Group	Java	- 3개의 포인터를 유지하며 링크드 리스트를 뒤집는다
26	Remove Duplicates from Sorted Array	Java	- 공간복잡도를 O(1)로 하기 위해 배열을 탐색하던 도중 중복이 발생하면 한칸 씩 앞으로 옮김
27	Remove Element	Java	- 공간복잡도를 O(1)로 하기 위해 배열을 탐색하며 일치하면 한칸 씩 앞으로 옮김
28	Implement strStr()	Java	- substring을 구하여 비교
30	Substring with Concatenation of All Words	Java	- 해쉬 맵을 활용하여 각 word의 개수를 미리 저장한 뒤, 스트링을 탐색하며 매치를 찾는다
31	Next Permutation	Java	- 공간복잡도를 O(1)로 하기 위해 순열의 성질을 활용
32	Longest Valid Parentheses	Java	- 스택을 활용하여 최대길이를 구한다 - 시간 복잡도 : O(n)
33	Search in Rotated Sorted Array	Java	- 이진탐색의 원리를 활용하여 정렬된 배열의 상태에 따라 경우의 수를 나누어구한다
34	Find First and Last Position of Element in Sorted Array	Java	- 시간복잡도를 O(log(n))으로 만들기 위해 이진탐색을 두번 진행하여 target의 앞과 뒤를 찾음
35	Search Insert Position	Java	- 이진탐색 활용
36	Valid Sudoku	Java	- 주어진 룰대로 반복하며 행, 열, sub-box를 확인
37	Sudoku Solver	Java	- dfs/백트래킹을 활용 - 현재 위치에서 가능한 숫자들을 계산하고 탐색
38	Count and Say	Java	- 재귀 방식으로 해결
39	Combination Sum	Java	- dfs/백트래킹을 활용
40	Combination Sum II	Java	- dfs/백트래킹을 활용 - 중복 제거를 위해 Set 사용
43	Multiply Strings	Java	- 한 글자씩 정수로 변환하여 계산하는 곱셈, 덧셈 함수 구현
45	Jump Game II	Java	- dp 활용 - O(n * m)
48	Rotate Image	Java	- (i, j) -> (j, (n - 1) - i)
49	Group Anagrams	Java	- 단어의 구성 알파벳을 키로 활용 - 해싱하여 분리

프로그래머스 문제 정리

프로그래머스에서 해결한 문제 정리

문제 / 풀이

*의 경우 개선해야 함

문제	정답	정리	레벨
양궁대회	Kotlin	- dfs 완전 탐색	lv2
멀쩡한 사각형	Java	- gcd를 활용한 수학 문제	lv2
124 나라의 숫자	Java	- 3진법을 계산하듯 계산하며 3으로 나누어 떨어지는 경우 1을 빼준다	lv2
[1차] 뉴스 클러스터링	Java	- 두 스트링에 대한 map을 생성하여 각 원소의 개수를 계산한 뒤 합집합, 교집합의 크기를 구한다	lv2
양과 늑대	Kotlin	- dfs로 탐색, 지금까지 방문한 노드가 현재 상태	lv3
파괴되지 않은 건물	Kotlin	- 누적 합 배열 활용	lv3
[1차] 셔틀버스	Java	- 콘의 출근 시간을 분 단위별로 가능 여부를 모두 계산해 본다	lv3
자물쇠와 열쇠	Java	- 가능한 모든 열쇠 - 키 조합에 대해 확인한다.	lv3
[1차] 추석 트래픽	Java*	- 스트링을 처리 시작시간, 종료 시간으로 파싱 후 가능한 조합을 모두 비교한다.	lv3

백준 문제 정리

백준에서 해결한 문제 정리

문제 / 풀이

문제	정답	정리
13168	Java	- 이진 탐색, 해싱
11066	Java	- 다이나믹 프로그래밍 - O(n^3), dp[i][j] = min{ dp[i][k] + dp[k][j] }

코드 포스 문제 정리

코포 문제 정리

문제 / 풀이

문제	정답	정리
1690B	Java	- 단순 구현 문제