[자바 알고리즘 인터뷰] 9장 스택,큐(2) - 중복 문자 제거

 

https://leetcode.com/problems/remove-duplicate-letters/description/

 

 

 

- 중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열하라 

 

 

풀이 1) 재귀를 이용한 분리 

 

사전식 순서(Lexicographical Order)

 

- 사전에서 가장 먼저 찾을 수 있는 순서 

- bcabc에서 중복 문자를 제외하면 사전에서 가장 먼저 찾을 수 있는 문자열은 abc가 된다. 

 

- ebcabc가 입력값이라면 결과는 eabc가 된다. 

 -> e 문자 자체는 해당 문자열 내에서는 사전에서 가장 뒤에 있지만 e는 입력값에서 딱 한번만 등장하고, a,b,c는 뒤이어 등장하기 때문에 e의 위치를 변경할 수 없기 때문이다. 

 

- ebcabce라면 첫 번째 e는 중복으로 제거할 수 있고 마지막 e를 남겨서, 결과는 abce가 될 수 있다. 

 

<dbacdcbc를 사전식 순서로 중복 문자를 제거>

 

- 중복 문자를 제외한 알파벳순으로 문자열 입력값을 모두 정렬한 다음 가장 빠른 a부터 접미사 suffix를 분리해 확인한다. 

- a는 가장 빠른 알파벳일뿐만 아니라 문자열에서도 b,c,d도 뒤에 있기 때문에 가장 먼저 정답으로 추출할 수 있다. 

 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자 :박상길 <책만>

 

- a가 빠지고 cdcbc가 남은 상태에서 다음 알파벳 순서는 b이지만 b를 추출하면 그 뒤에 남은 문자가 c밖에 없기 때문에 d를 추출할 수 없다. 

 

- 분리 가능 여부는 전체 집합과 접미사 집합이 일치하는지 여부로 판별 가능 

if(toSortedSet(s).equals(toSortedSet(suffix))) {
	...

 

- 집합은 중복된 문자가 제거된 자료형이므로 b를 기준으로 분리한다고 할 때 남아 있는 문자는 s={b,c,d}이고 suffix={b,c}로 두 집합이 일치하지 않는다. 

 

- 그 다음 알파벳 순서인 c로 넘기고 이제 c로 분리하면 s={b,c,d}와 suffix={b,c,d}로 두 집합이 일치해 분리가 가능하다.

 

- 일치하는 변수명 c를 정답으로 추출하고 나머지 문자열을 입력값으로 하여 다시 재귀호출 

- 이때 추출한 문자는 이후에 이어지는 모든 c를 replace()로 제거한다.

//전체 집합과 접미사 집합이 일치하면 해당 문자 정답에 추가하고 재귀 호출 진행
if(toSortedSet(s).equals(toSortedSet(suffix))) {
    return c + removeDuplicateLetters(suffix.replace(String.valueOf(c),""));
}

 

- 이렇게 하면 일종의 분할 정복과 비슷한 형태로 접미사 suffix의 크기는 점점 줄어들고 더 이상 남지 않을 때 백트래킹되면서 결과가 조합된다. 

 

import java.util.*;

class Solution {
    public Set<Character>toSortedSet(String s) {
        //문자열을 문자 단위로 집합으로 저장할 변수 선언
        Set<Character> set = new TreeSet<>(new Comparator<Character>() {
            //비교 메소드 재정의 
            @Override
            public int compare(Character o1, Character o2) {
                //동일한 문자이면 무시 
                if(o1==o2)
                    return 0;
                //새로운 문자(o1)가 기본 문자(o2)보다 크면 뒤에 위치 
                else if(o1>o2) 
                    return 1;
                //작으면 앞에 위치
                else
                    return -1;
            }
        });

        //문자열을 문자 단위로 집합에 저장. 정렬된 상태로 저장된다. 
        for(int i=0; i<s.length(); i++) {
            set.add(s.charAt(i));
        }
        return set;
    }

    public String removeDuplicateLetters(String s) {
        //정렬된 문자열 집합 순회 
        for(char c : toSortedSet(s)) {
            //해당 문자가 포함된 위치부터 접미사로 지정
            String suffix = s.substring(s.indexOf(c));
            //전체 집합과 접미사 집합이 일치하면 해당 문자 정답에 추가하고 재귀 호출 진행
            if(toSortedSet(s).equals(toSortedSet(suffix))) {
                return c + removeDuplicateLetters(suffix.replace(String.valueOf(c),""));
            }
        }
        return "";
    }
}

65밀리초 

 

 

풀이 2) 스택을 이용한 문자 제거 

 

