공모전에 참가했던 우리 팀은 `Tanstack Query`를 사용하면서 `caching` 및 `mutation`에 사용되는 `queryKey`, `mutationKey`를 효과적으로 관리하는 방법에 대해 고민을 많이 하였습니다.

1. 문제인식

1. `useMutation`으로 인해 컴포넌트가 너무 길어져 가독성을 저해한다.
2. 각 컴포넌트에서 키를 선언하면 통합 및 관리가 어렵다
3. 같은 `mutation`을 사용하는 경우, 컴포넌트마다 선언해줘야 한다.

 

이러한 문제를 해결하기 위해 저희 팀은 모듈화를 통한 Key 관리 를 진행하였습니다.

 

어떻게 모듈화를 진행했는지 설명해보겠습니다.

 


2. 기본 Tanstack Query 호출

useMutation
공식문서
queries와는 다르게, mutations는 생성(POST) / 수정(PATCH) / 삭제(DELETE) 작업을 수행할 때 사용됩니다.

 

`useMutation`을 사용하여 비동기 호출을 하면 다음과 같은 코드로 작성됩니다.

const App = ():ReactNode => {
  const { data, isPending, isSuccess, isError, error, mutate } = useMutation({
    mutationFn: newTodo => {
      return axios.post('/todos', newTodo)
    },
  })

  let content
  if (isPending) {
    content = 'Adding todo...'
  }
  if (isError) {
    content = <div>An error occurred: {error.message}</div>
  }
  if (data) {
    if (isSuccess) content = <div>Todo added!</div>
  }

  return (
    <>
      <button
        onClick={() => {
          mutate({ id: new Date(), title: 'Do Laundry' })
        }}
      >
        Create Todo
      </button>
      {content}
    </>
  )
}

 

하지만, 대부분의 경우 `mutation`은 `queries`와 함께 사용됩니다.

 

예를 들어, `Todo`의 정보를 데이터베이스에 저장하는 위의 코드에서, 한 가지 기능을 추가해보겠습니다.

유저의 기존 `Todo`를 불러와서 렌더링하고, 새로운 `Todo`를 생성하면 불러온 값을 `Update`하는 코드로 수정해야 한다면 어떻게 할까요?

 

invalidateQuries를 통해 caching된 값을 stale 상태로 만들어, Refetch하도록 유도해야 합니다.

 

실행방법

  1. `useQuery`를 통해 데이터를 불러와야 합니다.
  2. 유저가 `Todo`를 추가하면 `useMutation`을 호출하고, 데이터베이스를 업데이트합니다.
  3. 기존에 페칭했던 `useQuery` 데이터를 `invalidate` 해서 refetch를 유도해야 합니다.

(주석을 따라가며 이해해 보세요)

const Todo = () => {
  const queryClient = useQueryClient();

  // 1. useQuery로 Todo 데이터 불러오기
  const { data: todos, isLoading, isError } = useQuery(['todos'], fetchTodos);

  // 2. useMutation으로 Todo 추가
  const mutation = useMutation(addTodo, {
    onSuccess: () => {
      // 3. 데이터를 invalidate하여 최신 상태를 가져오기
      queryClient.invalidateQueries(['todos']);
    },
  });

  // mutate 사용처
  const handleAddTodo = () => {
    const newTodo = { title: `Todo ${Date.now()}` };
    mutation.mutate(newTodo);
  };

  if (isLoading) return <p>Loading...</p>;
  if (isError) return <p>Error loading todos</p>;

  return (
    <div>
      <h1>Todo List</h1>
      <ul>
        {todos.map((todo: { id: number; title: string }) => (
          <li key={todo.id}>{todo.title}</li>
        ))}
      </ul>
      <button onClick={handleAddTodo} disabled={mutation.isLoading}>
        {mutation.isLoading ? 'Adding...' : 'Add Todo'}
      </button>
    </div>
  );
};

 

