Level 2 짝지어 제거하기

programmers.co.kr/learn/courses/30/lessons/12973?language=python3

코딩테스트 연습 - 짝지어 제거하기

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

def solution(s):
    stack = []
    if len(s) % 2 != 0 or len(s) == 0: return 0
    for c in s:
        if len(stack) == 0: stack.append(c)
        else:
            if stack[-1] == c:
                stack.pop()
            else: stack.append(c)
    if len(stack) == 0: return 1
    else: return 0

 

---

풀이 과정

풀이 시간  31분

1. 문자열의 길이 체크

if len(s) % 2 != 0 or len(s) == 0: return 0

 문자열의 길이가 홀수인 경우에는 짝지어 제거하더라도 문자열이 남으므로 바로 0을 리턴한다.

또는 문자열이 0인 경우에도 제거할 문자열이 없으므로 0을 리턴해준다.

 

2. Stack 활용하기

 이 문제의 제한사항을 보면 문자열은 모두 소문자로 이루어져 있으며, 길이는 1,000,000이하의 자연수라고 나와있다.

따라서 문자열의 길이가 최대 1,000,000이라는 점을 고려해서 효율성을 따져주어야 문제를 해결할 수 있다.

스택을 활용하면 문자열의 길이만큼만 탐색하여 결과를 얻을 수 있다.

    for c in s:
        if len(stack) == 0: stack.append(c)
        else:
            if stack[-1] == c:
                stack.pop()
            else: stack.append(c)
    if len(stack) == 0: return 1
    else: return 0

1) for문을 활용해 문자열의 길이만큼 반복하여 짝지어 제거하기

1. stack이 비어있는 경우, c를 push 해준다.
2. stack의 top과 c가 같은 경우, top을 pop 해준다.(c 또한 push 해주지 않음으로써 짝지어 제거하기가 수행된다.)
3. stack의 top과 c가 다른 경우, c를 push 해준다.

2) 결과값 도출

1. 최종적으로 stack에 담긴 문자의 개수가 0인 경우, 문자열이 모두 짝지어 제거할 수 있었음을 의미하므로 return 1
2. 0이 아닌 경우, 모두 제거되지 않았음을 의미하므로 return 0

 

---

오답 노트

틀린 코드

def delete_pair(s):
    for i in range(len(s)-2):
        if s[i] == s[i+1]:
            s.pop(i)
            s.pop(i+1)
            if len(s) > 0: delete_pair(s)
            return 1
    return 0
    
def solution(s):
    answer = 1
    if len(s) == 0 or len(s) % 2 != 0: return 0
    answer *= delete_pair(list(s))
    return answer

1. 문자열 s의 길이가 0이거나 홀수인 경우, return 0

2. 문자열 s를 리스트로 바꿔주고 delete_pair함수 실행

1. 짝지어 제거할 수 있는 경우, 두 요소를 pop() 해준다.
2. 리스트 s에 문자열이 남아있는 경우, 재귀함수 호출하고 return 1
3. 리스트 s에 문자열이 없는 경우, 문자열이 모두 짝지어 제거되었음을 의미하므로 return 1
4. 제거할 문자열이 없는 경우, return 0

3. delete_pair의 반환 값을 곱한 결과를 return 해준다.

 

 

결과

 문제에서 주어진 테스트케이스는 통과했지만, 제출하는 과정에서 런타임 에러와 시간 초과가 발생했다.

 

내가 푼 방법은 문자열을 담은 리스트에서 연속으로 중복된 두 문자를 제거할 때마다 다시 첫번째 요소부터 탐색하게 된다.

따라서 문제에서 주어진 제한사항에서 문자열의 길이가 1,000,000라면 수도 없이 많은 반복이 일어날 것이다.

최종 코드처럼 스택의 구조를 활용하면 전체 탐색은 문자열의 길이만큼만 이뤄지므로 시간이 절약된다.

 

 

---

참고

• 2021/01/11 - [C++] - [STL] Stack

[STL] Stack