알고리즘(Python)/LeetCode(2)
-
[Leetcode] 75. Sort Colors
0,1,2로 된 배열을 작은 순으로 정렬을 하는데 라이브러리를 사용하지 않고 해결하는 것이다. 물론 라이브러리를 사용해도 문제 해결은 가능하지만 이는 정렬에 대한 내용을 이해하고 있는지 점검하기 위한 것이 목표인 문제인 것 같다. 일반적으로는 스왑을 하는 sort알고리즘으로 풀면되고 nlogn의 복잡도를 가지는 알고리즘을 사용해도 좋다. 하지만 nlogn의 복잡도를 가지는 알고리즘은 구현하기에 너무 까다롭고 일반적인 알고리즘은 O(n^2)이라서 효율이 좋지 않다. 이번에는 O(n)의 복잡도로 풀어보라는 미션을 주셔서 O(n)이 되도록 풀어보았다. class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything..
2022.05.06 -
[LeetCode] 1209. Remove All Adjacent Duplicates in String II
코드없는 프로그래밍 채널의 해설을 참고해서 풀었고, 같은 문자가 k번 반복될 때마다 k번 pop을 해주는 방식으로 풀었다. 1. 문자열을 저장할 스택과 얼마나 반복됐는지 체크할 숫자스택을 만든다. 2. 문자열 스택의 마지막을 제시된 문자열과 비교해 같은지 파악한다. 3. 같으면 추가하고 숫자스택의 값도 1올려준다. => 숫자스택의 값을 체크해 k와 같으면 k만큼 pop을 해준다. 4. 같지 않으면 문자스택에 추가하고, 숫자스택에 1을 추가한다. 처음에 문제를 읽고 처음 문자열 스택에서 pop을 하고 나면 변형된 스택에서 새로 겹치게 되는 것을 찾지 못하는 것이 아닌가 생각해 보니 새로 비교하는 문자를 이어서 숫자 스택에 더해주기 때문에 찾을 수 있다는 것을 알게 되었다. st = [] nt = [] fo..
2022.05.02