✅ stack

문제

링크

풀이

1. 문제 접근

https://scarlettb.tistory.com/18

괄호 쌍을 찾는 문제와 같은 문제이다.

2. 자료구조 선택과 그 이유

들어온 반대 방향으로 같은 문자쌍을 찾는 문제이므로 stack 사용

3. 문제 해결 로직 (풀이법)

문자를 입력 받을때마다 stack.top과 비교하여 같은 문자이면 pop해주고
다른 문자면 push 해준다.
코드가 끝나고 stack에 남는게 있으면 좋은 단어가 아니다.

의사코드

cin >> N

for(1~N){
	cin >> str
    for(int i : 0 ~ str.length-1){
    	if(stack.empty) stack.push(str[i])
        else{
        	if(stack.top == str[i]) stack.pop
            else stack.push(str[i])
        }
    }
    
    if(stack.empty) cnt++
}

cout << cnt

4. 시간 복잡도 분석

n : 단어의 길이
단어는 최대 100개 주어지므로 O(100n)이지만 100은 생략 가능이므로
O(n)

(처음에 O(N)이라고 적었었는데 문제에서 N을 단어의 수로 사용했으므로 새로운 변소로 새로 정의하거나 n은 단어의 길이라고 재정의 해주는게 정확하다고 하셨음)

5. 문제에서 중요한 부분

단어 위로 아치형 곡선을 그어 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다.
라는 설명이 있는데 여기서 아치형 곡선이 뭔지 이해가 안가 이해가 잘 안되었음 ㅎ..
이외에는 괄호쌍 찾는 문제와 동일한 간단한 문제였음