저희도 처음에는 이렇게 개발 초기에는 개발을 하다보니, 몇 가지 문제점들이 발생했습니다.

  1. `useMutation`으로 인해 컴포넌트가 너무 길어져 가독성을 저해한다.
    • 모든 `Mutation` 마다 `invalidateQueries`를 해주는 행위는 상당히 번잡합니다.
    • `useMutation`의 `onSuccess`, `onError`에 모달, 토스트 띄우기 등 로직을 추가하다 보면, 코드가 길어집니다.
    • 혹여나, 하나의 컴포넌트에서 여러개의 `Mutation`을 사용한다면, 컴포넌트는 겉잡을 수 없을 정도로 길어집니다.
    // 하나의 컴포넌트에서 Mutation이 너무 많은 경우
    // 1. Todo 추가
    const { mutate : addTodoMutation }= useMutation(addTodo, {
      onSuccess: () => {
        queryClient.invalidateQueries(['todos']);
      },
    });
    
    // 2. Todo 수정
    const { mutate : updateTodoMutation }= useMutation(updateTodo, {
      onSuccess: () => {
        queryClient.invalidateQueries(['todos']);
      },
    });
    
    // 3. Todo 삭제
    const { mutate : deleteTodoMutation }= useMutation(deleteTodo, {
      onSuccess: () => {
        queryClient.invalidateQueries(['todos']);
      },
    });
    
    
  2. queryKey 통합 관리가 어렵다.
    • 특정 mutation 이후 `invalidate` 하는 `queryKey`를 찾기 위해 코드를 찾아다녀야 합니다.
    • 새로운 `Query`의 `queryKey` 설정을 위해서는 기존에 사용되었던 값 들을 찾아다녀야 합니다
  3. 반복되는 `mutation`을 계속해서 선언해주어야 한다.
    • 좋아요, 스크랩을 추가하고 삭제하는 기능을 개발한다고 할 때, 좋아요를 누르는 행위는 많은 페이지에서 동일하게 이루어졌습니다.
    • 모든 컴포넌트에서 동일한 `useMutation`을 선언하여 사용해야 했습니다. 이는 매우 번거롭고 귀찮은 행위입니다. (유지보수에 최악)
    • 이때, 같은 `mutation`은 같은 `invalidate`를 수행해야 하므로, 반복 코드가 발생할 뿐만 아니라, 실수의 가능성도 있습니다.

 

💡 이러한 이유로, queryKey와 mutationKey, useMutation 함수를 모두 하나의 파일에서 관리하는 모듈화 방법을 사용하였습니다.


3. 모듈화 방법

1. Key 관리 (QueryKey, MutationKey)

QueryKey

  • `QueryKey`는 `caching`된 값에 접근할 수 있는 매우 중요한 값입니다.
  • 매번 접근할 때마다 잘못된 값에 접근하지 않고 편리하게 접근하기 위해 객체로 관리합니다.
// cache-key.ts
export const QUERY_KEYS = {
  USER: {
    PLANS: {
      INDEX: ['plans', 'user'],
      SCRAP: ['plans', 'user', 'scrap'],
    },
    PLAN: {},
    PLACES: {
      SCRAP: ['places', 'user', 'scrap'],
    },
    PLACE: {},
  },
  GENERAL: {
    PLANS: {
      INDEX: ['plans'],
    },
    PLAN: {
      INDEX: (planId: number) => ['plan', planId],
    },
    PLACES: {
      INDEX: ['places'], // 일반 여행지
    },
  },
}

MutationKey

  •  `mutationKey`는 `queryKey` 보다는 중요하지 않습니다. `mutationKey`는 `mutation`을 구분하거나, `useMutationState`를 통해 이전 `mutation` 값을 불러오는데 사용됩니다.
  • `mutation`에는 항상 비동기 함수가 매핑됩니다. 따라서, `mutationKey` 값 이외에 비동기 함수도 같이 값으로 저장해주었습니다.
// todo가 아닌, 실제 사용했던 코드로 대체합니다
// cache-key.ts
export const MUTATION_KEYS = {
  PLAN: {
    CREATE: {
      key: ['createPlan'],
      fc: createPlan, // 비동기 함수
    },
    UPDATE: {
      key: ['updatePlan'],
      fc: updatePlan,
    },
     ...
    },
    SCRAPS: {
      ADD: {
        key: ['addPlanScrap'],
        fc: addPlanScrap,
      },
      DELETE: {
        key: ['deletePlanScrap'],
        fc: deletePlanScrap,
      },
    },
    COMMENTS: {
      ADD: {
        key: ['addPlanComment'],
        fc: addPlanComment,
      },
    },
  },
} as const

