프로그래머스의 레벨 2 문제 전화번호목록 문제 요구 조건 접두어가 리스트에 포함되는지 비교해야한다. 내 풀이 방법 문자열 비교에 걸리는 시간을 단축하기 위해서 해시테이블에 저장하고, 모든 접두어를 만들어서 n*m으로 해결했다. # 모든 가능한 접두어를 해시테이블에 저장하고 비교하면 n*m. 범위가 작아서 가능 def solution(phone_book): d = {phone[:i]: True for phone in phone_book for i in range(1, len(phone))} for phone in phone_book: if d.get(phone, False): return False return True 다른 풀이 방법 문자열을 사전식으로 정렬하면 원소의 뒤에 있는 원소에 포함되는지만 비교..
Computer science/Algorithm
프로그래머스의 레벨 2 문제 H Index 문제 요구 조건 조건에 맞는 h의 최댓값을 구해야한다. 내 풀이 방법 첫 번째 방법. 범위가 작으므로 완전탐색을 하면 n^2 으로 풀 수 있다. 두 번째 방법. 역순으로 정렬하고, 순회할 때 하나씩 세면서 citation이 h보다 클 때 h를 1씩 증가시키면 h는 h보다 높은 citation의 수가 된다. 따라서 h의 최댓값을 구할 수 있다. # h의 최댓값을 구해야함 # h 값의 범위는 0~1000 # 배열을 정렬하고 0부터 1000까지 조회하면서 가장 큰 h를 찾자 # 6 6 5 5 3 1 0 -> 4 def solution(citations): answer = 0 citations.sort(reverse=True) for i, citation in enum..
프로그래머스의 레벨 2 문제 가장 큰 수 문제 요구 조건 숫자들을 가지고 사전식으로 가장 큰 수가 되도록 만들어야 한다. 내 풀이 방법 숫자의 앞 자릿수가 큰 순서대로 정렬한다. 숫자의 최대 길이가 4이기 때문에 모든 숫자의 길이를 최소 4로 맞춰준다. # 숫자의 앞 자리수가 큰 순서대로 정렬한다 # 문자를 여러번 반복해서 최소 4자릿수로 만들어서 비교한다 # 정렬한 배열의 원소들을 문자열로 만든다 def solution(numbers): l = sorted(map(str, numbers), key=lambda x: x*4, reverse=True) return str(int(''.join(l))) solution([6, 10, 2]) solution([31, 312, 313, 318, 319])..
프로그래머스의 레벨 2 문제 호텔 대실 문제 요구 조건 이해하기 필요한 최소 객실의 수를 알아내야 한다. 내 풀이 방법 빈 방이 있으면 주고, 없으면 객실을 하나 늘린다. 빈 방이 있는지 검사하는 방법은 예약 시작 시간과 방들의 퇴실 시간 + 10분을 비교한다. 예약 목록을 예약 시작 시간을 기준으로 정렬하고 예약 목록을 순회하면서 1번을 반복한다. class Room: def __init__(self, t): self.time = t def change(self, t): self.time = t def is_empty(self, t): if self.time + 10
프로그래머스의 레벨 2 문제 리코쳇 로봇 문제 요구 조건 이해하기 보드 게임판의 시작 지점에서 목표 지점까지 최소 몇 번 만에 도착할 수 있는지 찾아야 한다. 내 풀이 방법 최소 이동 횟수를 구하는 문제이므로 BFS를 사용해서 풀 수 있다고 생각했다. 최소 이동 횟수를 구해야 하므로 BFS를 구현할 때, 턴을 나눠서 행동하도록 했다. 그리고 도달할 수 없는 경우는 모든 포지션을 방문하고 큐가 비었을 때라고 생각했다. 미끄러지는 이동을 담당하는 move 함수를 만들고, BFS를 사용해서 풀었다. from queue import deque def move(pos, board, direction): board_height = len(board) board_width = len(board[0]) if dir..
코딜리티의 Easy 문제 PassingCars 문제 요구 조건 이해하기 배열을 순회하면서 원소의 값이 1이라면 그 이전 인덱스까지의 원소들 중에 0이 몇 개나 존재하는지 세어야 한다. 내 풀이 방법 문제 카테고리가 구간합인걸 보고 힌트를 얻었다. 누적합 배열을 만들고, 주어진 배열을 순회하며 값이 1인 곳의 index - 누적합[index] + 1이 이전까지의 원소들 중 0의 개수라는 것을 이용했다. def solution(A): sum_array = [A[0]] result = 0 for i in range(1, len(A)): sum_array.append(A[i] + sum_array[i-1]) for i, value in enumerate(A): if value == 1: result += i..
