IT/Algorithm(29)
-
Leetcode 33. Search in Rotated Sorted Array - Python
Leetcode 33 문제 보기 문제 이해하기 오름차순으로 정렬된 어떤 정수의 리스트 nums가 특정 값을 기준으로 회전되었다. 예를 들어 [1,2,3,4]가 3을 기준으로 회전되면 [3,4,1,2]가 된다. 어떤 정수 target이 주어질 때, 해당 target이 nums안에 존재하는지 판단하고 만약 존재한다면 그 숫자의 nums내 index값을 반환하고, 존재하지 않는다면 -1을 반환하라. 단, 알고리즘은 O(logn)의 시간복잡도를 가져야 한다. 아이디어 구상 단순히 target이 nums에 있는지 알기위해서는 리스트를 순차적으로 탐색하면서 있는지 없는지 판단하면 될 것이다. 그러나 이는 O(n)의 시간복잡도를 가진다. 때문에 O(logn)의 시간복잡도를 가지기 위해서는 결국 Binary Searc..
2022.07.25 -
Leetcode 647. Palindromic Substrings - Python
Leetcode 647 문제 보기 문제 이해하기 영문 알파벳 소문자로 이루어진 문자열 s가 주어진다. 이때 s의 substring 중 팰린드롬인 경우가 얼마나 되는지 구하여라. 아이디어 구상 substring, 즉 부분문자열은 문자열내에서 일부 문자열을 그대로 떼어낸 형태를 말한다. 팰린드롬이란 앞뒤가 똑같은, 뒤집혀도 뒤집히기 전과 형태가 같은 것을 의미한다. 각각의 substring이 팰린드롬인지 확인하기 위해서는 어떤 한 character를 중심으로 양 옆으로 포인터가 퍼지며 두 포인터가 가리키는 character가 같은지 확인하면 된다. 그렇다면 for문을 통해 문자열 s의 첫번째 글자부터 반복을 돌리고, 각 글자에 대해 중심부터 투 포인터가 퍼지며 팰린드롬 여부를 판별하면 되겠다. 여기서 하나 ..
2022.07.21 -
Leetcode 621. Task Scheduler - Python
Leetcode 621 문제 보기 문제 이해하기 CPU가 순차적으로 task를 하나씩 처리한다. Task는 영문 알파벳 대문자로 표시된다. 이때 같은 종류의 task는 연달아 진행할 수 없고, 휴식(idle)이 필요하다. 또한 동일한 종류의 task 사이에는 n만큼의 idle이 필요하다. clock이 일정하게 흐르고 각 task 및 idle은 종류에 상관없이 1clock의 시간을 소모한다. 모든 task를 마무리할 수 있는 가장 빠른 시간을 구하여라. 아이디어 구상 Leetcode Medium 난이도 문제였지만, 개인적으로 웬만한 Hard 난이도보다 어려운 문제였다. 이 문제에서 키 포인트는 다음과 같다. "가장 많이 수행해야하는 task부터 처리하는 것이 유리하다." 이를 위해 최대힙을 사용하여 문제를..
2022.07.18 -
Leetcode 239. Sliding Window Maximum - Python
Leetcode 239 문제 보기 문제 이해하기 정수로 구성된 리스트 nums와 양수 k가 주어진다. k 사이즈의 리스트가 nums 내에서 움직인다. 이때 각 'k 사이즈 리스트(window)' 내 가장 큰 값을 결과 리스트에 담아, 최종적으로 결과 리스트를 출력하라. 아이디어 구상 우선 문제를 보면, Brute Force한 O(n^2)의 알고리즘이 바로 떠오른다. Slicing를 이용하거나 nums를 한바퀴 순회하며 window를 업데이트하고 매순간 window내 max를 찾는 경우가 되겠다. 별도의 시간복잡도에 관한 constraint가 없었기 때문에 혹시나 하는 마음에 Brute Force 풀이를 submit해봤으나, TLE(Time Limit Exceeded)가 떴다. 그렇다면 이를 좀 더 효율적..
2022.07.07 -
Leetcode 42. Trapping Rain Water - Python
Leetcode 42 문제 보기 문제 이해하기 높이에 관한 정보가 주어질 때, 가둘 수 있는 빗물의 부피를 구하라. 예를 들어, height = [0,1,0,2,1,0,1,3,2,1,2,1] 일 때(위 그림 참조), 정답은 6이다. 아이디어 구상 가장 먼저 떠오른 생각은, 가장 높은 지점을 기준으로 좌우를 나누어 계산하면 될 것 같다라는 점이다. 다음처럼 생각해보자. 가장 높은 곳을 기준으로 좌측 영역을 우선 생각해보자. 첫 시작부터 포인터가 이동하면서 max값을 업데이트하며, max와 현재 지점의 높이의 차를 정답에 더해준다. 포인터는 전체에서 가장 높은 곳에 도달하면 멈추게 된다. 이렇게 되면 좌측 영역에서, 우측에는 분명한 '벽'(전체에서 가장 높은 지점)이 존재하므로 영역 내 높이 낮아지는 지점에..
2022.06.27 -
Leetcode 179. Largest Number - Python
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다Leetcode 179 문제 보기 문제 이해하기 주어진 nums 리스트에는 양의 정수들이 있다. 이들을 조합하여 만들 수 있는 가장 큰 수를 구하라. 예를 들어 nums = [3,30,34,5,9] 일 경우, 정답은 "9534330" 이다. 아이디어 구상 주어진 예시에서 알 수 있듯이, 단순히 큰 수를 앞으로 놓는다고 해결되지 않는다. 각각의 digit이 가능한 큰 숫자가 오도록 나열해야 정답을 구할 수 있다. 때문에 nums 안에 있는 각각의 숫자를 String으로 만들고, 두 개의 원소 n1, n2를 순서를 바꿔 결합하여 대소 관계를 비교, 큰 수가 앞서도록 정렬하면 되겠다. 그렇다면 이제 어떻게 이 과정을 코드로 옮..
2022.06.23