LeetCode #400 NthDigit. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
처음엔 스탠다드로 처리과정도 먼저 쫙 쓰고 함수도 쪼개면서 에프엠으로 했는데 시간이 늦어지면서 뱀꼬리.. 퍼포먼스도 이틀 연속 최하치~
Worst performance ever~~
LeetCode #400
Q.
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 2^31).
무한대로 연속된 정수에서 n 번째 숫자를 찾아라
Note:
n 은 양수이고, 32bit 정수 범위 안에 있다. (n < 2^31)
e.g.
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
설명 : 11번째 숫자는 0 이다, 10에서 뒷부분의 0 ( 숫자 하나하나가 한 숫자 )
Process
// Process (main func)
//1. Input
//2. FindDigitLength
//3. FindDigit
//4. Return digit
// FindDigitLength
//1. Input integer n
//2. Iterate if digitSum is smaller than n
// 2.1.1. Add 9*i * 10^(i-1) to digitSum
// 2.1.2. Count digitCount
//3. Get overNumber
//4. Return digitSum and overNumber
// FindDigit
//1. Input digitCount and overNumber
//2. Get quotient and remainder using overNumber and digitCount
//3. Get Digit
//4. Return Digit
// 처리과정 (실제 함수)
//1. 정수 n을 입력받는다.
//2. n이 몇자리 수 숫자에 포함되는지 찾는다. (자릿수 길이 찾기)
//3. 해당 자리수 숫자에서 수를 찾는다. (수 찾기)
//4. 찾은 수를 반환한다.
// 자릿수 길이 찾기
//1. 정수 n을 입력받는다.
//2. 자릿수합이 n 보다 클때까지 반복한다. (i는 1부터)
// 2.1.1. n보다 작으면 자릿수합에 9*i * 10^(i-1) 을 더한다.
// 2.1.2. 자릿수카운트 센다.
//3. 이전 자릿수합보다 n 이 얼마나 더 큰지 구해둔다. (해당 자리수에서 오버된 수)
//3. 자릿수카운트, 오버된 수를 반환한다.
// 수 찾기
//1. 자릿수와 오버된 수를 입력받는다.
//2. 오버된 수를 자릿수로 나눈 몫과 나머지를 구한다.
//3. 몫만큼 자릿수에서 +=1 씩 진행한다.
//4. 나머지만큼 해당 자릿수에서 이동해서 수를 구한다.
//5. 구한 수를 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
class Solution {
private:
void findDigitLength(int n, int *digitLength, int *overLength) {
double lengthSum = 0;
bool isDone = false;
double nextDigitSum;
while (!isDone)
{
nextDigitSum = (9 * *digitLength) * pow(10, *digitLength - 1);
if (lengthSum + nextDigitSum < n)
{
++*digitLength;
}
else
{
*overLength = n - lengthSum;
isDone = true;
}
lengthSum += nextDigitSum;
}
}
int findDigit(int *digitLength, int *overLength) {
int digit;
if (*digitLength == 1)
return *overLength;
int remainder = *overLength % *digitLength;
int quotient = *overLength / *digitLength;
int number = pow(10, *digitLength - 1);
for (int i = 0; i < quotient; ++i)
{
++number;
}
int length;
if (remainder != 0)
{
length = *digitLength - remainder;
}
else
{
length = 0;
--number;
}
cout << number << " " << length << endl;
for (int i = 0; i < length; ++i)
{
number /= 10;
}
digit = number % 10;
return digit;
}
public:
int findNthDigit(int n) {
int digitLength = 1;
int overLength = 0;
findDigitLength(n, &digitLength, &overLength);
int digit = findDigit(&digitLength, &overLength);
//cout << n << " " << digitLength << " " << overLength << endl;
//cout << "answer : " << digit << endl;
return digit;
}
};
int main(int args, char* argv[]) {
Solution sln;
sln.findNthDigit(15);
}
Something else you might like...?
2019/02/03 - [Algorithm/Leet Code] - LeetCode #393 UTF-8 Validation. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/01 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/31 - [Algorithm/Leet Code] - LeetCode #593 ValidSquare. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법