문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12981
문제 설명
영어 끝말잇기에서 틀린 사람의 순서와 몇번째 차례에 틀렸는지 반환하라
- 주요 규칙
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
1차 시도
def solution(n, words):
before_list = []
before = words[0][0]
for k, i in enumerate(words):
num = (k+1)%n
if i in before_list or before != i[0]:
if num==0:
return [n,(k+1)//n]
else:
return [num, (k+1)//n+1]
before_list.append(i)
before = i[-1]
return [0,0]주요 규칙 두가지를 염두에 두고 작성한 코드.
여기서 중요한 점. (내가 인덱싱을 활용을 못하네..)
- before list를 만들어줄 필요 없이 이전 원소까지의 리스트를 슬라이싱해서 확인하면 된다.
- 마찬가지로 before을 저장해줄 필요 없이 인덱스로 접근하면 된다.
2차 시도
def solution(n, words):
for i in range(1,len(words)):
num = (i+1)%n
if words[i] in words[:i] or words[i-1][-1] != words[i][0]:
if num==0:
return [n,(i+1)//n]
else:
return [num, (i+1)//n+1]
return [0,0]그 부분을 수정해서 작성한 코드.
근데 여기서 순서와 차례를 계산하는 코드가 단순화될 수 있다! (다른 사람 풀이를 보고 안 것)
3차 시도
def solution(n, words):
for i in range(1,len(words)):
if words[i] in words[:i] or words[i-1][-1] != words[i][0]:
return [i%n+1,i//n+1]
return [0,0]요렇게. 이건 그냥 생각을 덜 해서 발생한 실수였던 것 같다.
4차 시도
def solution(n, words):
for i in range(1,len(words)):
if len(set(words[:i])) == len(set(words[:i+1])) or words[i-1][-1] != words[i][0]:
return [i%n+1,i//n+1]
return [0,0]다른 사람 풀이에 시간복잡도를 생각하면 in 대신 set을 쓰는게 좋겠다는 댓글이 있어서 바꿔봤는데, 이렇게 쓰라는 말이 아닌가? 오히려 더 오래걸림. 아니면 words 최대 길이가 100뿐이라서?
5차 시도 - 가장 효율적인 코드
def solution(n, words):
used = set()
used.add(words[0])
for i in range(1,len(words)):
before = len(used)
used.add(words[i])
if len(used)==before or words[i-1][-1] != words[i][0]:
return [i%n+1,i//n+1]
return [0,0]오 이렇게 해봤더니 이게 2차 시도 코드보다 더 빠르다!
for문마다 list에 set을 씌우는 것보단 애초에 사용된 set을 만들어서 길이를 측정하는 쪽이 더 효율적인 것 같다.
아마 words 길이가 더 길어진다면 in을 사용하는 것보다 이게 더 효율적인 코드가 되겠다.
정리
- set을 잘 사용한다면
in보다 더 효율적인 코드를 작성할 수 있다. - 인덱싱, 슬라이싱을 잘 활용하자. 새로운 변수를 할당하기보단 있는걸 잘 사용하자
- 무조건 짧은 코드가 좋은 건 아니다. 잘 생각하자.
