[LeetCode] 400. Nth Digit(Java, 순서 찾기, N번째 숫자 찾기, 코딩테스트)
## 접근방법 이 문제는, 1부터 2^31 - 1까지 나열했을 때, N번째 숫자를 찾는 것이다. 10번째 숫자는, 10에서 1을 의미한다. 이제 규칙을 찾아서, N번째 숫자를 찾아야 한다. N의 범위가 2^31 - 1이므로, 모든 숫자를 확인하면서 자리수를 확인하면 시간초과가 발생할 것이다. 자리수의 규칙을 찾아보자. 1 ~ 9는 한 자리수, 9개 10 ~ 99는 두 자리수, 90 * 2개 100 ~ 999는 세 자리수, 900 * 3개 위와 같은 규칙이 성립한다. 위의 규칙을 이용하면 N이 적어도 몇 자리수인지 파악이 가능하다. 개수를 누적합하면서, 구간을 찾으면 몇자리수인지 확인할 수 있다. 위의 그림을 보면서 규칙을 파악해보자. 현재 두 자리수는 10번째부터 시작한다. 몇번째부터 시작하는지는 N -..
[LeetCode] 60. Permutation Sequence(Java, Hard)
## 접근방법 순열 문제는 자주 나온다. 보통은 그 다음 순열을 물어보는데, 이 문제는 전체 순열에서 순서를 물어보고 있다는 차이점이 있다. 순열을 생각해보면, 1234에서 가장 앞자리가 2가 되려면 3!만큼의 순서가 지나야 될 수 있다. 즉, 어떤 순서를 구할 때, 바로 다음을 구하는 것보다 팩토리얼을 이용해서, 순서를 차감해가는 방식을 사용할 것이다. 그림과 함께 이해를 해보도록 하자. n은 6이고 k는 77이라고 가정해보자, 어떤 수를 넣어도 원리는 동일하다. 첫번째 그림은 초기 상태인 123456을 의미한다. 두번째 그림은, 77 - 5! >= 1이다. 따라서, 1에서 가장 가깝게 큰 2로 변경해준다. 세번째 그림은, 17 - 3! >= 1이므로, 3에서 가장 가깝게 큰 4로 변경해준다. 네번째 ..
[프로그래머스] 섬 연결하기(Java, Greedy, Lv3)
programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr ## 접근방법 섬을 최소의 비용으로 연결해야 한다. 이 문제를 보자마자 최소 신장트리의 개념이 떠올랐다. 가장 거리가 짧은 것들 부터 추가하면, 최소의 비용으로 모든 섬들을 연결할 수 있다. 그리디에서 자주 출제되는 유형은, 가장 거리가 짧은 것부터 찾아서 전역적 최적해를 찾는 방식이 자주 나오는 거 같다. 본론으로 돌아가서, 크루스칼 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다. 처음에 시행착오를 소개하자면, 다리 비용을 기준으로 오름차순으로 정렬을 마쳤지만, 섬을 방..
