타입챌린지 : 2257-MinusOne (medium)

 

이 글은 제가 타입챌린지를 하면서 해석한 내용을 적는 글입니다. 틀린 내용이 있으면 댓글 달아주시면 감사하겠습니다.

 

https://github.com/type-challenges/type-challenges/blob/main/questions/02257-medium-minusone/README.md

GitHub - type-challenges/type-challenges: Collection of TypeScript type challenges with online judge

 

정말... 어렵습니다.

각오하시고 보세요. (이전처럼 자세하게 설명까진 안하겠습니다... 이거 풀 정도면 웬만한 건 다 아신다고 판단하겠습니다...)

 

제네릭 인자로 숫자가 들어오면, 해당 숫자에 -1을 해서 리턴하는 타입이다.

일단, 이 문제를 보고 바로 든 생각이 배열이었다. 배열의 Length를 이용해서 푸는 것이다.

그래서 다음의 코드가 나왔다.

type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type NumberToArrayForMinusOne<T extends number, U extends any[] = []> = U['length'] extends T ?
  U : NumberToArrayForMinusOne<T, Push<U, 0>>

type MinusOne<T extends number> = NumberToArrayForMinusOne<T> extends [infer F, ...infer O] ? O['length'] : never;

NumberToArrayForMinusOne타입은 U라는 배열의 length가 T와 같이질 때 까지, 원소 0을 U에 Push해서 넘긴다음, U라는 배열을 리턴하는 타입이고,

MinusOne은 리턴받은 U에서 원소 하나를 제외한 배열의 length값을 리턴한다. 그러면 -1이 된다.

 

하지만... MinusOne<1101>과 같이 큰 수가 들어가면 재귀가 너무 깊다면서 에러가 뜬다...

 

 

그러다, 풀다보면서 든 생각은 string을 number로 바꾸어서 푸는 것이다.

와... 겨우 풀었다.... 이거 설명도 어려울거 같은데 ㅋㅋㅋㅋ

type MinusOneNums = {
  '1':0, '2':1, '3':2, '4':3, '5':4, '6':5, '7':6, '8':7, '9':8, '0':9
}

type Numbers = {
  '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9, '0':0
}

type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type ArrayToString<T extends any[]> = T extends [infer F, ...infer O] ? 
  F extends string ? 
  `${F}${ArrayToString<O>}` : '' : '';

type ParseInt<T extends string> = T extends `${infer F extends number}${infer O}` ?
  F extends 0 ? 
  O extends `${infer X extends number}` ? X : F :
  T extends `${infer Y extends number}` ? Y : never : never;

type C = ParseInt<'0'>

type ExceptLast<T extends string, V extends any[] = []> = T extends `${infer F}${infer O}` ? 
  ExceptLast<O, Push<V, F>> :
  V extends [...infer O, infer L] ? ArrayToString<O> : never

type B = ExceptLast<''>

type MinusOne<T extends number, V extends string = ExceptLast<`${T}`>> = T extends 0 ? -1 : `${T}` extends `${V}${infer L}` ?
  L extends '0' ? ParseInt<`${MinusOne<ParseInt<V>>}${MinusOneNums[L]}`> : 
  L extends keyof MinusOneNums ? ParseInt<`${V}${MinusOneNums[L]}`> : never : never;


/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<MinusOne<1>, 0>>,
  Expect<Equal<MinusOne<55>, 54>>,
  Expect<Equal<MinusOne<3>, 2>>,
  Expect<Equal<MinusOne<100>, 99>>,
  Expect<Equal<MinusOne<1101>, 1100>>,
  Expect<Equal<MinusOne<0>, -1>>,
  Expect<Equal<MinusOne<9_007_199_254_740_992>, 9_007_199_254_740_991>>,
]

나도 어떻게 푼지 모르겠다... 어떻게 풀었지??

 

일단, 차근차근 살펴보자.

type MinusOneNums = {
  '1':0, '2':1, '3':2, '4':3, '5':4, '6':5, '7':6, '8':7, '9':8, '0':9
}

type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type ArrayToString<T extends any[]> = T extends [infer F, ...infer O] ? 
  F extends string ? 
  `${F}${ArrayToString<O>}` : '' : '';

type ExceptLast<T extends string, V extends any[] = []> T extends `${infer F}${infer O}` ?
	ExceptLast<O, Push<V, F>> :
    V extends [...infer O, infer L] ? ArrayToString<O> : never;

처음으로 내가 만든 타입들이다.

MinusOneNums는 -1을 하기 위해 만든 타입이다.

 

Push타입은 배열 마지막에 원소를 Push하기 위해서 만들었다.

맨 마지막에 [U]를 리턴하는 이유는 빈 배열 상태일 때 원소를 push하기 위함이다.

 

ArrayToString타입은 배열을 문자열로 바꿔주는 타입이다.

T를 받아서 재귀를 이용하여 문자열로 바꿔준다.

 

ExceptLast타입은 문자열에서 마지막 문자만 뺀 나머지 문자열을 리턴하는 타입이다.

재귀를 이용하여 배열 V에 문자를 첫 문자부터 하나씩 넣고, 최후에는 V에서 마지막 원소를 제외하여 문자열로 바꿔서 리턴한다.

 

type MinusOne<T extends number> = `${T}` extends `${ExceptLast<`${T}`>}${infer L}` ?
	L extends '0' ? `${MinusOne<ExceptLast<`${T}`>>}${MinusOneNums[L]}`> :
	L extends keyof MinusOneNums ? `${ExceptLast<`${T}`>}${MinusOneNums[L]}`> : never : never;

