정재영

1일 1문제 푸는 중

코딩테스트 고득점 Kit - 해시 문제

✔️ 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항

  • phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.
  • 👉 문제 보러가기


✔️ 문제 풀이

(1) Pseudo-Code

- 전화번호부에 있는 요소들을 정렬하였을 때, 첫 번째 값만 접두사가 되는 것이 아니다.

1. 전화번호부에 있는 요소는 정렬되어있지 않기 때문에 sort로 순서를 정렬한다.
2. for문으로 i번째 값과 i+1번째 값의 길이가 다른 경우, i+1 값을 i 값의 길이로 슬라이싱하여 같은 지를 확인한다.
3. 같으면 False 를 변수에 할당하고, 반복문을 종료시킨다.

(2) 코드 작성

def solution(phone_book):

    # 순서 정렬하여 접두사가 0번 위치에 있도록 설정
    phone_book = sorted(phone_book)
    
    # 접두사를 제외한 나머지 번호에서 접두사가 포함되었는지 확인
    answer = True

    for i in range(len(phone_book)-1):
        if len(phone_book[i]) < len(phone_book[i+1]):
            if phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
                answer = False
                break

    return answer

(3) 코드 결과

  • 성능 요약 : 메모리 28.1 MB, 시간 89.30 ms
  • 채점결과 : 정확성 83.3, 효율성 16.7, 합계 100.0/100.0

(4) 코드 리뷰

  • for문과 sort, 슬라이싱으로 리스트 내에 있는 요소들의 값이 같은지 확인하였다.
  • 위 문제에서 enumerate를 사용해볼까 했지만, 다음 요소의 값을 가져와야했기 때문에 적절하지 않다고 판단했다.


문제 회고

  • 문제를 해석하는데 시간이 오래 걸렸다. (접두사가 한 개만 있을 것이라고 생각하였음)
  • 코드 실행으로 3문제는 맞았지만, 제출 후 채점하기를 누르면 특정 테스트 번호에서 실패가 떴다.
  • 문제를 열심히 읽어보니, 접두사가 하나만 있다고는 언급되지 않았다….! (문제를 자세히 보자! 입출력 예제만 믿지말자!)
  • 여러 번의 실패 끝에, 코드를 완성하였다.
  • 채점결과에서 효율성이 낮게 나와서 ‘효율성’은 어떤 것을 기준으로 채점되는지 확인해 보았다.
    • 재귀함수 이용, 내장함수의 파라미터 개수 줄이기 등으로 효율성 점수를 높일 수 있다.


👩🏻‍💻개인 공부 기록용 블로그입니다
오류나 틀린 부분이 있을 경우 댓글 혹은 메일로 따끔하게 지적해주시면 감사하겠습니다.

댓글남기기