내일은 알고리즘

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

문제에서 요구한 그대로 구현하면 쉽게 풀릴 것 같지만, 입력 문자열의 길이가 100만이기 때문에 좀 더 효율인 방법이 필요합니다. 

예를 들어 입력이 10일때 요구한 그대로 문자열을 비교한다면 알파벳이 2개씩 사라지므로 5번의 시행이 필요하고 그 때마다 10, 8, 6, 4, 2 길이의 문자열을 자르고 이어붙여야합니다. 문자열의 길이가 길수록 기하급수적으로 커지겠죠.

Stack, 혹은 List 등의 자료구조를 활용하여 맨 뒤의 알파벳만 비교할 수 있습니다. 이 경우엔 정확히 문자열의 길이만큼만 다루면 됩니다. Python 기준으로 List를 Stack과 유사하게 사용할 수 있으므로 이를 사용해 알파벳을 넣어주고, 만약 맨 뒤의 알파벳(즉 나와 맞닿은 알파벳)이 같다면 지워주는 식으로 풀 수 있습니다.

def solution(s):
    st = []
    
    for c in s:
        if len(st) > 0 and st[-1] == c:
            st.pop()
        else:
            st.append(c)
    
    return 1 if len(st) == 0 else 0

https://school.programmers.co.kr/learn/courses/30/lessons/133502

일주일 공부를 안한 사이에 또 문제가 추가되었다.

열일하는 프로그래머스 화이팅~

기본적인 Stack 응용 문제인것 같은데, 사실 그닥 스택 느낌이 없다. 문제 설명도 뭔가 부족한 느낌... 처음엔 가능한 만큼 햄버거를 계속 만드는줄 알았는데 그런거 없더라.

아무튼, Python엔 Stack이 없기 때문에 List를 하나 만들어 주고, 적절히 탐색해가면서 만들어지는 햄버거의 갯수를 카운팅하면 쉽게 풀린다.

def solution(ingredient):
    answer = 0
    remain = []

    for i in ingredient:
        if i == 1 and len(remain) >= 3 and remain[-1] == 3 and remain[-2] == 2 and remain[-3] == 1:
            for _ in range(3):
                remain.pop()
            answer += 1
        else:
            remain.append(i)

    return answer