일단,다음 코드를 봐보자.`${T}` extends `${ExceptLast<`${T}>}${infer L}` : 문자열 T를 마지막 문자L과 나머지 문자열 ExceptLast로 나누고,L extends '0' ? `${MinusOne<ExceptLast<`${T}`>>}${MinusOneNums[L]}`> : 맨 뒷자리가 0인 경우, -1을 하면 해당 자리의 앞의 자리 숫자도 -1을 해주어야하기 때문에 재귀를 이용해서 문자열을 리턴해준다.

L extends keyof MinusOneNums ? `${ExceptLast<`${T}`>${MinusOneNums[L]}`> : L exteds keyof MinusOneNums를 해야 MinusOneNums[L]을 사용할 수 이써서 해주었다. 만약, 마지막 문자가 0이 아니라면, 마지막 숫자는 -1을 하고(MinusOneNums[L]), 나머지(ExceptLast<`${T}`>는 그대로 리턴한다.

 

여기서 마지막 문자를 제외한 나머지 앞 문자열들을 계속 ExceptLast<`${T}`> 로 계속 표한하기에는 가독성이 떨어져서 다음과 같이 코드를 변경했다.

type MinusOne<T extends number, V extends string = ExceptLast<`${T}`>> = `${T}` extends `${V}${infer L}` ?
	L extends '0' ? `${MinusOne<V>}${MinusOneNums[L]}`> :
	L extends keyof MinusOneNums ? `${V}${MinusOneNums[L]}`> : never : never;

제네릭 V를 ExceptLast<`${T}`>로 설정해주어서 보기 깔끔하게 변경했다.

 

여기서는 문제가 리턴값이 문자열이라는 점이었다. 그래서, ParseInt 타입을 만들어주었다.

type ParseInt<T extends string> = T extends `${infer F extends number}` ? F : never

하지만, ParseInt<'09'> 같이 앞에 0이 들어가면 never를 리턴해버렸다...

 

그래서 ParseInt를 다음과 같이 바꿨다.

type ParseInt<T extends string> = T extends `${infer F}${infer O}` ?
  F extends '0' ? 
  O extends `${infer X extends number}` ? X : never :
  T extends `${infer Y extends number}` ? Y : never : never;

ParseInt<'09'>는 9로 정상 출력이 되었으나... 이 코드도 문제가 있었다. 바로 ParseInt<'0'>을 하면 never가 리턴이 되어버린다는 점이었다.

T가 '0'이면 F가 '0'이지만, O는 빈 문자열이기 때문에 X가 리턴되지 않고 never가 리턴 되어버린 것이다.

 

그래서 이렇게 또 바꿨다... 진짜 찐 최종이다.

type ParseInt<T extends string> = T extends `${infer F extends number}${infer O}` ?
  F extends 0 ? 
  O extends `${infer X extends number}` ? X : F :
  T extends `${infer Y extends number}` ? Y : never : never;

자세한 설명은 생략하겠다!

 

그래서 MinusOne타입을 이렇게 작성할 수 있었다.

type MinusOne<T extends number, V extends string = ExceptLast<`${T}`>> = `${T}` extends `${V}${infer L}` ?
 	 L extends '0' ? ParseInt<`${MinusOne<ParseInt<V>>}${MinusOneNums[L]}`> : 
	 L extends keyof MinusOneNums ? ParseInt<`${V}${MinusOneNums[L]}`> : never : never;

하지만! 테스트 예제에 MinusOne<0> = -1 이 되어야 한다는 조건이 있었으므로! 나또한 조건을 하나 추가했다

 

진짜 찐 최종 MinusOne타입이다.

type MinusOne<T extends number, V extends string = ExceptLast<`${T}`>> = T extends 0 ? -1 : `${T}` extends `${V}${infer L}` ?
  	L extends '0' ? ParseInt<`${MinusOne<ParseInt<V>>}${MinusOneNums[L]}`> : 
  	L extends keyof MinusOneNums ? ParseInt<`${V}${MinusOneNums[L]}`> : never : never;

T extends 0 ? -1 : ~ : T가 0이라면 -1을 리턴한다.

`${T}` extends `${V}${infer L}` ? : T가 0이 아닐 때, 마지막 문자를 L이라고 하고,

L extends '0' ? ParseInt<`${MinusOne<ParseInt<V>>}${MinusOneNums[L]}`> : L이 0이면, 앞 자리 수도 -1을 해주어야 하므로 재귀를 통하여 앞자리 수를 MinusOne<ParseInt<V>>로 넘겨서 앞자리 수도 -1을 해준다. 그리고 최종적으로 나오는 문자열에 ParseInt를 하여 number타입으로 바꿔준다.

L extends keyof MinusOneNums ? ParseInt<`${V}${MinusOneNums[L]}`> : L이 0이 아닌 MinusOneNums의 key 중 하나라면 그냥 L만 -1해서 앞 문자열(V)에 붙여준다. 따라서 최종적으로 `${V}${L-1}` 형태가 되는데, 이것을 PaseInt를 통해 number타입으로 바꾸어 주면 된다.

그리고 나머지 상황에서는 never를 리턴하게 해준다. 

 

 

이번 타입 챌린지를 하면서 T extends `${infer F extends number}`와 같이 분산 조건부 타입을 사용할 수 있다는 것을 깨달았다... 엄청 어려웠지만, 유익했다!