연습장
24. 달리기 경주 본문
players 의 배열의 원소 위치를 바꾸는데
callings 에서 해당 원소가 나올때마다 인덱스를 왼쪽으로 이동 하게된다.
mumu soe poe kai mine
kai -> mumu soe kai poe mine
kai -> mumu kai soe poe mine
mine -> mumu kai soe mine poe
mine -> mumu kai mine soe poe
1. callings 에서 원소를 하나씩 꺼내온다.
2. players 에서 해당 원소의 위치를 찾는다.
3. 왼쪽으로 한칸 땡겨준다.
4. callings 의 모든 원소에 대해서 반복한다.
def solution(players, callings):
answer = []
for call in callings:
print(players.index(call))
return answer
index 함수를 사용하면 다음과 같이 위치를 인덱스로 알려주게 된다.
총 4개로 나눌 수 있다 .
앞순위 변동없음 : mumu soe
추월 당하는 : poe
추월 하는 call : kai
뒷순위 변동없음 : mine
순서대로 다음과 같이 나눌 수 있으며
print(players[:idx-1], [players[idx-1]], [call] ,players[idx+1:])
[players[idx-1]], [call] 의 순서를 바꾸게 되면 순위가 바뀌게 된다.
def solution(players, callings):
answer = []
for call in callings:
idx = players.index(call)
players = players[:idx-1] + [call] + [players[idx-1]] + players[idx+1:]
answer = players
return answer
결과는 시간초과로 실패하였다.
players 의 길이와 callings 의 길이가 매우 길어질 경우 이렇게 되는거 같다.
최대 5만명의 players 가 100만번 순위가 뒤바뀔수 있다는 제한조건인데..
def solution(players, callings):
answer = []
for call in callings:
idx = players.index(call)
# players = players[:idx-1] + [call] + [players[idx-1]] + players[idx+1:]
# answer = players
return answer
2줄을 주석처리하고 진행해도 시간 초과가 났다.
def solution(players, callings):
answer = []
for call in callings:
len(call)+1
return answer
for 문자체에 대해서는 시간초과가 안나는걸로 보아 callings 에 대한 for 문까지는 진행해도 될거같다.
index 함수에서 시간초과가 난것으로 생각이되며 다른 방법을 찾아야겠다.
슬라이싱이 아닌 바로 원소의 위치를 교환하는 방식으로 변경하였다.
조금 더 빨라지긴 했으나 아직 해결되지 않는다.
def solution(players, callings):
for call in callings:
idx = players.index(call)
players[idx-1], players[idx] = players[idx], players[idx-1]
return players
만약 dic 으로 푼다면
def solution(players, callings):
dic = {}
j = 0
for i in players:
dic[i] = j
j += 1
print(dic)
return players
callings 에서 순위가 바뀌는 target_player 의 현재 rank 를 얻고 그 순위보다 1작은 순위의 pre_player 를 얻어야 된다.
즉 target 이 추월하려는 사람의 정보는 그 사람보다 순위가 높다는 정보하나밖에 없기 떄문에 이를 활용하기 위해서 dic를 2개 사용하였다.
dic = player : 순위
dic2 = 순위 : player
def solution(players, callings):
answer = []
dic = {} # player - 순위
dic2 = {} # 순위 - player
j = 0
for i in players:
dic[i] = j
dic2[j] = i
j += 1
for target_player in callings:
rank = dic[target_player] # 3
pre_player = dic2[rank-1] # poe
dic[target_player] , dic[pre_player] = dic[pre_player], dic[target_player]
dic2[rank] , dic2[rank-1] = dic2[rank-1] , dic2[rank]
# 정렬
dic2 = dict(sorted(dic2.items()))
for i in dic2:
answer.append(dic2[i])
return answer
dictionary 로 조회를 하니 훨씬 빠른 속도가 나오게 되었다.
'프로그래머스 > 1단계' 카테고리의 다른 글
26. 신고 결과 받기 (1) | 2024.01.22 |
---|---|
25. 공원 산책 (0) | 2024.01.22 |
23. 개인정보 수집 유효기간 (1) | 2024.01.22 |
22. 바탕화면 정리 (0) | 2024.01.20 |
21. 데이터 분석 (0) | 2024.01.20 |