[Algorism/HackerRank] Frequency Queries

👉 문제 링크

✏️ 문제 요약

• 숫자를 저장, 제거, 빈도수 검색을 할 수 있는 쿼리 메소드를 만듬
• 숫자를 저장하면 빈도수는 증가
• 숫자를 제거하면 빈도수는 감소

  ex 쿼리...
  1 1 // 숫자 1 저장
  1 1 // 숫자 1 저장
  3 2 // 빈도수 2를 검색했을 때 숫자 1이 있음
  2 1 // 숫자 1 제거
  3 1 // 빈도수 1로 검색했을 때 숫자 1이 있음
  1 3 // 숫자 3 저장
  3 1 // 빈도수 1로 검색했을 때 숫자 1 또는 3이 있음

💡 문제 풀이

• 숫자별로 빈도수를 관리하기 위해 맵을 사용
  => 단, 맵 하나만 사용하면 맵의 모든 value에서 빈도수와 일치하는 값을 검색해야 함
  => 맵을 하나만 사용하면 TC 중 검색 쿼리시에 1개에서 타임 아웃 발생함
  => 문제에서 원하는건 검색시에도 O(1)만 원하는 것으로 보임
  => Worst Case에서는 명령어 loop까지 O(N^2)이라서 그럴지도...

• 상단 타임아웃 처리를 위해 빈도수를 기준으로 몇 개의 숫자가 있는지 관리하는 맵 사용

💻 구현 코드

코드 보기

  static final int INSERT_COMMAND = 1;
  static final int DELETE_COMMAND = 2;
  static final int SEARCH_COMMAND = 3;

  // Complete the freqQuery function below.
  static List<Integer> freqQuery(List<List<Integer>> queries) {
      List<Integer> answerList = new ArrayList<>();

      Map<Integer, Integer> numberMap = new HashMap<>();  // 저장할 숫자 기준으로 빈도수를 가지고 있는 맵
      Map<Integer, Integer> frequencyMap = new HashMap<>();  // 빈도수를 기준으로 몇개의 숫자가 있는지 관리하는 맵

      for (List<Integer> query : queries) {
          int command  = query.get(0);
          int num = query.get(1);

          switch (command) {
              case INSERT_COMMAND:
                  if (numberMap.containsKey(num)) { 
                      // 저장전 빈도수 관리맵에서 해당 숫자의 빈도수를 제거
                      frequencyMap.computeIfPresent(numberMap.get(num), (key, frequency) -> frequency - 1);
                  }

                  numberMap.merge(num, 1, Integer::sum);

                  // 저장후 빈도수 관리맵에서 해당 숫자의 빈도수를 추가
                  frequencyMap.compute(numberMap.get(num), (key, frequency) -> frequency == null ? 1 :  frequency + 1);
                  break;
              case DELETE_COMMAND:
                  if (numberMap.containsKey(num)) {
                      // 저장 명령어와 동일한 처리
                      frequencyMap.computeIfPresent(numberMap.get(num), (key, frequency) -> frequency - 1);
                  }

                  numberMap.computeIfPresent(num, (key, value) -> value > 0 ? value - 1 : 0);

                  if (numberMap.containsKey(num)) {
                      // 저장 명령어와 동일한 처리
                      frequencyMap.compute(numberMap.get(num), (key, frequency) -> frequency == null ? 1 : frequency + 1);
                  }
                  break;
              case SEARCH_COMMAND:
                  int answer =  frequencyMap.getOrDefault(num, 0) > 0 ? 1 : 0;
                  answerList.add(answer);
                  break;
          }
      }

      return answerList;
  }