💡setDefaultMutation으로 미리 useMutation 정의하기

setDefaultMutation 공식문서

 

왜 `setDefaultMutation`을 사용하나요❓
`setDefaultMutation`은 `mutationKey`와 `mutationFn`을 연결하여 미리 선언된 `queryClient`에 정의할 수 있습니다.

⭐이후, 컴포넌트에서 `mutationKey`만 으로 간편하게 `mutation`에 접근 가능합니다.⭐

 

어떻게 선언하나요?

 

1. 아래와 같이 미리 `mutation`에 `mutationKey`와 `mutationFn`이 연결되도록 선언합니다.

// #1. Plan
queryClient.setMutationDefaults(MUTATION_KEYS.PLAN.CREATE.key, {
  mutationFn: MUTATION_KEYS.PLAN.CREATE.fc,
  onSuccess(data, variables, context) {
    queryClient.invalidateQueries({ queryKey: QUERY_KEYS.USER.PLANS.INDEX })
  },
  onError: () => {
    toast({ title: '서버 오류 다시 시도해주세요' })
  },
})

 

2. `useMutation`을 사용하고자 하는 컴포넌트에서 `mutationKey`만 지정해주면 간편하게 사용 가능합니다.

const { mutate: createPlanMutate, isPending: isCreating } = useMutationStore<CreatePlanType>(MUTATION_KEYS.PLAN.CREATE.key)

 

 `useMutationStore`은 무엇인가요

`useMutationStore`는 Tanstack Query의 기본 함수가 아닙니다.

useMutation의 Response Type을 지정하고 (백엔드 팀과 Response 형태 맞추기), 비동기 호출의 매개변수 variables의 Type을 재네릭으로 지정하여 사용한 함수입니다.

/**
 * Type T에서 key K의 value들로 이루어진 Type 생성하는 유틸함수 (재귀)
 */
export type ExtractValueByKey<T, K extends string> = T extends { [key in K]: infer V }
  ? V
  : {
      [key in keyof T]: ExtractValueByKey<T[key], K>
    }[keyof T]

// 위에서 정의한 MUTATION_KEYS의 key값들을 유니온 값으로 갖는 Type
export type MutationKeyType = ExtractValueByKey<typeof MUTATION_KEYS, 'key'>

export const useMutationStore = <T>(mutationKey: MutationKeyType) => {
  return useMutation<SuccessResponse, Error, T, unknown>({ mutationKey })
}

  • 제너릭 타입으로 제공하는 Variables Type은 해당 useMutation이 사용하는 비동기 함수의 객체 형태로 제공하는 매개변수의 Type입니다.
// 객체 형태의 함수 매개변수 Type
export interface CreatePlanType {
  state: StateType
  startDate: Date
  endDate: Date
  accessToken: string
}
/**
 * 새로운 여행 계획 만들기
 * @param param0 `{state: 지역, startDate: Date, endDate: Date, accessToken: string}`
 * @returns data: `{planId: number}`
 */
export const createPlan = async ({ state, startDate, endDate, accessToken }: CreatePlanType) => {
  let backendRoute = BACKEND_ROUTES.PLAN.CREATE
  const body = {
    state: state,
    startDate: formatDateToHyphenDate(startDate),
    endDate: formatDateToHyphenDate(endDate),
  }

  const res = await fetch('/server' + backendRoute.url, {
    method: backendRoute.method,
    headers: {
      Authorization: accessToken,
      'Content-Type': 'application/json',
    },
    body: JSON.stringify(body),
    credentials: 'include',
  })
  ... api logic
  
}

 

참고) `useMutation`의 기본 Type 선언을 참고하여 변형하였습니다.

// 기본 타입선언
// useMutation.d.ts
import { UseMutationOptions, UseMutationResult } from './types.js';
import { DefaultError, QueryClient } from '@tanstack/query-core';

declare function useMutation<TData = unknown, TError = DefaultError, TVariables = void, TContext = unknown>(options: UseMutationOptions<TData, TError, TVariables, TContext>, queryClient?: QueryClient): UseMutationResult<TData, TError, TVariables, TContext>;

export { useMutation };

 


4. 최종 형태

