Py) 프로그래머스 12973 짝지어 제거하기

https://programmers.co.kr/learn/courses/30/lessons/12973

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

 

1차 시도: 30분

2차 시도: 30분

답 찾아보고 (3차 시도): 3분?

 

0. 입출력

 

1. 김예고리즘

1.1 로직

반복문을 돌려서 인덱스를 비교한다

 -> 문제 풀면서 생각 못한 것:
1. for문을 사용하면 인덱스 때문에 2중 반복문을 사용하게 된다.
2. 큐를 사용하면 뒤로 가버리기 때문에 무한루프임,,

1.2 코드

틀린 코드 (시간 초과)

def solution(s):
    answer = 1
    # arr = copy.deepcopy(s)
    # pre = len(arr)  # 길이 저장

    # 길이변화가 여기에도 적용이 되네..?
    # 얕은 복사가 여기서도 적용되는건가, int로 취급되고 끝나는게 아닌가
    # ... 반복문에서 잘못해서 그런거였음,,

    pre = now = len(s)

    while True:

        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                s = s[:i] + s[i+2:]
                now = len(s)
                break
        if len(s) == 0 or pre == now:
            break
        else:
            now = pre

    if len(s) >= 1:
        answer = 0

    return answer

고쳤는데 또 틀린 코드 (시간초과 22)

def solution(s):
    answer = 1
    pre = now = len(s)
    i = 0

    while i < len(s)-1:
        if s[i] == s[i+1]:
            s = s[:i] + s[i+2:]
            i = 0       # 인덱스 처음으로
            continue
        i += 1

    if len(s) >= 1:
        answer = 0

    return answer

시무룩,,

이후 deque을 써서 큐처럼 해볼까 해서 코딩하다가 문득, 반복을 어느 기준으로 어떻게 멈추지? 하는 생각.

해보다가 정말 이상한 짓이구나를 깨닫고 시간이 없어서 그냥 찾아봄 이걸 찾아보네,, ._.

큐 아니야 제발,,

 

2. Solution

2.1 사용 알고리즘 및 자료구조: 스택

 

2.2 로직

1) 비어있는 stack에 s 원소 하나를 넣고 순서대로 s의 원소와 stack 맨위 원소를 비교한다.
2) stack 맨위 원소가 동일하면 맨위 원소를 제거한다
3) s가 비었을 때 stack에 남아있는게 있다면 짝지어 연결이 안되는 것 -> return 0

 

2.3 코드

def solution(s) :
    stack = []

    for a in s:
        if not stack:   # 비었다면
            stack.append(a)
        elif stack[-1] == a:    # stack의 맨 위가 동일하다면
            stack.pop()
        else:
            stack.append(a)
    if stack:
        return 0
    else: return 1

 

2.4 새롭게 알게 된 것 && 리마인드

*깊은 복사, 얕은 복사

중간에 코드 잘못짜서 왜인지 깊은 복사 얕은 복사를 좀 보게 되었다.

immutable은 얕은 복사(그냥 =)을 사용해도 괜찮지만

mutable(list, array, dictionary)은 깊은 복사를 사용해야 다른 주소를 가리키기 때문에 변화가 반영 안됨

 --> ref - https://blockdmask.tistory.com/576

 

3. 문제 풀면서 알게된 내 문제점

문제를 풀기 전에 생각은 하는데, 자료구조, 알고리즘에 대해 생각을 안하는 것 같다.

내가 공부하고 아는 것 중 뭘 사용해야 효율적으로 풀 수 있을지 생각해야함.

애초에 자료구조와 알고리즘을 배우는 이유가 효율적으로 설계하고 효율적으로 풀기 위함이니까 문제 접근할 때 그거 부터 생각하자