백준 12605 : 단어순서 뒤집기 (print 성능)

 

더 많은 풀이

Algorithms & Data structures

📐 문제 요약

---

입력한 문장을 띄어쓰기 기준으로 쪼갠 후 반대의 순서대로 출력하는 문제.

• 입력

첫째줄 - 테스트 케이스 수

n - 뒤집을 문장 문장

• 출력

반대 순서로 출력

 

📐 문제 풀이

---

1. 사용 자료구조 및 알고리즘
   • 스택
     • 배열 내 원소를 뒤집기 위해 마지막 원소(last-in)를 먼저 꺼내야한다(last-out)는 생각과 함께 스택을 사용
2. 문제 풀이

• 검증되지 않은 가정

pop한 원소를 담은 **새로운 스택을 생성함으로써 더 큰 메모리를 차지할 것(X)**이라 생각 → 방법 2대로, pop한 원소를 개행문자 제거 후 그때 그때 프린트하여 메모리를 절약할 수 있을 것이라 생각 → 하지만 방법 1과 메모리 사용량은 동일했고, 시간이 오히려 print구문을 많이 사용했을 때 더 소요됨을 확인.

# 메모리 113112KB
# 시간 112ms

# 방법 1. 
import sys

input = sys.stdin.readline

N = int(input())
for i in range(1, N+1):
    char_lst = input().rstrip().split()
    print(f"Case #{i}:", end= " ")
    while char_lst:
        print(char_lst.pop(), end=" ") # 한번에 프린트 or 여러번 프린트!

# 메모리 113112KB
# 시간 108ms

# 방법 2. **채택 두둥**
import sys
input = sys.stdin.readline

N = int(input())
for i in range(1, N+1):
    char_lst = input().rstrip().split()
    stk = [] 
    while char_lst:
        stk.append(char_lst.pop())
    print(f"Case #{i}:", " ".join(stk)) 

 

• 이전 값을 참조한 새로운 스택 생성

아래 예제를 만들어보았습니다. 이미 생성된 값(변수,스택,배열)을 참조하여 새로운 값을 생성하는 경우, 기존 생성된 값의 메모리 주소가 담기게 됩니다.

따라서, 해당 문제처럼 이전 스택값을 참조해 역순의 새 스택을 생성하는 경우에 추가적인 메모리 소모가 발생하지 않습니다.

stk1 = [1,2,3,4]
stk1_cp = stk1.copy()

stk2 = []
while stk1:
    stk2.append(stk1.pop())

for x,y in zip(stk1_cp, reversed(stk2)):
    print("메모리 주소 동일" if id(x) == id(y) else "상이") # id(변수): 메모리 주소 확인

• 배운 점

검증없는 가정을 기반으로 한 생각은 위험하다. 많은 문제들을 연습해보며 가정을 검증해보자.