본문 바로가기

programming study/Algorithm

 (275)
[프로그래머스] 순위 검색 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 해결 방법 시간복잡도가 중요한 문제 query가 매개변수로 주어질 때, 해당하는 사람들의 숫자를 배열에 담아 반환 query 배열의 크기는 최대 100,000 info 배열의 크기는 최대 50,000 query * info를 따져봤을 때 시간복잡도에서 오답처리가 된다는 것을 예측할 수 있다. 효율적인 방식 Hash Table : 특정 값을 검색할 때 O(1) query의 경우의 수를 다 구해서 hash key로 만들기 hash key를 충족하는 지원자의 점수를 key 값에 배열로 넣기 각 hash key에 들어가 있는 점수 배열을 정렬 이분 탐색으로 원하는 결과를 찾기 파이썬 코드 # 순위 검색 from itertools..
[프로그래머스] 소수 찾기 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 소수 찾기 from itertools import permutations import math def solution(numbers): # numbers를 리스트화 numbers = list(numbers) # numbers의 길이 numbers_len = len(numbers) # numbers의 순열 number_per = set() # 주어진 수로 만들 수 있는 순열 for i in range(1, numbers_len + 1): # 만들어진 순열을 하나의 문자열로 합쳐서 반환 # -> 정수화 # -> set 자료형으로 중복 제거 number_per |= ( set(map(int, map(''.joi..
[프로그래머스] 카펫 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 카펫 def solution(brown, yellow): # 답을 담을 배열 answer = [] # 노란색 격자의 가로 길이 yellow_width = 0 # 노란색 격자의 세로 길이 yellow_height = 0 # 갈색 격자의 수를 구하는 공식 # (yellow_wdith * 2) + (yellow_height * 2) + 4 # 위 식을 이용하여 주어진 갈색 격자의 수가 나오는 노란색 격자의 가로, 세로의 조건을 찾는다 while True: # 노란색 격자의 높이를 1씩 더하기 yellow_height += 1 # 노란색 격자의 가로길이 구하기 yellow_width = yellow / yello..
[프로그래머스] 예상 대진표 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 2 x n 타일링 # 메모이제이션 memo = { 1: 1, 2: 2, } def solution(n): # memo에 있는 경우 if n in memo: return memo[n] # memo에 없는 경우 else: for i in range(3, n + 1): # 3부터 해당 수까지 메모이제이션하여 찾기 memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007 return memo[n] Comment n이 1, 2, 3, 4, 5 일 때 각각 직접 그려보면서 점화식을 도출하였다. 길이가 n일 때의 경우의 수는 n - 2, n - 1일 때 경우의 수의 합과 같으므로 이것..
[프로그래머스] 예상 대진표 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 예상 대진표 import math def solution(n, a, b): answer = 0 # 진행할 수 있는 경기 수가 1보다 크면 실행 # 진행하는 경기 수가 1이면 서로 무조건 만나므로 while True: # 현재 라운드 수 answer += 1 # 이겼을 때 부여되는 번호 입력 a = math.ceil(a / 2) b = math.ceil(b / 2) # 이겼을 때 부여되는 번호가 같으면 중단 if a == b: break return answer Comment 메모장에서 대진표를 직접 그려보고 시뮬레이션하여 빠르게 풀어낼 수 있었다! 어떠한 수도 이기고 나서 자기 자신을 나눈 것의 올림으로 ..
[프로그래머스] 위장 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 위장 def solution(clothes): answer = 1 # 딕셔너리 변환 clothes_dic = {} for cloth in clothes: # 키가 딕셔너리에 없는 경우 # 배열안에 키 값을 넣기 if cloth[1] not in clothes_dic: clothes_dic[cloth[1]] = [cloth[0]] # 키가 딕셔너리에 있는 경우 # append하기 else: clothes_dic[cloth[1]].append(cloth[0]) # 입을 수 있는 옷 조합은 # 옷 조합의 수 = (각 종류별 옷의 수 + 1) * (각 종류별 옷의 수 + 1) ... - 1 # -1 은 전부 안 ..
[프로그래머스] 다음 큰 숫자 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 다음 큰 숫자 def solution(n): answer = 0 # n을 2진수로 변환 후 문자열로 바꾸기 n_bin = str(bin(n)) # 1의 갯수 one_count = n_bin.count('1') # 조건을 충족하는 수가 나올 때 까지 반복 while True: n += 1 # 2진수로 변환 후 문자열로 바꾸기 next_bin = str(bin(n)) # 1의 갯수가 n의 1의 갯수와 같으면 정답처리 후 중단 if one_count == next_bin.count('1'): answer = int(n) break return answer Comment 내 코드가 평가가 좋은 답안과 거의 비슷했..
[프로그래머스] 기능 개발 - python 풀이 본 게시물은 프로그래머스의 연습 문제 풀이입니다. 저작권은 (주) 그랩에게 있습니다 파이썬 코드 # 기능 개발 from collections import deque def solution(progresses, speeds): answer = [] # 주어진 두 리스트를 deque로 변환 progresses = deque(progresses) speeds = deque(speeds) # 모든 기능이 완료될 때 까지 반복 while progresses: # 카운트 cnt = 0 # progresses의 길이 progresses_len = len(progresses) # progresses에 하나씩 접근하여 speeds 더하기 for i in range(progresses_len): # 100보다 큰 경우 넘..

티스토리툴바