달리기 경주 문제 - 깊게 보기
달리기 경주 문제 - 깊게 보기 — #개발자의 도구들 /#프로그래머스 #코딩테스트 사용된 언어: 코틀린, 혹은 파이썬 순서: 로직, 코드 구현, ...
#개발자의 도구들 /#프로그래머스 #코딩테스트
- 사용된 언어: 코틀린, 혹은 파이썬
- 순서: 로직, 코드 구현, 코드 분석
깊게 풀어서 부족한 부분 매꾸기
Programmers (Lv1. 달리기 경주) 48&
[코딩테스트 연습 - 달리기 경주
알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.
school.programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/178871)
⚠️ 문제의 제약 조건: 1 <= n <= 1,000,000, 5 <= m <= 50,000
n값이 너무 커서 n log n 내에 풀어야 함
- 이 문제는 callings(<= 1,000,000)을 순회하면서 players(<= 50,000)을 다시 순회하기에는 너무 많은 시간이 걸린다.
- O(n)으로 풀기 위해 미리 players의 순위를 구해둬야 할 필요가 있다.
- 👉 여기까지 오면 거의 다 푼 것
첫 번째 접금법
우선 첫번째로 O(N \* M)이 불가하다는 것을 알았다. 그렇기 때문에 순위를 매번 초기화 하는 것이 불가능하다고 생각했다. 순위 변동 값을 map으로 저장하고 마지막에 한번에 순위를 결정짓는 알고리즘을 생각했다.
["mumu", "soe", "poe", "kai", "mine"] 해당 배열의 초기값을 설정하고 변화를 추적하기 위한 map 추가
original = {"mumu": 0, "soe": 1, "poe": 2, "kai": 3, "mine": 4}
changed = {"mumu": [adjusted_idx, last_call_idx(0 df)], "soe": [...], ... }
callings를 다 돌면, adjusted_idx 값에 따라 순위가 정해진다.
callings = ["kai", "kai", "mine", "mine", "mine"]
changed = {...,"kai": [1, 1(callings_last_idx)], "mine": [1, 4], "soe": [1, 0] ...}
이때 changed내에 동일 순서가 3개나 생긴다.
👉 순서 결정 changed idx
👉 동일 값인 경우 last_call_idx로 순서 판단 ( 절대 같을 수 없음 )
위 순서로 순서를 나열하면 "mine", "kai", "soe"로 정렬됨
⚠️⚠️⚠️⚠️ ❌❌❌
이렇게 매번 changed에 순서가 같은 key가 있는지 확인하고, 순서를 조정한다면 많은 시간 복잡도가 소모
changed의 크기가 M이라서, M * M * (M - k) (k = key값이 동일하지 않는 수)의 시간 복잡도로
훨씬 오래걸림
두 번째 접근방법
순서 변경을 위해서 Players를 조회 해야하는 것이 문제다. 여기서 탐색 시간이 많이 발생하기 때문이다. 그렇다면, 각 player가 before, after값을 가지고 있으면 어떨까? 그럼 직접 players를 탐색하지 않고도, 이전, 이후 선수의 순위를 바로 확인할 수 있다.
before, after를 이전, 이후 선수의 이름으로 저장하고 map으로 idx를 바로 조정하면 call이 되는 순간 바로 순서 변경이 가능하다. 이는 마치 더블링크드 리스트 내에서의 swap과 같은 로직이다.
original = {players[0]: [0, None, players[1]]}
for i in range(1, len(players) - 1):
original[players[i]] = [i, players[i - 1], players[i + 1]]
original[players[len(players) - 1]] = [len(players) - 1, players[-2], None]
# switch
for current in callings:
current_idx, before, after = original[current].copy() # [idx, before_str, after_str]
if before == None:
continue # skip first
# change before and now
bb = original[before][1]# before before
original[current][0] -= 1
original[before][0] += 1
original[current][2] = before
original[current][1] = bb
original[before][1] = current
original[before][2] = after
if bb != None:
original[bb][2] = current
# change after and now
if after != None:
original[after][1] = before
"""
filtered = [[k, original[k][0]] for k in original]
filtered.sort(key = lambda x : x[1])
answer = [infos[0] for infos in filtered]
"""
answer = ["" for _ in range(len(players))]
for name, (idx, _, _) in original.items():
answer[idx] = name
return answer
- 구현에 애를 먹었다.
- 예외 처리를 잘해주자.
- 예외 빼먹지 말기
- bb -> after = current
- b = None 이면 skip
- after != None이면 after -> berfore = before
- 정답이다.
Hash Map으로 문제풀기
사실 이렇게 까지 복잡하게 할 필요는 없었다. HashMap 두 개로 쉽게 순서 변경이 가능하다.
👉 Hash Map을 사용하는 이유는 결국 called 된 name이 어디에 위치하는지 알기 위함이다.
{name: idx}
{idx: name}
call 될때 마다 name으로 idx를 조회하고, idx - 1의 위치의 name과 순서를 변경해주면 된다
def solution(players, callings):
answer = []
# original = [now idx, before, next]
ntoi = {key: idx for idx, key in enumerate(players)}
iton = {idx: key for idx, key in enumerate(players)}
for name in callings:
p = ntoi[name]
if p == 0:
continue
b_i = p - 1
# adjust rank(idx)
ntoi[name] -= 1
before = iton[p - 1]
ntoi[before] += 1
# adjust position
iton[b_i] = name
iton[p] = before
answer = ["" for _ in range(len(players))]
for n, i in ntoi.items():
answer[i] = n
return answer
- Map을 왜 사용해야하는지 정확하게 알면 자유자재로 응용할 수 있다
- list의 특정 값을 빠르게 찾아야할 때
- list 특정 값 이전 혹은 이후 idx 값을 빠르게 찾아야 할 때
sort skip
filtered = [[k, original[k][0]] for k in original]
filtered.sort(key = lambda x : x[1])
배열내에 특정 값으로 정렬하기 위해 lambda를 사용했었다.
answer = ["" for _ in range(len(players))]
for name, (idx, _, _) in original.items():
answer[idx] = name
idx 값을 포함하고 있다면 이런식으로 바로 넣어주자.