이렇게 하면, 초반에 작성했던 코드는 다음과 같이 매우 짧고 가독성이 좋은 코드로 바뀝니다.

const Todo = () => {
  const queryClient = useQueryClient();

  // 1. useQuery로 Todo 데이터 불러오기
  const { data: todos, isLoading, isError } = useQuery(['todos'], fetchTodos);

  // 2. useMutation으로 Todo 추가 (매우 짧아짐)
  const {mutate, isPending} = useMutationStore<addTodoType>(MUTATION_KEYS.TODO.ADD.key)

  // 새로운 Todo 추가 핸들러
  const handleAddTodo = () => {
    const newTodo = { title: `Todo ${Date.now()}` };
    mutation.mutate(newTodo);
  };

  if (isLoading) return <p>Loading...</p>;
  if (isError) return <p>Error loading todos</p>;

  return (
    <div>
      <h1>Todo List</h1>
      <ul>
        {todos.map((todo: { id: number; title: string }) => (
          <li key={todo.id}>{todo.title}</li>
        ))}
      </ul>
      <button onClick={handleAddTodo} disabled={mutation.isLoading}>
        {mutation.isLoading ? 'Adding...' : 'Add Todo'}
      </button>
    </div>
  );
};

💡 로직 분리하기

개발을 진행하며, 유지보수를 위해 `caching` 로직과 컴포넌트에서 사용될 로직을 구분지어 사용하였습니다.

