백준(Baekjoon Online Judge) - 1541번(잃어버린 괄호) 문제 풀이

1. 문제

2. 입출력 예시

3. 문제 풀이

이 문제 역시 간단히 해결할 수 있었다.

• 주어진 식의 합(total)을 0으로 초기화한다.
• 문자열로 구성된 식을 입력받으며, 이 때 +를 기준으로 나눈 후 이를 리스트(values)에 저장한다.
• 반복문을 통해 +를 기준으로 나눈 리스트의 요소를 다시 - 기준으로 나누어주며, 이때 나눈 요소들은 정수형(int)으로 변환 후 이들의 합을 리스트에 저장한다.
• 리스트의 길이만큼 역순으로 반복하며, 인덱스가 0일 경우 식의 합에 해당 해당 요소를 더하고, 그 외에는 식의 합에서 해당 요소만큼 빼준다. 인덱스가 0인 경우는 가장 첫 번째에 위치한 숫자이므로, 이를 식의 합에 더해주는 것이다. 효율성을 위하여 인덱스에 해당하는 요소를 호출할 때 pop을 사용한다.
• 반복이 종료되면 식의 합을 출력한다.

이를 코드로 나타내면 다음과 같다.

values = [sum([int(x) for x in s.split("+")]) for s in list(input().split("-"))]

total = 0

for i in range(len(values)-1, -1, -1):
    print(i)
    if not i:
        total += values.pop(i)
    else:
        total -= values.pop(i)

print(total)

코드는 총 2회 제출하였으며, 이들의 차이는 pop 적용 여부만 다르다. 이들 모두 메모리 28,776 KB가 소요되었다. 그러나 pop을 적용하였을 때 시간은 64 ms, 단순 호출만 하였을 때에는 76 ms가 소요되었으며, pop을 적용하였을 때 시간이 조금 더 단축되는 것을 확인할 수 있었다.

참고자료

• 백준알고리즘 문제 - 1541번 잃어버린 괄호