[소프티어 softeer] [한양대 HCPC 2023] X marks the Spot (Lv.2) - 파이썬(Python)

문제

https://softeer.ai/practice/7703

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

오답 풀이

처음에 문자열을 누적하여 추가해주었더니 테스트케이스 5번과 8번 시간초과가 났습니다.

# 오답코드
import sys

input = sys.stdin.readline

n = int(input())
answer = ''  # 문자열 누적
for i in range(n):
    s, t = input().split()
    s = s.upper()
    t = t.upper()

    answer += t[s.find('X')]  # 문자열을 매번 새로 생성

print(answer)

 

위 오답 코드는 문자열 'answer'에 문자를 하나씩 추가할 때마다 새로운 문자열을 생성합니다.

파이썬의 문자열은 불변(immutable)이기 때문에, 새로운 문자열을 만들 때마다 기존 문자열의 내용을 복사해야 합니다.

이 과정이 반복되면, 특히 반복 횟수가 많을 때 매우 비효율적입니다.

이러한 이유로 시간초과가 났던 것입니다.

 

시간 복잡도

• 첫 번째 반복: O(1) (answer가 짧음)
• 두 번째 반복: O(2)
• 세 번째 반복: O(3)
• ...
• n번째 반복: O(n)

 

 

정답 풀이

import sys

input = sys.stdin.readline

n = int(input())
answer = []  # 리스트에 문자열 누적
for i in range(n):
    s, t = input().split()
    s = s.upper()
    t = t.upper()

    answer.append(t[s.find('X')])  # 리스트에 문자를 추가

print(''.join(answer))  # 최종적으로 한 번에 문자열 생성

 

위 정답 코드는 리스트 'answer'에 문자를 하나씩 추가합니다.

리스트는 가변(mutable) 객체이기 때문에, 새로운 항목을 추가할 때 기존 리스트의 내용을 복사하지 않습니다.

리스트에 문자를 모두 추가한 후, join 메서드를 사용하여 최종 문자열을 한 번에 생성합니다.

 

시간 복잡도

for 루프의 전체 시간 복잡도는 O(n)이며, 마지막에 ''.join(answer)는 리스트의 모든 문자를 하나의 문자열로 합치는 연산으로 O(n) 시간이 소요됩니다.

• O(n) (반복) + O(n) (join 연산)

 

정리하면

• 오답 코드에서 문자열 연결 연산이 반복적으로 일어나면서 각 반복마다 answer가 점점 길어지기 때문에 시간복잡도가 O(N^2)으로 증가합니다.
• 정답 코드에서는 리스트에 문자를 추가하는 연산이 평균 O(1) 시간으로 효율적이며, 마지막에 한 번의 join 연산으로 전체 문자열을 생성하므로 시간 복잡도는 O(n)입니다.
• 따라서 정답 코드가 훨씬 효율적이고, 대규모 입력에서도 시간 초과 없이 동작할 수 있습니다.