코테 19

[리트코드/leetcode/python] 209. Minimum Size Subarray Sum

처음에 그냥 생각나는 로직대로 푼 알고리즘은 다음과 같습니다. nums를 처음부터 더하는데, target보다 같거나 커지면, check 변수를 통해 플래그를 걸어 놓고 여태 더했던 순회 횟수, 즉 길이를 저장합니다. 그리고 다음 인덱스로부터 또 같은 행동을 반복하는데, 최소 길이가 갱신 된다면 최소 길이를 갱신하고 그렇지 않다면 그냥 패스합니다. 풀었던 코드는 아래와 같습니다. 푼 코드는 아래와 같습니다. class Solution(object): def minSubArrayLen(self, target, nums): for i in range(len(nums)): tmp = 0 for j in range(i,len(nums)): tmp += nums[j] if tmp >= target : length ..

[리트코드/leetcode/python] 347. Top K Frequent Elements

이 문제를 처음 봤을 때 계수정렬을 생각해봤습니다. nums[i]의 범위가 -10^4 부터 시작되므로, 음수도 포함될 수 도 있기에, 음수일 때와 양수일 때를 나눠서 계수정렬로 로직을 짰었습니다. 하지만, 계수정렬을 한 리스트가 내림차순되면서, k 번째까지 리스트를 슬라이싱 하는데에, 원소 순서가 변하기에 한계가 있었습니다. 어떤 수가 몇 번 나왔는지를 체크해야 하므로, 계수정렬보다는 딕셔너리 등을 사용하는 것이 더 적합했습니다. follow up을 보면, O(n log n)의 시간복잡도를 구현해보라고 하는데, 딕셔너리로 풀 때, O(n)으로 풀리는 것이 아닌가 하는 의구심으로 문제를 풀기 시작했습니다. 푼 코드는 아래와 같습니다. class Solution(object): def topKFrequent..

[프로그래머스] 코딩테스트 연습 - 124 나라의 숫자(Python)

문제 설명 더보기 문제 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한 n은 50,000,000이하의 자연수 입니다. 입출력 예시 입출력 예 n result 1 1 2 2 3 4 4 11 https:/..

[프로그래머스] 코딩테스트 연습 - 선입 선출 스케줄링(Python)

문제 설명 더보기 문제 처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다. 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다. 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다. 처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요. 제한 코어의 수는 10,000 이하 2이상 입니다. 코어당 작업을 처리하는 시간은 10,000이하 입니다. 처리해야 하는 일의 개수는 50,00..

[백준/알고리즘/python/java] 14499번 - 주사위 굴리기

이 문제는 삼성sw 역량 테스트 기출 문제에 속하는데요. 삼성 코테 유형은 대체로 구현이 많이 나옵니다. 차근차근 문제를 이해하고 종이에 써가면서 풀어본다면, 끈기와 빨리 풀 수 있는 실력만 있다면 충분히 푸실 수 있는 문제입니다. 겉으로 봤을 땐, DFS나 BFS로 푸는 문제인 것 같지만, 단순 구현으로도 풀리는 문제입니다. 먼저 문제를 이해해보록할게요. 보드가 있구요. 보드 위에 주사위가 있습니다. 주사위는 보드 위 숫자가 0인 부분에 있고 명령에 따라서 굴리는 문제라고 보시면 됩니다. 그럼, 아래 문제의 내용이 이해가시나요? 주사위가 보드 위에서 굴려질 때마다 주사위 면에 적혀지는 숫자와 보드위에 적혀지는 숫자가 달라진다는 것을 알 수 있습니다. 즉, 주사위가 굴려짐에 따라 보드와 주사위의 숫자가 ..

반응형