1027: 인접한 문자 제거하기 HARD

Link : judge.koreatech.ac.kr/problem.php?id=1027

---

1. 문제

• 다음과 같이 인접한 문자를 모두 제거하는 기능을 구현하세요.
  문자열 S 가 주어질 때,
      1. S[i] == S[i+1] 인 가장 작은 i 를 찾습니다.
      2. S[i] 와 S[i+1] 를 제거합니다.
      3. S[i] == S[i+1] 인 i 가 존재하지 않을 때까지 반복합니다.
  예를 들어,
  입력 문자열 S 가 SIEEILLL 이라면 위의 과정을 통해 아래 순서대로 변하게 됩니다.
  SIEEILL -> SIILL -> SLL -> S
  위의 과정이 완료된 후 남은 문자열을 답으로 출력합니다.

 

---

2. 문제의 조건

• 1 <= T <= 100
• 1 <= len <= 100,000
• 영문 대문자로만 구성 됨.

 

---

3. 문제 접근

• 시간 복잡도
  
  1시간제한 1초에 100개의 테스트에 10만길이로 주어진 문제입니다. O(N^1.14)이내에 풀어야합니다.

 

• 아이디어
  
  1. 같은 문자열이 사라질 때 까지 중복을 제거하자.
  이는 O(N^2)의 시간이 소요되어 시간초과가 날 것 입니다.
  
  2. Stack을 이용하여 중복을 제거하자.
  스택은 O(N)의 시간이 소요되어 이 문제를 풀기에 적합하다고 생각합니다.

 

---

4. 풀이 방법

• 문자열 s를 앞글자부터 넣어줍니다.
• 만약 stack의 size가 1보다 작으면 그냥 데이터를 추가시켜줍니다.
• 이후 들어온 문자와 stack의 맨 마지막 요소를 비교하여 같으면 pop으로 빼주고
  다르면 그냥 추가시킵니다.
  ※ stack의 pop(), pop(-1)은 O(1)이다. 다만 pop(idx)일 경우 O(N)이 소요된다.

 

---

5. 소스코드

• cjw-git.tistory.com/35

 

---

 

cjw.git@gmail.com