[알고리즘] 소프티어 Lv2. 8단 변속기 (Python)

Softeer 알고리즘 문제 풀이

문제: Lv2. 8단 변속기

https://softeer.ai/practice/6283

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

---

풀이 1

리스트의 모든 숫자가 1부터 8까지 계속 증가할 때마다 result 딕셔너리의 ascending 값을 증가시켜주었다.

그리고나서 이 딕셔너리 값이 8인지에 따라 최종값을 출력하였다.

import sys
input = sys.stdin.readline

nums = [int(i) for i in input().split()]

result = {"ascending": 0, "descending": 0}
for i in range(8):
    if nums[i] == i+1:
        result["ascending"] += 1
    elif nums[i] == 8-i:
        result["descending"] += 1

if result["ascending"] == 8:
    print("ascending")
elif result["descending"] == 8:
    print("descending")
else:
    print("mixed")

🚀 시간 복잡도

• for i in range(8): → O(8) = O(1)
• if nums[i] == i+1: → 8번 반복 (O(1))
• if result["ascending"] == 8: → O(1) (딕셔너리 조회)

➡️ 전체 시간 복잡도: O(1) (항상 8번 반복하므로 상수 시간)

⚡ 속도가 더 빠른 이유

• 루프를 한 번만 수행하면서 두 조건을 동시에 확인하기 때문.
• 딕셔너리를 사용해 값을 카운트하는 방식이기 때문에 메모리를 약간 더 사용하지만, 속도에는 거의 영향이 없음.

---

풀이2

위처럼 풀이한 후 구글링 해보니, 이 방법으로 더 쉽게 풀린다는 걸 알게되었다.
사실 처음에 이 생각도 했었는데 이렇게 풀면 안 될 줄 알았다 ㅋㅎㅋㅎ

그런데 속도는 이전 풀이가 (조금) 더 빠르다.

import sys
input = sys.stdin.readline

nums = [int(i) for i in input().split()]

ascending = list(range(1, 9))
descending = ascending[::-1]

if nums == ascending:
    print("ascending")
elif nums == descending:
    print("descending")
else:
    print("mixed")

🚀 시간 복잡도

• ascending = list(range(1, 9)) → O(8) = O(1)
• descending = ascending[::-1] → O(8) = O(1)
• if nums == ascending: → O(8) = O(1) (리스트 비교)
• elif nums == descending: → O(8) = O(1) (리스트 비교)

➡️ 전체 시간 복잡도: O(1) (여전히 상수 시간이지만 리스트 비교가 2번 일어남)

⏳ 속도가 느린 이유

• 리스트 비교 (nums == ascending, nums == descending)는 두 리스트의 모든 요소를 순차적으로 비교해야 함.
• 즉, 최악의 경우 두 번의 비교 연산이 필요해서 실제 연산량이 첫 번째 코드보다 약간 많아질 수 있음.

메모리 측면

• ascending과 descending 두 개의 리스트를 추가로 생성해야 함

---

즉, 두 풀이의 속도 차이가 나는 이유는 리스트 비교 방식이 다르기 때문이다.

내가 혼자 생각해서 푼 풀이가 더 빨라서 뿌듯하다😎