1396. Design Underground System
checkin, checkout을 통해 두 도시간의 평균 시간을 구하는 문제 그냥 간단하다. checkin 할 때는 map으로 id가 들어온 시각을 저장한 후 checkout 할때 해당 구간에 대해 걸린 시간과 카운트를 누적해서 더해주면 평균을 쉽게 구할 수 있다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
214 213 535. Encode and Decode TinyURL
tinyurl 같은 것을 구현하는 문제. ... medium 치고 너무 쉬운데... 그냥 daily 라서 풀어보았다. 단순히 입력받는 것을 리턴해도 통과가 된다... 하지만 아무 의미가 없으니 간단하게 짜보자. 간단하게 하는 방법으로 id 카운터 값을 놓고 1씩 증가하면서 shorturl을 생성할 수 있다. map으로 관리해주면 매우 간단하게 가능하다.
212 1735. Count Ways to Make Array With Product
n, k 가 입력으로 주어질 때 n개의 수의 곱으로 k를 만들 수 있는 방법의 수를 구하는 문제. 처음에 단순 DP로 하니 시간 초과가 난다... O(NKD) (F: 약수 개수) dicussion을 보니 Stars and bars 개념을 이용해서 풀 수 있다. Stars and bars를 간단하게 설명하면 별을 바로 나눌 수 있는 경우의 수를 구하는 문제이…
211 173. Binary Search Tree Iterator
BST에서 크기 순으로 동작하는 이터레이터를 만드는 문제. 메소드는 next(), hasNext() 두개를 구현하면 된다. 초기화 때 inorder으로 전부 돌아서 배열에 넣은 다음 하나씩 출력하는 방법이 간단하지만 메모리는 O(n)이긴 하다. 스택을 쓰면 O(h)로 메모리를 줄일 수 있다. 하지만 결과에서의 실행 시간은 배열에 전부 집어넣은 방식이 더 빠…
210 230. Kth Smallest Element in a BST
BST가 주어질 때 K번째 작은 원소를 구하는 문제 BST를 탐색하면서 K번째 작은 원소가 나오면 리턴하면 된다. BST 탐색 방법 중 inorder 탐색을 하면(왼쪽 서브트리, 자신, 오른쪽 서브트리) 크기 순으로 탐색할 수 있고 이를 배열에 넣은 다음에 배열에서 k-1 인덱스의 원소를 뽑아내면 된다. 중간에 k번 탐색을 했다면 바로 리턴하는 식으로 가지…
209 857. Minimum Cost to Hire K Workers
노동자의 품질과 최소 임금이 주어질 때 K 명의 노동자를 뽑아야 한다. K명의 노동자가 받는 임금과 품질의 비율은 모두 같아야 한다. 이때 K 명을 뽑을 수 있는 최소 임금을 구하는 문제. 처음부터 드는 생각은 가성비가 좋은 노동자를 뽑아보는 것이다. 즉, wage / quality 를 한 값이 작은 순서로 K명을 뽑아주면 가성비가 좋은 K 명을 뽑을 수 …
208 403. Frog Jump
처음엔 1칸을 뛸 수 있고 k칸 뛴 다음엔 k-1, k, k+1 칸을 뛸 수 있을 때 끝까지 점프할 수 있는지 확인하는 문제. 그냥 DP. N 크기도 작아서 대충 돌려주면 된다. 하드 중에서 아주 쉬운 문제. DP[i, k]: i 인덱스에서 k칸 뛸 때의 가능 여부 위처럼 점화식 세우고 k-1,k,k+1 에 대해 돌려주면 된다. 위치가 아니라 인덱스로 저장…
207 600. Non-negative Integers without Consecutive Ones
n 이하의 수 중에서 2진법으로 했을 때 1이 연속으로 나오지 않는 수의 개수를 구하는 문제. DP로 풀 수 있다. 특정 자리 수에서 1이 연속으로 나오지 않는 수의 개수는 DP로 구하고 n보다 작은지 판단은 1이 나왔을 때 0으로 시작하는 나머지 수들을 더해주면 된다. 아래 디스커션이 이해하기 좋다.
206 991. Broken Calculator
startValue 와 target이 주어질 때 startValue를 target으로 만드는 최소 연산 횟수를 구하는 문제. 연산은 2를 곱하는 것과 1을 빼는 것이 있다. 문제를 그대로 풀면 꽤 tricky 한데 반대로 생각해보면 쉽게 풀린다. 즉, target을 startValue로 만드는 최소 횟수를 구하면 된다. 대신 연산은 2을 나누는 것과 1을 …
205 1663. Smallest String With A Given Numeric Value
1: a, 2: b... 26: z 라고 할 때 k를 나타낼 수 있는 n 길이의 사전순으로 가장 작은 문자열을 출력하는 문제. 문자열의 값은 각 자리의 알파벳 수를 더하는 것이다. 딱 보니 큰 알파벳을 뒤부터 채워나가면 된다. z부터 넣다가 안되면 일반 알파벳, 나머지는 a로 채우면 사전순으로 가장 작게 만들 수 있다. 즉 그리디.