중복 문자 제거

파이썬 알고리즘 인터뷰 21. 중복 문자 제거

1. 이번주 문제 중 가장 어려웠던 문제.

파이썬 알고리즘 인터뷰를 정동지와 함께 풀면서 이번주 가장 어려웠던 문제였던 것 같다. 우선 문제를 이해하는데 시간을 많이 소모했다. 사전식 순서는 말그대로 사전에서 가장 빨리 찾을 수 있는 순서를 말한다. 이 문제에서는 중복을 제거 조건을 추가되어 있다. 그래서 중복 여부에 따라서 순서를 조정해야 하는 부분이 조금 까다롭게 다가왔던 문제이다.

2. 문제의 컨셉

문제의 가장 핵심적인 컨셉은

1. 문자열 내, 문자의 갯수를 count하고
2. 스택을 사용해 현재 문자와 비교한다.
   • 스택(Stack) : 출력할 문자를 저장하는 공간.
   • 셋(HashSet) : 문자의 중복 여부를 확인할 공간.
   • 스택 요소 제거 조건
     1. 현재 문자가 스택에 쌓여 있는 문자보다 앞선 문자이고(현재 문자 < stack.peek()),
     2. 뒤에 다시 붙일 문자가 남아 있다면(count > 0), 스택 요소를 제거한다.

3. Code

HashMap(counter)과 HashSet(중복 체크)을 이용한 문제 풀이
int[](counter)와 visited(중복 체크)를 이용한 문제 풀이

두가지 코드의 로직은 같으나, 중복 요소를 확인하기 위하여 Set을 선언했고, 다른 하나는 boolean[]을 사용하였다. 실행 시간을 확인해본 결과, 아까 말한 순서대로 5ms, 1ms가 측정되었는다. 아마 boolean에서 true/false 값에 따라 하위 로직의 진행 여부가 달라지기 때문에 시간 효율이 다른 것 같다고 예상한다. 내일 정동지와 같이 디스커션하면서 원인에 대해서 공부해봐야겠다.

4. 문제 삽질하면서 알아낸 것들.

• Collections.frequency(객체를 담고 있는 컬렉션 인스턴스, 기대하는 객체) : Collection 안에 객체가 몇번 등장했는지 리턴해주는 함수.

• Map method

  • putIfAbsent(key, value) : key값이 존재하지 않을 떄, (key, value)를 추가한다.
  • computeIfPresent(K, BiFunction<? super K, ? super V, ? extends V> remappingFunction) : key가 존재할 경우, 해당 함수를 실행한다.

• python : Collections.Counters(s) : 문자열 내의 문자 갯수를 집계하는 함수

• java로 구현할 때는 HashMap을 이용해서 구현!

   Map<Chracter, Integer> map = new HashMap<>();

   for(char c : s.toCharArray()) {
      map.putIfAbsent(c, 1);
      map.computeIfPresent(c, (k,v) -> v + 1);
   }