본문 바로가기

2021카카오공채5

[programmers][2021카카오공채] 광고 삽입 문제 : programmers.co.kr/learn/courses/30/lessons/72414 부분합 문제. hh:mm:ss 로 이루어진 문자열 시간으로는 계산하기 힘드므로 플레이타임, 광고시간, log 시간들 모두 second로 변환한 후 계산한다. log의 시작 시간을 start, 종료 시간을 end라 한다면 subSum[start]++, subSum[end]-- 로 갱신한다. 예를 들어, start가 1, end가 3이라면 index (i) 0 1 2 3 4 subSum[i] 0 1 0 -1 0 모든 log 정보를 탐색하며 subSum을 갱신했다면 처음부터 모든 subSum을 탐색하며 subSum[i] = subSum[i] + subSum[i-1]로 정보를 갱신한다. 갱신하면 특정 시간대의 광고를.. 2021. 3. 24.
[programmers][2021카카오공채] 순위 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/72412 query가 100,000 infos가 50,000. query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다. 개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개. 3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다. scores[개발언어][직군][경력][소울푸드] = 점수들 배열. 만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다. query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 s.. 2021. 3. 6.
[programmers][2021카카오공채] 합승 택시 요금 문제 : programmers.co.kr/learn/courses/30/lessons/72413 그래프이고 간선에 가중치가 있다. 최단거리알고리즘을 생각해본다. 정점 개수 n의 크기가 200으로 작은 편이므로 플로이드 워셜알고리즘으로 각 정점에서 다른 정점까지 이동할 때 최소 비용을 구해둔다. pays[u][v] = u->v로 택시를 타고 이동할 때 드는 최소 비용 합승종료지점 m 이라 하자. 이 때, 택시 비용은 출발지점에서 m 위치로 이동하는 비용 + m에서 각자의 집으로 이동하는 비용이 된다. pays 배열로 표현하면 pays[s][m] + pays[m][a] + pays[m][b] 과 같다. 따라서 m을 0~n으로 두고 위 수식에 적용하여 구한 택시비용들 중 최소 비용이 정답이 된다. 시간복잡도는.. 2021. 3. 4.
[programmers][2021카카오공채] 메뉴 리뉴얼 문제 : programmers.co.kr/learn/courses/30/lessons/72411?language=cpp orders의 모든 문자열을 탐색하며 각 주문들을 먼저 오름차순 정렬 후, DFS를 돌리며 모든 조합을 구한다. 만약 구한 조합 문자열 길이가 courses에 해당된다면 해당 조합을 key값으로 하고 등장횟수를 value로 하는 map(ex, 만약 AC 조합이 2번 등장했으면 map["AC"] = 2)에 갱신한다. ( value + 1) 해당 map을 다 만들었으면 탐색하면서 이번에는 조합의 길이(코스종류)를 key값, 등장횟수와 조합 리스트를 value로 가지는 map을 만든다.(ex, map[2] = [{1, "AC"}]) 이때, 등장횟수가 한 번인 경우는 메뉴가 될 수 없으므로 제.. 2021. 2. 7.
[programmers][2021카카오공채] 신규 아이디 추천 문제 : programmers.co.kr/learn/courses/30/lessons/72410 하라는대로 하면 된다. 입력값으로 받은 문자열을 앞에서부터 탐색하면서 6(길이가 16이상), 1(대문자 -> 소문자), 2(맞지않은 기호 패스), 4(콤마인데 정답 문자열이 비어있거나 정답문자열의 마지막이 콤마인지) 순으로 체크하고 문제없으면 answer 문자열의 뒤에 추가한다. 탐색이 끝난 후 4(정답 문자열의 뒤가 콤마라면 제거), 5(빈 문자열이면 'a' 추가), 7(길이가 3이상이 될때까지 가장 뒤에있는 문자를 추가) 순으로 조건을 만족하는 문자열을 만든다. 시간복잡도는 O(N). N은 문자열의 길이다. 소스코드 : github.com/fpdjsns/Algorithm/blob/master/program.. 2021. 2. 1.