.codility(DisappearingPairs)

https://app.codility.com/programmers/trainings/4/disappearing_pairs/

 

1. 2022.04.15 시도

소요시간: 21분

import java.util.*;

class Solution {
    public String solution(String S) {
        Stack<Integer> prev = new Stack<>();
        
        for (int i=0; i<S.length(); i++) {
            if (prev.size() >0 && (S.charAt(prev.peek()) == S.charAt(i))) {
                prev.pop();
                continue;
            }

            prev.push(i);            
        }

        String ret ="";
        while(!prev.isEmpty()) {
            ret = S.charAt(prev.pop()) + ret;
        }

        return ret;
    }
}

풀이 접근 과정

같은 문자 2개의 블럭은 제거될 수 있는 문제이기 때문에 stack을 사용해서 peek()와 다음 문자가 같은지를 파악해서 글자를 지워나갈 수 있다.

다 지워졌다면 그 이후남은 문자를 연결해서 리턴한다.

 

느낀점

• stack을 생각하는 순간 문제가 easy로 변한다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형