해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수 해시(Hash) 만약 이름 대신 번호가 주어졌다면? => 선형 배열 이름을 키(key)로 하여 해시 함수(Hash function)를 통해 해시 테이블(hash table)에 매핑 풀이 (1) 사전(Dictionary)의 원소들을 해시를 이용해 O(1) 시간에 접근 가능 사전을 활용하여 "이름 : 이름 수"로 저장하여 마지막 남은 사람의 이름 반환 코드 get(x, 0) : x라는 키가 존재하면 해당 값을, 존재하지 않으면 0을 반환 최종 시간 복잡도 : O(n) def solution(participant, completion): d = {} # O(n) for x in participant: d[x] = d.get(x, 0) + 1 # O(n) ..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 한 번호가 다른 번호의 접두어인 경우가 있는지 확인 전화번호를 담은 배열 phone_book 어떤 번호가 다른 번호의 접두어인 경우 False, 그렇지 않다면 True 반환 풀이 배열 phone_book을 모두 확인하여 접두어가 있으면 False, 접두어가 없다면 True 반환 배열 phone_book의 길이는 최대 1,000,000이므로 시간 초과에 유의 => 연산 횟수를 줄이기 위해 배열과 문자열의 길이를 변수를 통해 저장 및 조건문 추가 sort 메소드를 통해 phone_book을 정렬 ..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 각 종류별로 최대 한 가지 의상만 착용 가능 착용한 의상의 일부가 겹쳐도 다른 의상이 겹치지 않거나 추가로 착용하면 다른 경우로 봄 하루에 최소 한 개의 의상을 입음 의상이 담긴 2차원 배열 clothes, [의상의 이름, 의상의 종류]로 구성 서로 다른 옷의 조합의 수를 반환 풀이 아무 것도 입지 않는 경우를 포함한 모든 경우를 구하는 방법은 (N + 1)(M + 1)...(P + 1) 아무 것도 입지 않는 경우를 제외해야 하므로 (N + 1)(M + 1)...(P + 1) - 1 의상의 종..