본문 바로가기

Algorithm175

[LeetCode] 846. Hand of Straights (Swift, Python) Hand of Straights - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 먼저 입력으로 주어진 hand를 오름차순으로 정렬한다. 정렬된 hand에서 가장 앞에 있는(가장 작은) 카드를 손에 들고 현재 손에 있는 수에서 groupSize까지의 카드가 현재 배열에 존재하는지 체크한다. 예제에서는 처음에 손에 카드 1을 들고 2와 3이 있는지 체크한다. 2가 있다면 카운트를 하고 hand 배열에서 2를 제거한다. 다음으로 3이 있다면 카운트를 하고 ha.. 2022. 1. 9.
[LeetCode] 1663. Smallest String With A Given Numeric Value (Swift, Python) Smallest String With A Given Numeric Value - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 앞에서부터 차례대로 문자열을 만들어나간다. 사전순으로 가장 앞에 있는 문자열을 구하기 위해서는 앞의 자리에 최대한 a에 가까운 문자로 만들어야한다. 현재 채워야 하는 자리 이후에 가장 큰 z를 채운다고 가정했을 때 k를 만족할 수 있는지를 따져보면 된다. 예제의 n = 5, k = 73을 생각해보자. 현재 채워야하는 첫 번째 자리를.. 2022. 1. 6.
[고득점 Kit(탐욕법)] 단속카메라 (Python) 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 차량의 진입/전출에 따른 범위를 그림으로 그려서 판단하면 쉽게 해결 가능하다. 먼저 입력으로 주어진 routes를 전입을 기준으로 오름차순 정렬을 한다. 그 후 다음과 같이 경우를 나누어 for문을 돌면서 이에 맞게 처리를 해주면 된다. 먼저 처음 차량의 범위에 단속카메라를 설치한다고 가정하고 시작한다. 참고로 카메라의 설치 범위에서 시작 부분은 따로 신경쓰지 않는다. 어차피 정렬을 하고 나면 진입 지점은 항상 뒤일 것이기 때문에 카메라의 설치 범위 역시 그에 맞춰서 좁아진다고 생각하면 된다. (1) 다음 차량의 진입 지점(nowStart)이 이전 차량의 전출.. 2022. 1. 3.
[고득점 Kit(탐욕법)] 섬 연결하기 (Swift, Python) 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 섬을 연결할 때 일단 가장 적은 비용의 다리를 먼저 사용해야 하므로 입력으로 주어진 costs를 비용을 기준으로 오름차순 정렬을 한다. 그 후 차례대로 다리를 사용해가면서 이미 연결된 두 섬에 대한 다리인지를 체크한다. 이미 두 섬이 연결되어 있으면 해당 다리를 사용하지 않고 넘어간다. 다리를 사용할때마다 몇 개의 다리를 사용했는지 체크한다. n개의 섬이 모두 연결되기 위한 최소 다리 개수는 n-1개이기 때문에 다리가 n-1개가 사용됐다면 탐색을 종료한다. 코드 [Swift] import Foundation var edges: [[Int]] = Array.. 2022. 1. 2.
[고득점 Kit(탐욕법)] 구명보트 (Python) 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 people을 정렬한 상태로 만들어준다. 그 후 left와 right를 두어 현재 가장 가벼운 사람과 무거운 사람을 최대한 같이 태울 수 있도록 해주었다. 먼저 보트에 가장 무거운 사람을 태웠을 때 limit보다 작다면 무거운 사람을 태우고 right 인덱스를 -1 해준다. 그 후 가장 가벼운 사람을 태웠을 때 limit보다 작다면 가벼운 사람을 태우고 left 인덱스를 +1 해준다. 이 때 flag를 사용했는데 만약 flag가 .. 2022. 1. 1.
[고득점 Kit(탐욕법)] 큰 수 만들기 (Python) 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 입력으로 주어진 number를 앞에서부터 탐색하면서 answer에 담아준다. 이때 현재 number의 숫자랑 answer에 담겨 있는 숫자를 하나씩 비교하여(역순으로) 현재 숫자가 answer에 담겨 있는 숫자보다 클 경우 answer의 숫자를 한자리씩 지워나간다. 예제의 "4177252841"로 살펴보면 다음과 같다. 처음 숫자인 4를 answer에 담는다. 이제 1과 answer를 한 자리씩 비교하는데 4보다 작으므로 1을 그래도 담는다. answer에는 41이 담겨져 있다. 7과 answer를 역순으로 한 자리씩 비교한다. 7이 1보다 크므로 answer에서 1을 지운다. k는 1 감소 다음으로 7과 4를 비교하는데 7이 더 크.. 2022. 1. 1.

티스토리툴바