이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.
이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고
이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나
product.kyobobook.co.kr
이번 문제는 아래 링크에 접속해서 풀어볼 수 있습니다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
정답 코드
파이썬 Ver.
해답 1
해답 2
자바스크립트 Ver.
해답 3
해답 4
해답 5
문제 풀이
나는 배열을 반복문으로 탐색하며 인덱스를 조정하여 풀려고 했는데 완전 틀린 접근 방법이었다. 해당 문제를 풀기 위해서는 '우선순위 큐(최소 힙)'이라는 자료구조를 활용하면 된다. 파이썬의 heapq를 사용하면 간단히 구현할 수 있다.
모든 음식을 시간 기준으로 오름차순으로 정렬한 뒤에 시간이 적게 걸리는 음식부터 제거해 나가는 식으로 풀면 된다. 우선순위 큐에 값들을 (음식 시간, 음식 번호)의 튜플로 넣는다. 이때 입력값들은 시간들 = [8, 6, 4], K = 15 라고 하자. 첫 단계에서는 시간이 가장 적은 음식인 3번 음식을 뺀다. 음식이 3개 남아 있으므로 3(남은 음식의 개수) * 4(3번 음식을 먹는 시간) = 12를 빼야 한다. 즉 3번 음식을 다 먹는 데 12초가 걸린다는 의미이다. 결과적으로 전체 남은 시간은 15 - 12 = 3초가 된다. 전체 남은 시간은 3초이고 이번 단계에서는 그 다음 시간이 적게 걸리는 2번 음식을 뺀다. 전체 음식이 2개 남아 있으므로 2(남은 음식의 개수) * 2(2번 음식을 다 먹는 시간) = 4초를 빼야 하는데 현재 전체 남은 시간은 3초라서 빼지 못한다. 따라서 '다음으로 먹어야 할' 음식의 번호를 찾아 출력하면 된다. 전체 남은 시간이 3초이므로 4번째 음식의 번호를 출력하면 된다.
따라서 2번 음식을 출력한다.
해답 5를 기준으로 또 다른 풀이를 설명하겠다. 우선 주어진 음식 배열을 '음식을 먹는 데 걸리는 시간'을 기준으로 오름차순 정렬하면 다음의 오른쪽 그림과 같다. 가로축의 숫자는 음식 번호이고, 세로축은 음식을 먹는 데 걸리는 시간이다.
현재 음식을 먹는 데 걸리는 총 시간을 음식을 먹는 데 소모할 수 있는 남은 시간(k)에서 차례대로 빼나간다. 이때 작은 것부터 빼나가는데 그래야 한꺼번에 k에서 뺄 수 있기 때문이다. 위 그림에서는 음식 번호 3번이 음식을 먹는 데 걸리는 시간이 1이므로 가장 작다. 음식을 먹는 데 걸리는 시간(1) * 남은 음식의 총 개수(6)을 하면 현재 음식을 먹는 데 걸리는 총 시간(6)이 나오고 이를 음식을 먹는 데 소모할 수 있는 남은 시간에서 빼면 20 -> 14가 된다. 이를 배열로 나타내면 다음과 같다.
[1, 3, 3, 5, 5, 6] -> [0, 2, 2, 4, 4, 5]
3번 음식을 다 먹었으므로 모든 음식 중 먹을 수 있는 음식의 개수는 5개가 된다. 그리고 다음 먹을 음식의 개수는 2이다. 원래는 3이었지만 이전 작업에서 1만큼 먹었기 때문이다. 따라서 음식을 먹는 데 걸리는 총 시간은 2 * 5 = 10 이 되고 이를 k에서 빼면 k는 4가 된다.
다음 음식을 먹는 데 걸리는 총 시간은 2 * 3 = 6으로 k보다 크다. 이를 k에서 한꺼번에 뺄 수 없으므로 정답을 반환한다. 정답을 구하기 위해서는 배열을 다시 음식 번호 순으로 오름차순 정렬을 한다. 그런 다음 k에서 남은 음식 개수를 나눈 나머지를 구하면 바로 다음 먹을 음식의 인덱스이다. 이를 반환하면 정답이 된다.
참고 링크
https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/
2019 카카오 신입 공채 1차 코딩 테스트 문제 해설
작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데
tech.kakao.com
https://gwang920.github.io/algorithm/progreammers-2-42891/
프로그래머스 - [Level 4] 무지의 먹방 라이브(JAVASCRIPT)
프로그래머스 무지의 먹방 라이브[2019 카카오 블라인드]
gwang920.github.io
[JS] Q06 무지의 먹방 라이브
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어졌고 고민 끝에 카카오 TV 라이브 방송을 하기로 마음먹었습니다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 다음과 같
velog.io
034 다양한 기준으로 정렬하려면? ― operator.itemgetter
operator.itemgetter는 주로 sorted와 같은 함수의 key 매개변수에 적용하여 다양한 기준으로 정렬할 수 있도록 하는 모듈이다. ## 문제 학생의 이름, …
wikidocs.net
'👩💻 Programming > Coding Test 문제 풀이' 카테고리의 다른 글
| [이코테] 구현_상하좌우(파이썬/자바스크립트) (0) | 2022.12.10 |
|---|---|
| [프로그래머스] level 1 체육복(파이썬 python) (0) | 2022.12.04 |
| [이코테] 그리디_볼링공 고르기(파이썬 python) (0) | 2022.11.29 |
| [이코테] 그리디_만들 수 없는 금액(파이썬/자바스크립트) (0) | 2022.11.29 |
| [이코테] 그리디_문자열 뒤집기(파이썬/자바스크립트) (0) | 2022.11.25 |
댓글