본문 바로가기

알고리즘 문제

프로그래머스 예산 어려웠던 점 1. 언제까지 반복해야 하나 ->log_2(max - min)+1 번 2. 예산 상한액을 어떻게 측정하나 -> 가능한 상한액을 list에 넣고 최대값 출력 3. 테스트 케이스 9번, 런타임 에러 -> n개의 도시에 예산을 배분할 때 (M // len(budgets)가 min(budgets)를 넘지 못하면 (M // len(budgets)가 최대 예산이다. 마지막 테스트 케이스는 유효한지 모르겠다. 세 도시에 1씩 나눠줄 수 없어서 1,1,0 이렇게 나눠야 하는데 균등하게 분배한다고 하면 0이 맞는 것 같다. 도시 예산의 총 합이 M 이하면 도시 예산 중 최대값 반환 전체 예산을 각 도시에 균등하게 분배할 수 있는 금액이 최소 도시 예산도 넘지 못하면 균등하게 분배할 수 있는 금액 반환 이분탐..
프로그래머스 카펫 일단 red, brown으로 만들어지는 모양은 십자가같은 건 아니고 직사각형이다. 가로, 세로 길이가 다양하게 나올 수 있는데 주어진 red, brown의 타일 수로 red 직사각형을 만들고 brown으로 그 테두리를 감쌀 수 있으면 되는 것이다. red의 개수로 직사각형을 그리다보면 red를 만들 수 있는 공약수로 짝을 지어서 그릴 수 밖에 없다. red가 9면 1 x 9, 3 x 3 27이면 1 x 27, 3 x 9 24면 1 x 24, 2 x 12, 3 x 8, 4 x 6 이런 식이다. 가로의 길이는 세로보다 같거나 크다. red로 만들 수 있는 다양한 직사각형의 테두리에 brown의 개수를 다 써서 채우는 걸 찾으면 된다. red의 공약수 짝으로부터 테두리에 쓰인 타일 수를 구하는 식은 red의 ..
프로그래머스 숫자 야구 111, 011, 101, 133, 999와 같이 중복되는 숫자나 0은 나올 수 없다. 123, 456, 987 이런 숫자만 올 수 있다. make_nums 함수는 3자리 수이면서 각 자리수가 서로 중복되지 않는 수들을 만든다. 가능성이 있는 수들의 list인 nums를 돌면서 주어진 질문과 비교한다. 각 자리수에 있는 값이 일치하면 strike를 증가시키고 그 자리를 False로 만든다. 혹은 False 처리를 안하고 나중에 ball 비교를 할 때 index가 다르면 ball을 증가해주면 된다. 만약 질문에 있는 strike, ball의 값이 하나라도 다르면 flag는 False가 되고 나머지 질문들을 검사할 필요가 없이 주어진 n은 탈락이므로 break로 for문을 벗어나고 다음 n을 검사한다. 만약..
프로그래머스 소수 찾기 시간 초과가 났는데, 잘 모르겠어서 다른 분의 코드를 참고했다. 에라토스테네스의 체를 효율적으로 작성해서 index 접근만으로 소수인지 아닌지 판단을 해야한다. itertools 패키지의 permutations 모듈을 활용해 입력된 문자열화 된 숫자의 순열을 구한다. '123'이라면 '1', '2', '3', '12', '23', '13', '123' 이런 식이다. '011'이라면 '0', '1', '1', '01', '11', '011'인데 '1'과 '01'을 정수화하면 똑같은 1이고, '11', '011' 역시 정수화 하면 똑같이 11이다. 그래서 set()을 사용해서 중복을 제거해야 한다. from itertools import permutations def get_prime(n): primes =..
프로그래머스 모의고사 def solution(answers): supo = [ [1, 2, 3, 4, 5], [2, 1, 2, 3, 2, 4, 2, 5], [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] ] an_len = len(answers) for nums in supo: mul = an_len // len(nums) if mul > 0: nums *= (mul + 1) supo_dict = {0: 0, 1: 0, 2: 0} for i in range(an_len): if answers[i] == supo[0][i]: supo_dict[0] += 1 if answers[i] == supo[1][i]: supo_dict[1] += 1 if answers[i] == supo[2][i]: supo_dict[2] += ..
프로그래머스 베스트 앨범 실패 여러 테스트 케이스에서 런타임 에러가 남 from operator import itemgetter def solution(genres, plays): album_list = [] for i in range(len(genres)): album_list.append({ 'genres': genres[i], 'play_value': plays[i], 'play_index': i }) album_list = sorted(album_list, key=itemgetter('play_value'), reverse=True) genre_dict = {} for album in album_list: if album['genres'] not in genre_dict: genre_dict[album['genres']]..
프로그래머스 위장 테스트 1에 대해 시간 초과난 코드. def solution(clothes): c_dict = {} for c in clothes: if c[1] in c_dict: c_dict[c[1]] += 1 else: c_dict[c[1]] = 1 c_list = [] for i in c_dict: c_list.append(c_dict[i]) result = 0 length = len(c_list) n = 2 ** length for i in range(1, n): bin_n = format(i, 'b').zfill(length) multi_result = 1 for j in range(length): num = int(bin_n[j]) if num != 0: multi_result *= c_list[j] * n..
프로그래머스 전화번호 목록 dict를 쓰라는데 고민해봐도 잘 안떠올라서 되는대로 풀었다. 다른 사람 풀이를 보니까 startswith()를 사용해서 비교하기도 했다. def solution(phone_book): pb_len = len(phone_book) phone_book.sort() for i in range(pb_len): phone_book[i] = str(phone_book[i]) for i in range(pb_len): for j in range(i+1, pb_len): std_num_len = len(phone_book[i]) if std_num_len > len(phone_book[j]): continue else: if phone_book[i] == phone_book[j][:std_num_len]: retur..

티스토리툴바