[programmers lv1. python] 서울에서 김서방 찾기 (초..간단하게 풀기)

 

프로그래머스

 

학습을 시작하는 매일 아침마다 정신도 차리고 알고리즘 감도 유지할 겸 프로그래머스의 lv 1 문제들을 풀고 있는데, 오늘 푼 문제가 어이없다시피 간단하게 풀 수 있는 방법이 있어 공유하고 싶어 포스팅을 한다.

---

 

먼저 알고리즘 문제를 푸는 필자의 루틴은 ㅡ

1. 일단 푼다. (어렵거나 복잡하면 수도 코드를 사용하거나 그림을 그림)
2. 풀어서 맞추면 그 코드를 좀 더 간단하게 풀거나 클린 코드로 개선할 수 있는지 찾아본다.
3. 남은 어떻게 풀었나 '다른 사람의 코드' 섹션도 참고해본다. ('가끔 이렇게도 풀 수 있다고 ..?' 거나 '이 사람 미친거같은데 ..' 하는 경우가 왕왕 나온다)
4. 다른 풀이의 방법을 찾았다면 시간 복잡도나 가독성 등을 비교해 보고 더 좋은 코드로 개선한다.

이렇게 진행하는 편이다. 오늘 문제는 매우 쉬운편이라 간단하게 풀었다. 

 

<1차 풀이> 👉 정답

def solution(seoul):
    for i in range(len(seoul)):
        if seoul[i] == "Kim":
            return "김서방은 " + str(i) + "에 있다"

for문으로 배열 seoul을 순회하면서 Kim을 찾으면 바로 return 하는 식! 

 

시간 복잡도

리스트 seoul의 길이만큼 반복하는 for문이 있기 때문에(최악의 경우 리스트의 모든 요소를 탐색하게 됨) 시간 복잡도는 O(N)이 된다. 

즉, 리스트 seoul의 길이에 따라 시간 복잡도가 선형적으로 증가하게 된다.

---

그러다 '다른 사람의 풀이'를 들어가봤는데 ..

? ..

ㅇ ㅏ맞다. . index라는 함수가 있었지. 있는 함수 안갖다쓰고 for문부터 냅다 써버린 ^-^ ..

▪️index 함수
index 함수는 리스트나 문자열에서 특정 값을 찾아 그 값이 처음으로 나타나는 위치(인덱스)를 반환한다.
- 사용법: list.index(value)

위의 코드를 조금만 변형해서 다시 답을 개선해봤다.

 

<2차 풀이> 👉 정답

def solution(seoul):
    return f"김서방은 {seoul.index('Kim')}에 있다"

위 코드 중  seoul.index('Kim')은 리스트 seoul에서 'Kim'이라는 값이 처음 나타나는 위치를 반환한다. 1차 풀이에서 for문으로 푼 코드보다 훨-씬 간결해졌고 가독성도 좋다 ..

 

시간 복잡도

이 코드도 1차 풀이처럼 리스트의 길이에 비례해 수행 시간이 증가하는 O(N)의 선형 시간 복잡도를 가져서 크게 차이는 나지 않지만, 아주아주 미세하게 빠른 것 같다.

 

 

<정리>

사실 두 가지 코드 둘 다 시간복잡도 면에서는 차이가 없지만, 2번째 풀이가 코드의 길이가 월등히 짧아 직관적이고 가독성도 좋아서 2번째 풀이를 사용하지 않을 수 없다. index 함수 까먹지않겠어 ..