고관운

Q42577_전화번호 목록

문제 풀이

(1) 문제

(2) 코드

코드

 정렬하는 과정을 통해 다음 번호만 비교하면 되도록 했다.

range(len(phone_book)-1) : 다음 번호와 비교하는 과정이기 때문에 index 에러 방지를 위해 -1을 했다.

접두어의 비교를 위해 비교 대상 번호를 비교 번호의 길이만큼만 슬라이싱하여 가져왔다.
(123 vs 2345면 234만 슬라이싱하여 가져옴)

Q42578_위장

문제 풀이

(1) 문제

문제 확인하기

(2) 코드

첫 시도 코드

최종 코드

풀이 방식

처음 문제를 보고 서로 다른 옷의 조합의 수를 보고 조합을 떠올렸다. makeList 함수에서는 딕셔너리를 만들어 옷의 종류의 개수를 리스트로 만들어 리턴해줬다.

실패 방식 모든 조합의 원소의 곱을 구하기 위해 삼중 for문을 사용했다. 시간복잡도에서 효율적이지 않지만 의상의 수가 30이하이기 때문에 문제가 없을 것이라고 생각했다. 하지만 우려했던대로 테스트1번에서 시간초과가 발생했다.

개선 방식 이후 시간복잡도를 줄이기 위해 수학적으로 접근했다. 이 문제는 다항식 곱의 계수들의 합과 연관이 있다는 것을 깨달았다. 옷의 종류가 3가지, 옷의 개수가 a,b,c일 때, $(x+a)(x+b)(x+c) = x^3 + (a+b+c)x^2 + (ab+bc+ca)x + abc$ 즉, 모든 조합의 원소의 곱을 구하지 않고 계수를 합하면 쉽게 구할 수 있다. (계수를 구하는 법 : x에 1을 대입) (단, $x^3$의 계수는 조합에 포함되지 않기 때문에 결과 리턴시 -1을 해준다.)