cache-key.ts`에서의 `onSuccess`와 개별 클라이언트의 onSuccess의 용도를 구분해서 사용했습니다.

컴포넌트의 mutate의 onSuccess(onError)가 cache-key.ts의 onSuccess(onError) 보다 먼저 실행됩니다.
// 컴포넌트
const {mutate, isPending} = useMutationStore<addTodoType>(MUTATION_KEYS.TODO.ADD.key)
  
const handleAddTodo = () => {
  const newTodo = { title: `Todo ${Date.now()}` };
  mutation.mutate(newTodo, {
	  // 실행 1번
	  onSuccess() {
	  	setState(어떤 값으로 바꾼다)
        router.push(어디로 이동한다)
	  }
  });
};

// cache-key.ts
queryClient.setMutationDefaults(MUTATION_KEYS.PLAN.CREATE.key, {
  mutationFn: MUTATION_KEYS.PLAN.CREATE.fc,
  // 실행 2번
  onSuccess(data, variables, context) {
    queryClient.invalidateQueries({ queryKey: QUERY_KEYS.USER.PLANS.INDEX })
  },
})​
  • 특정 `mutation`이 공통적으로 수행하는 `invalidate`과 같은 행위는 `cache-key.ts`에서 다루며
  • `state`관리 등의 컴포넌트 단위 프로세스는 컴포넌트 내부에서 선언한 `useMutationStore`의 리턴 값인 `mutate` 함수의 `onSuccess`, `onError`에서 관리합니다.

  • 컴포넌트 `mutate`: state 변화, toast 처리, routing 등을 처리
  • `cache-key.ts` : invalidateQuries 등 caching 처리

 


참고 문헌

Tanstack Query useMutation 공식문서

Tanstack Query setMutaitonDefault 공식문서

Tanstack Query invalidate Query 공식문서

들어가며

Tanstack Query의 `useQuery`는 HTTP GET 요청을 보낼 때 사용하는 함수입니다.

이 함수에는 GET 요청에 사용될 비동기 함수를 지정하는 queryFn과, 받아온 데이터를 캐싱할 queryKey를 지정할 수 있습니다.

 

공식문서 보기

 

이때, queryFn의 인자로 아래 코드와 같이 `QueryFunctionContext`가 제공되는데, 이를 활용하는 방법에 대해 알아보겠습니다.

 

// useQuery에서 제공되는 QueryFunctionContext
  const { data, isPending, isError, error } = useQuery({
    queryKey: ['post', postId],
    queryFn: (QueryFunctionContext) => user_async_function() // QueryFunctionContext의 위치
    enabled: postId !== undefined
  })

QueryFunctionContext의 구성요소

`queryFn`은 `QueryFunctionContext`를 객체 형식의 인자로 제공합니다.

 

공식문서에서는 다음과 같이 설명해줍니다.

[공식문서]
The QueryFunctionContext is the object passed to each query function. It consists of:
1. queryKey: QueryKey - Query Keys  
2. signal?: AbortSignal
- AbortSignal instance provided by TanStack Query
- Can be used for Query Cancellation
3. meta: Record<string, unknown> | undefined
- an optional field you can fill with additional information about your query

 


queryKey

`queryKey`는 해당 `useQuery`에서 사용된 `queryKey`를 반환합니다.

 

이는 Query Key에 변수 값을 사용할 경우, 해당 값을 `queryFn`의 인자로 적용해야 할 때 유용합니다.

 

예를 들어, 글의 ID값을 기반으로 API를 호출한다고 가정해보겠습니다.

 

[대략적인 프로세스]

  1. 글의 id 값을 async fetch. (다른 API를 통해)
  2. 해당 id를 가진 글을 사용자가 클릭하면, 글의 정보를 async fetch.
  3. 이때, queryKey를 ['post', postId] 형태로 관리.

해당 로직은 기본적으로 다음과 같이 useQuery를 활용하여 구현할 수 있습니다.

// #0. Fetch Info using planId (useQuery)
  const { data, isPending, isError, error } = useQuery({
    queryKey: ['post', postId],
    queryFn: () => getPlan({postId: postId})
    enabled: postId !== undefined
  })

 

이때, 제공되는 `queryKey` 값을 사용하면 컴포넌트에서 관리하는 state대신 useQuery에서 사용되는 queryKey를 사용할 수 있습니다.

  • `queryKey`는 위에서 제공해준 값과 동일하게 주어진다. (예시의 경우 ['post', postId])
const { data, isPending, isError, error } = useQuery({
  queryKey: ['post', postId],
  queryFn: ({ queryKey }) => getPlan({ postId: queryKey[1] }),
  enabled: postId !== undefined,
});

 

이처럼 queryKey를 통해 postId 값을 쉽게 활용할 수 있습니다.

그래서 뭐..? 같은 값에 접근하여 사용하는거 아닌가..?🤔

네 맞습니다.

 

위 예시는 `postId`에 해당하는 하나의 변수만은 `queryKey`에 사용하지만, 복잡한 구조를 가진 코드에서 변수 값을 찾으러 다니기 보다, 가장 가까운 `queryKey`에서 찾는 것이 미래의 내가 코드를 다시 읽을때 편리하지 않을까요?

아래 그림의 2번 루트가 1번 루트보다 가깝다고 할 수 있으니, 디버깅 하기에 원활하지 않을까 생각합니다.

queryKey 부연설명


signal: AbortSignal

(AbortSignal은 Typescript에서 사용하는 type입니다. 기본적으로 제공되는 타입이므로 import하지 않아도 됩니다.)

 

다음은 `signal`입니다. 개인적으로 이해하는데 상당히 애먹었던 개념입니다.

먼저, MDN에서는 Signal에 대해 이렇게 설명합니다.

[MDN, AbortSignal]
AbortSignal 인터페이스는 DOM 요청(Fetch와 같은)과 통신하고 필요한 경우 AbortController 객체를 통해 취소할 수 있게 해주는 신호 객체를 나타냅니다.

 

직역하면, “통신을 취소”할 때 발생하는 “신호”로 이해할 수 있습니다.

 

 

이때, `queryFn`에서 제공하는 signal은 useQuery로 인해 발생하는 signal을 자동으로 관리하는 역할을 수행합니다.

즉, Tanstack Query의 라이프사이클(쿼리 재시작, 컴포넌트 언마운트 등)에 따라 자동으로 쿼리를 취소하는 역할을 합니다. 따라서, 개발자는 fetch의 옵션으로 signal을 제공해주기만 하면 됩니다.

 

구현 예제

async function fetch_example({ queryKey, signal }) {

	// 다음과 같이 signal을 옵션으로 넘겨주면 됩니다
	const response = await fetch(`/api/todos?status=${status}&page=${page}`, { signal });
	if (!response.ok) {
		throw new Error('Failed to fetch data');
	}
	return response.json();

	if (err.name === 'AbortError') {
		console.log('Request aborted');
		return;
	}
	throw err;
}

 

Signal에 대해 이해하셨다면, 이를 직접 생성하여 `fetch` 요청을 자유자재로 다룰 수 있습니다.

 

예를 들어

유저는 너무 길어지는 GET 요청에 화난 나머지, “취소” 버튼을 눌러 요청을 중단하고 싶다고 하면, 해당 버튼을 클릭했을때 요청이 중단되어야 합니다. 그렇지 않으면, 화난 유저는 사이트를 떠나 버리거나 쌍욕을 하며 회원탈퇴를 해버릴 수도 있습니다.

 

또는 개발자 측에서 길어지는 요청을 방지하기 위해, 의도적으로 Abort 시키는 방법도 있습니다.

이후, 유저에게 “네트워크 상황을 확인해주세요” 토스트를 띄워, 유저의 네트워크 상황에 의한 시간지연을 웹사이트 성능의 문제점으로 인식시키지 않도록 할 수 있습니다.

 

 

이처럼, AbortSignal은 요청을 취소하는 신호 객체로, 긴 요청을 중단하거나 사용자가 중단 버튼을 클릭했을 때 유용합니다.

 

다음은 일정시간이 지난 이후, 의도적으로 개발자가 요청을 중단시키는 코드입니다.

구현 예제

async function fetchWithTimeout({ queryKey, signal: querySignal }) {
  const [_key, { status, page }] = queryKey;
  const controller = new AbortController();
  const timeoutId = setTimeout(() => controller.abort(), 10000); // 10초 후 요청 중단

  const signal = querySignal || controller.signal;

  try {
    const response = await fetch(`/api/todos?status=${status}&page=${page}`, { signal });
    clearTimeout(timeoutId);

    if (!response.ok) {
      throw new Error('Failed to fetch data');
    }
    return response.json();
  } catch (err) {
    if (err.name === 'AbortError') {
      console.log('Request aborted');
      return;
    }
    throw err;
  }
}

 

 

useQuery는 기존처럼 동일하게 사용하면 됩니다.

function Todos({ status, page }) {
  const { data, error, isLoading } = useQuery({
    queryKey: ['todos', { status, page }],
    queryFn: fetchWithTimeout,
  });

  if (isLoading) return <p>Loading...</p>;
  if (error) return <p>Error: {error.message}</p>;

  return (
    <ul>
      {data.map(todo => (
        <li key={todo.id}>{todo.title}</li>
      ))}
    </ul>
  );
}

🤔근데, AbortController을 통해 객체를 따로 생성하는 이유는 무엇이에요?

말씀드렸다 시피, queryFn에서 제공하는 signal은 Tanstack Query의 라이프사이클(쿼리 재시작, 컴포넌트 언마운트 등)에 따라 자동으로 쿼리를 취소하는 역할을 하므로, 특정한 상황에 대응하기 위해서는 객체를 직접 생성해야 합니다.

 

이를 활용하여 다양한 `fetch`에 대한 커스텀 훅을 만들어서 npm package로 관리해보는 것도 좋은 방법일 것 같습니다.


meta

meta는 개발자가 원하는 값을 객체 형태로 추가할 수 있는 필드입니다.

 

예를 들어, fetch마다 다른 에러 메시지를 관리하고 싶을 때 활용할 수 있습니다.

 

이때, v5부터 `onError`, `onSuccess`, `onSettled` 과 같은 콜백 함수들을 더이상 useQuery에서 사용할 수 없으므로, QueryClient 객체에서 다음과 같이 설정해주어야 합니다.

 

[콜백함수가 사라진 이유]

 

구현 예제

const queryClient = new QueryClient({
  queryCache: new QueryCache({
    onError: (error, query) => {
      if (query.meta.errorMessage) {
        toast.error(query.meta.errorMessage);
      }
    },
  }),
});

export function useTodos() {
  return useQuery({
    queryKey: ['todos', 'list'],
    queryFn: fetchTodos,
    meta: { errorMessage: 'Failed to fetch todos' },
  });
}

 

 


마치며

QueryFunctionContext는 queryKey, signal, meta와 같은 다양한 기능을 제공합니다.

창의적이고 새로운 기술을 만드는 것도 좋지만, 사용하고 있는 기술에 대해 깊이있게 이해하는 것도 중요하다고 생각되는 공부였습니다.

 

참고 문헌

TODO LIST

  • 길어지는 요청에 대한 fetch 함수를 커스텀 함수로 만들어서 관리하기
  • queryFn의 abort에 대한 역할을 직접 network tab에서 관찰해보기

✍️문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

  • 구조대 : 119
  • 박준영 : 97 674 223
  • 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
  • phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

조건으로 얻을 수 있는 정보

1. 배열의 길이가 `10^6` 이므로, 시간복잡도 `O(n x logn)`이 되도록 구현하여야 1초(10^8) 내에 실행 가

2. `O(n^2)` 방법은 시간 내에 처리 불가능하지만, 시간이 부족하면 이를 채택 (실전)

 

1️⃣ Brute False

누구나 가장 먼저 생각나는 방법으로, 각 phone_number를 순회하면서 해당 번호를 접두어로 사용하고 있는 phone_number가 있는지 판단하는 방법이다.

 

- 최소한의 최적화를 위해, 비교하는 두 phone_number를 문자열이 아닌 숫자로 변환하여 비교하였다.

is_jupdo : 문자열 비교

is_jupdo2 : 숫자 비

// #시도1. Brute false 문자열 비교, 시간초과
function is_jupdo(target, diff) {
  const target_len = target.length;

  for (let i = 0; i < target_len; i++) {
    if (target[i] !== diff[i]) {
      return false;
    }
  }
  return true;
}

// #시도2. Brute False 숫자 비교, 시간초과
function is_jupdo2(target, diff, power_10) {
  const target_len = target.length;
  const diff_len = diff.length;

  if (Math.floor(diff / power_10[diff_len - target_len]) - target === 0) {
    return true;
  }
  return false;
}
function solution(phone_book) {
  const len = phone_book.length;
  const power_10 = [1];

  // 10의 거듭제곱 값 넣기
  for (let i = 1; i <= 20; i++) {
    power_10[i] = power_10[i - 1] * 10;
  }

  phone_book.sort((a, b) => a.length - b.length);

  for (let i = 0; i < len - 1; i++) {
    const target = phone_book[i];
    for (let j = i + 1; j < len; j++) {
      const diff = phone_book[j];
      // Compare
      if (is_jupdo2(target, diff, power_10)) {
        return false;
      }
    }
  }
  return true;
}

 

효율성 테케 실행 결과 역시나 실패

 

2️⃣Hash Table

1. phone_number 값을 객체 (Hash Table)에 저장한다. (아래 그림 참고)

2. 각 phone_number를 순회하며, 생성가능한 모든 접두어가 객체(Hash Table)에 존재하는지 확인한다.

Hash Table 구조

// 시도3: Hash Table만들기
function solution(phone_book) {
  const table = {};
  for (const phone of phone_book) {
    table[phone] = true;
  }

  for (const phone of phone_book) {
    const len = phone.length;
    for (let i = 1; i < len; i++) {
      const substr = phone.substring(0, i);
      if (table[substr] === true) {
        return false;
      }
    }
  }

  return true;
}

 

효율성 테케 실행 결과 성공

 


분석

1️⃣Brute False

  • solution 함수에서는 전화번호를 길이 순으로 정렬한 후, 각 번호와 그 다음 번호들 간의 비교를 반복한다.
  • 여기서 이중 반복문을 사용하므로, 시간 복잡도는 최악의 경우 O(n^2)다.
  • 또한, is_jupdo 호출은 두 문자열의 길이에 비례하여 O(m) 시간이 소요되며, 이는 두 문자열 길이의 최대값에 의해 결정된다.
  • 따라서 전체 시간 복잡도는 `O(n^2×m)`로, 전화번호의 수가 많거나 각 번호의 길이가 길면 성능이 최악이다.

2️⃣Hash Table

  • 해시 테이블에 각 전화번호를 저장한 후, 각 전화번호의 접두사가 테이블에 있는지 확인한다. (O(n))
  • 각 phone_number의 길이-1 만큼 hash table에 접두어가 있는지 확인한다. (O(m))
  • 따라서, 이 방법의 시간 복잡도는 `O(n×m)`로, n은 전화번호 개수이고, m은 각 전화번호의 길이이다.

'PS' 카테고리의 다른 글

[파이썬] 코테 꿀팁  (2) 2024.10.10
Javascript PS 꿀팁 저장소  (0) 2024.06.29

+ Recent posts