[Python3] 프로그래머스 - k번째 수, 완주하지 못한 선수(딕셔너리, 슬라이싱)

k번째 수 문제요약

정수 배열 array와, 명령어 배열 commands가 주어진다.
각 command 는 [i, j, k] 형태

1. array의 i번째부터 j번째까지의 숫자들을 자른다
2. 잘라낸 배열을 정렬한다
3. 정렬된 배열에서 k번째 숫자를 꺼낸다

모든 command에 대해 k번째 수를 구해 리스트로 반환하면 끝!

 

핵심개념

array[start : end] 인덱스 슬라이싱

 

array를 m번째에서 n번째로 부분추출하는 코드를 0-based를 고려하여 array[m-1:n-1]로 코드를 짰는데 Error

-> m-1:n으로 해결

 

***Python 슬라이싱***에서

array[start : end]에서 end 인덱스를 포함하지 않는다.
즉, start ≤ 인덱스 < end 만 포함되기 때문이었음

def solution(array, commands):
    answer = []
    for i in range(len(commands)):
        m = commands[i][0]
        n = commands[i][1]
        k=commands[i][2]
        new_array=array[m-1:n]
        new_array.sort()
        answer.append(new_array[k-1])
    return answer

---

완주하지 못한 선수 문제요약

• participant: 경주 참가자 이름 리스트
• completion: 완주자 이름 리스트
• 동명이인 가능
• 참가자 중 1명만 완주하지 못함
• 완주하지 못한 선수의 이름 한 명을 반환

def solution(participant, completion):
    answer = ''
    for i in range(len(completion)):
        for j in range(len(participant)):
            if completion[i]==participant[j]:
                participant.remove(participant[j])
                break;
    answer=participant[0]
    return answer

*내가 짠 코드*

=> 정확성 테스트 : 통과, 효율성 테스트 : 실패(시간 초과)

왜?

🔹 동작 방식

• completion 리스트 하나씩 꺼내서
• participant 전체를 순회하며 같은 이름을 찾고 제거(remove)
• 결국 participant에 남은 한 명 반환

---

🔹 시간 복잡도 분석

1. for i in range(len(completion)) → 약 n번 반복
2. 내부 for j in range(len(participant)) → 최악의 경우 n번 반복
3. participant.remove() → 리스트에서 요소 제거 O(n)

➡ 따라서 전체 시간 복잡도:

O(n)∗O(n)∗O(n)=O(n3)O(n) * O(n) * O(n) = O(n^3)O(n)∗O(n)∗O(n)=O(n3)

• n이 커지면 (예: 100,000명) 절대 시간 안에 안 끝남 → 시간초과 발생

따라서, **딕셔너리(key: 이름, value: 카운트)** 풀이구조!

딕셔너리 문법 : {}를 통해 이름별 참가횟수를 세는 방법으로!

people={}

이렇게 사용하겠다고 선언 및 초기화를 하면,

people만 쓰면 key값만 반환!

people[x] 쓰면 value값 반환!

people.items() 쓰면 둘 다 반환!

*수정 후 코드*

O(n) 효율적 탐색

def solution(participant, completion):
    answer = ''
    people = {}
    for p in participant:
        people[p]=people.get(p,0)+1
    for c in completion:
        people[c]-=1
    for name,count in people.items():
        if count !=0:
            answer=name
    return answer

 

• people.get("John", 0)
  • "John"이 딕셔너리에 있는지 확인 → 없음
  • 따라서 default 값 0 반환
• people["John"] = 0 + 1
  • 이제 딕셔너리에 "John" 키가 생기고 값은 1이 됨

people.get(p, 0) + 1	p라는 이름이 있으면 값 +1, 없으면 0+1
for name, cnt in people.items():	딕셔너리 key와 value를 동시에 가져옴
if count != 0: return name	남은 카운트가 0이 아닌 사람 → 완주하지 못한 선수 반환