99클럽 코테 스터디 7일차 TIL ✒️ 좋은 단어 (스택 활용)

 

✅ 오늘의 학습 키워드

• Stack 활용하기
• 추가, 삭제, 조회 메서드별 비교

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

• 같은 문자끼리 짝 지어서 교차하지 않는 문자열의 개수를 반환한다
• 단어의 길이는 2와 100,000사이이다

이 문제를 보고 우선 문자를 짝 짓는 방법에 대해서 생각해봤다. 짝을 지을 때 교차하지 않으려면 2가지 방법이 존재했다. 첫번째는 왼쪽부터 오른쪽 방향으로 순차적으로 같은 문자가 나오는 패턴이었다. ( a a b b a a ) 두번째는 중간에 위치한 문자부터 양 끝으로 연결되는 패턴이었다. ( a b a b b a b a ) 

---

✨ 오늘의 회고

📌내가 적은 답안📌

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    br.readLine();
    String s;
    int cnt = 0;

    while ((s = br.readLine()) != null) {
      // 첫 문자와 두 번째 문자가 같을 경우
      // 스택에서 바로 제거
      // 첫 문자와 두 번째 문자가 다를 경우
      // a b a -> 교차로 나오면 안됨
      // 스택이 empty면 cnt++
      Stack<Character> stack = new Stack<>();

      for (char c : s.toCharArray()) {
        if (stack.isEmpty()) {
          stack.push(c);
        } else {
          if (stack.peek() == c) {
            stack.pop();
          } else {
            stack.push(c);
          }
        }
      }

      if (stack.isEmpty()) cnt++;
    }

    System.out.println(cnt);
  }
}

 

위처럼 문제 분석을 하고 코딩에 들어갔다. 처음에는 2가지 방법을 이용해서 if문을 두 개를 써서 문제를 풀려고 했다. 양 끝에서 문자가 연결되는 경우는 양방향 큐 Doubld Ended Queue를 사용해서 양쪽에서 문자를 비교해서 일치와 불일치를 찾으려고 했다. 그리고 다시 왼쪽부터 순차적으로 찾으려고 했다. 

 

하지만 이 방법에는 문제가 있었다. A A B A A B 처럼 함께 쓰이면 확인할 수 없었다.🤔

 

그래서 스택을 두 개를 선언해서 A와 B를 따로따로 저장하고 들어오는 순서에 따라서 알 수 없을까 하다가 A B A  또는 B A B처럼 교차 문자가 되면 탈락한다는 것을 찾았다. 그래서 이전 문자와 현재 문자가 같은 경우와 다른 경우로 조건식을 세우고 같을 경우 스택에서 제거하도록 했다. 그리고 스택이 비어있을 경우 변수 cnt를 증가하도록 했다.

 

같은 추가/삭제/조회 메서드라도 처리 방법이 다르다는 것을 배워서 정리해보았다.

 

✨ 자료구조가 비었을 때 예외 처리 메서드

Stack	Queue
push	add (IllegalStateException)
pop (EmptyStackException)	remove (NoSuchElementException)
peek (EmptyStackException)	element (NoSuchElementException)

 

✨false 또는 null 반환 메서드

Stack	Queue
	offer
	poll
	peek