- 세 종류의 변수 선언

//문자 개수를 계산해서 담아둘 변수 선언
Map<Character, Integer> counter = new HashMap<>();
//이미 처리한 문자 여부를 확인하기 위한 변수 선언
Map<Character,Boolean> seen = new HashMap<>();
//문제 풀이에 사용할 스택 선언 
Deque<Character> stack = new ArrayDequ

 

- 입력 문자열을 문자 단위로 처리하면서 스택 변수 stack에는 다음과 같이 앞에서부터 문자를 차례대로 쌓아나가고, seen 변수에는 처리한 걸로 선언하면서 반복 

stack.push(c);
seen.put(c,true);

 

- 만약 스택에 있는 문자가 현재 문자보다 더 뒤에 붙여야 할 문자이고 아직 처리해야 할 문자가 남아있다면(카운터가 0이상이라면), 다음과 같이 스택에 쌓아둔 걸 꺼내서 없앤다. 

//스택에 있는 문자가 현재 문자보다 더 뒤에 붙여야 할 문자라면 스택에서 제거하고
//처리하지 않은 걸로 표시 
while(!stack.isEmpty()&&stack.peek()>c&&counter.get(stack.peek())>0)
    seen.put(stack.pop(),false);

 

- 이 문제의 입력값 dbacdcbc에서 만약 세번째로 a 문자를 처리하는 중이라면 이전에 이미 스택에 들어있던 d와 b는 제거되고 a가 새롭게 삽입된다. 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자 :박상길 <책만>

- 카운터가 0 이상인 d와 b는 뒤에 다시 붙일 문자가 남아 있기 때문에 이처럼 스택에서 제거가 가능하다 

 

- 또한 이미 처리한 문자는 아무런 처리도 하지 않고 다음과 같이 바로 건너뛴다. 

//이미 처리한 문자는 건너뛴다. 
if(seen.get(c)!=null&&seen.get(c) == true)
continue;

 

- 마지막으로 스택 변수 stack에 담긴 문자를 큐 순서대로 추출했다. 

- StringBuilder를 이용해 구성한 다음, toString()을 이용해 다음과 같이 리턴 

 //스택에 있는 문자를 큐 순서대로 추출하여 리턴
 StringBuilder sb = new StringBuilder();
 while(!stack.isEmpty())
   sb.append(stack.pollLast());
 return sb.toString();

 

 

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {

      //문자 개수를 계산해서 담아둘 변수 선언
      Map<Character, Integer> counter = new HashMap<>();
      //이미 처리한 문자 여부를 확인하기 위한 변수 선언
      Map<Character,Boolean> seen = new HashMap<>();
      //문제 풀이에 사용할 스택 선언
      Deque<Character> stack = new ArrayDeque<>();

      //문자별 개수 계산
      for(char c : s.toCharArray())
        counter.put(c,counter.get(c)==null?1:counter.get(c)+1);

      for(char c: s.toCharArray()) {
        //현재 처리하는 문자는 카운터에서 -1 처리 
        counter.put(c,counter.get(c)-1);
        
        //이미 처리한 문자는 건너뛴다. 
        if(seen.get(c)!=null&&seen.get(c) == true)
            continue;
        
        //스택에 있는 문자가 현재 문자보다 더 뒤에 붙여야 할 문자라면 스택에서 제거하고
        //처리하지 않은 걸로 표시 
        while(!stack.isEmpty()&&stack.peek()>c&&counter.get(stack.peek())>0)
            seen.put(stack.pop(),false);
        
        //현재 문자를 스택에 삽입
        stack.push(c);

        //현재 문자를 처리한 걸로 처리 
        seen.put(c,true);
      }

      //스택에 있는 문자를 큐 순서대로 추출하여 리턴
      StringBuilder sb = new StringBuilder();
      while(!stack.isEmpty())
        sb.append(stack.pollLast());
      return sb.toString();
    }
}

4밀리초