해킹왕 양선규

그리디 문제이다. 살짝 어려웠다. 난 2가지 방식으로 풀었는데, 의문점이 있다. import sysinput = sys.stdin.readline"""1. 큰 값 순서대로 정렬2. 현재 가장 큰 값 기준으로, 원본 리스트 역순 순회하며 가장 큰 값 찾기3. 찾았다면, 가장 큰 값 포함한 좌측 값 전부 사서 큰값에 팔기4. 원본리스트에서 방금 사용된 값을 전부 없애기5. 반복현재 가장 큰 값 idx가 while문당 1씩 증가하는데, 이거 좀 비효율이다. 이후에 올 큰값들이 지워지면 쓸모없어지기 때문따라서 가장 큰 값 리스트에서도 값들을 지워주고, 항상 0으로 인덱싱 하면 될 것 같은데 귀찮다.[1, 3, 1, 10, 2, 9, 3, 10, 5][10, 9, 5, 3, 2, 1]"""for _ in rang..

그리디 문제이다. 실버 3보다는 좀 더 쉬운 것 같다. 시간복잡도도 고려할 필요 없다. 난 고려하긴 했지만. import sysinput = sys.stdin.readline"""0이 앞에 최대한 많아야 한다1은 앞부터 지우고0은 뒤부터 지우면 되지않나1. 리스트로 받아서 , 지우지 말고 -1로 교체 (지우는 연산 오버헤드 방지)2. 앞부터 -1이 아닐 경우 출력"""S = list(map(int, input().strip()))"""0, 1 개수 세기"""count = [0] * 2 # 0의 개수, 1의 개수 저장할 리스트for num in S: if num == 0: count[0] += 1 else: count[1] += 1"""앞부터 1 지우기"""delete..

구현, 정렬 문제이다. 입력값이 다양하게 주어져서 헷갈리고, 관리해야 하는 데이터가 많아 헷갈린다.그러나 정렬 조건만 제대로 숙지한다면 크게 어렵지 않게 풀 수 있는 문제이다. import sysinput = sys.stdin.readline"""k개의 문제를 풀면 0점 ~ 100점 획득함 -> 팀ID/문제번호/점수 저장한 문제를 여러 번 제출하면, 최고점수가 최종점수 -> 제출안하면 0점팀의 점수는 각 문제 최종 점수의 합점수가 동일한 팀이 있을 경우1. 점수가 같으면, 제출 횟수가 적은 팀이 이긴다2. 점수와 제출 횟수가 같으면, 마지막 제출 시간이 빠른 팀이 이긴다정렬 조건: 점수 높은순, 제출횟수 적은순, 제출시간 빠른순"""for _ in range(int(input())): """ ..

구현, 문자열 문제이다. 비슷한 단어가 될 수 있는 조건을 정확히 찾으면 쉬운 문제인데, 조건 하나를 빠뜨려서 조금 헤맸다. from collections import defaultdictimport sysinput = sys.stdin.readline"""길이가 2이상 차이나면 제외.1. 길이가 1차이나는 경우, 나머지 문자의 개수가 전부 같다면 비슷한 단어이다.2. 길이가 같은 경우, 모든 문자가 같으면 비슷한 단어이다.3. 길이가 같은 경우, 하나의 문자가 다르다면 비슷한 단어이다.-> 이 3가지 외에 만족하는 케이스는 없다."""N = int(input())ref = input().strip()ref_count = defaultdict(int)for key in ref: ref_count[k..

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다. import sysinput = sys.stdin.readline"""N: 식탁의 길이K: K 이하 거리 햄버거 먹기 가능table: 사람과 햄버거의 위치사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?K가 최대 10이니 가능할거같다. K 햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다."""def can_eat(idx, K): # 기준 (사람 또는 햄버거) point = table[idx] # idx 뒤로 K거리만큼 잘라낸다 (슬라이..

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다. import sysinput = sys.stdin.readline"""1. 모든 요청을 줄 수 있다면 다 준다2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다"""N = int(input())reqs = list(map(int, input().split()))budget = int(input())def calc(limit, arr): """ 상한가를 고려해, 지급해야 할 금액 계산 limit: 상한가 ..

구현, 정렬, 시뮬레이션 문제이다. 모든 학생이 각자 물러선 총 횟수를 구해야 한다. import sysinput = sys.stdin.readlinedef binary_search(child, arr): start = 0 end = len(arr) - 1 result = len(arr) while start end: mid = (start + end) // 2 if arr[mid] > child: result = mid end = mid - 1 else: start = mid + 1 return len(arr) - resultP = int(input())for _ in r..

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 문자열 문제이고 문제 조건이 크게 어려운 건 아닌데, 구현 문제다 보니까 디테일한 부분에서의 실수가 없도록 주의해야 하는 문제이다. def solution(msg): """인덱스 -> 문자열, 문자열 -> 인덱스 사전 제작""" idx_to_str = [''] + [chr(i) for i in range(ord('A'), ord('Z') + 1)] str_to_idx = dict() for i in range(26): char = chr(ord('A') + i) str_to_idx[char] = i + 1 """메인 로직, 문자열을 전부 압축할 때..

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 시뮬레이션 문제이고 블럭을 떨어뜨리는 로직을 구현하는 것이 핵심이다. def solution(m, n, board): """블럭을 제거하는 함수""" def delete_blocks(m, n, board): # 모든 블럭에 대하여 삭제 조건 검사 deleted_blocks = set() for x in range(m - 1): for y in range(n - 1): point = board[x][y] if point == '': ..

2020 KAKAO BLIND RECRUITMENT에 출제된 문제이다.구현, 완전탐색 문제이며 보드 확장 아이디어를 떠올리지 못한다면 풀기 까다로울 수 있는 문제이다. def solution(key, lock): """ 90도 회전시키는 함수 자물쇠가 열리는지 확인하는 함수 -> 열쇠를 보드에 적용 + 자물쇠값 모두 1인지 확인 + 열쇠를 보드에서 제거 확장된 보드를 만든다 자물쇠를 보드 중앙에 배치한다 열쇠를 4방향으로 회전시키며, 모든 가능한 위치에서 열기 시도한다 """ """키를 시계 방향으로 90도 회전하는 함수""" def rotate_key(key): return [list(row) for row in zip(..