👾

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 풀이 이분 탐색으로 풀 아이디어가 도저히 안 떠올라서 다른 사람의 풀이를 참조해서 풀었다. (hyeon930님 풀이) 이분탐색으로 바위를 제거하는 것이 아니라, 이분 탐색을 이용해 각 지점 사이의 거리의 최댓값을 구해야 되는 문제였다. 문제를 다시 생각해보면, "각 지점 사이의 거리의 최솟값이 x가 될 수 있는가?"를 만족하는 x들 중에 최댓값을 찾는..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 나는 처음에 차량을 진입 시점이 빠른 순서대로 정렬해서 문제를 풀었는데, 다른 사람들의 풀이를 보니 진출 시점이 빠른 순서대로 정렬 후 문제를 푸는게 더 간단했다. 진출 시점이 빠른 순서대로 차량을 정렬한다. 1) 차량의 진입 시점이 camera보다 앞에 있다면(작거나 같다면) => 차량 경로가 camera 위치에 포함되므로 추가 카메라 설치 필요 없음 2) 차량의 진입 시점이 camera보다 뒤에 있다면(크다면) => 현재 차량의 진출 시점에 다른 카메라를 설치..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 Kruskal(크루스칼) 알고리즘을 이용해서 문제를 해결했다. 섬 사이에 다리 연결에 드는 비용이 적은 순서대로 costs를 정렬한다. set[i]를 초기화해준다. set[i]는 i번째 노드의 부모 노드를 저장하는 배열이다. 부모노드란 i번째 노드와 연결된 모든 노드 중에서 인덱스가 가장 작은 노드이다. 예를 들어 노드0과 노드1이 연결되면 set[0] = 0, set[1] = 0이 저장된다. 정렬된 costs를 모두 탐색할 때까지 다음을 반복한다. - 연..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 unordered_map에 장르 이름을 key로, (장르별 재생 횟수, (노래의 고유 번호, 노래의 재생 횟수) 배열)을 value로 저장했다. 다음과 같이 문제가 주어졌을 때 genres plays return [classic, pop, classic, classic, pop] [500, 600, 150, 800, 2500] [4, 1, 3, 0] [cl..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 풀이 상의의 종류가 A, B, C 3가지일 경우 1. A를 입는다. 2. B를 입는다. 3. C를 입는다. 4. 상의를 입지 않는다. 위와 같이 4가지 경우가 있을 수 있다. 따라서 옷의 종류에 따라 (해당 종류의 옷 개수 + 1) 가지 경우의 수가 생긴다. 하지만 하루에 한 가지 이상의 옷을 꼭 착용해야 하므로 "모든 옷을 입지 않는다"라는 경우의 수를 빼줘야 한다. (answer - 1을 하는 이유) [ 의상의 종류: 해당 종류 의상의 개수 ]는 unordered_map을 이용해 저장했다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 phone_book은 string 벡터이기 때문에 {"119", "223", "11938"}을 정렬하면 {"119", "11938", "223"}이 된다. 즉, 사전 순으로 정렬된다. 따라서 phone_book을 정렬한 다음, 길이가 짧은 것부터 접두어가 가능한지 확인한다. 사전 순으로 정렬되어 있기 때문에 바로 다음 번호의 접두어가 되지 못하면, 그 뒤..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 풀이 간단히 participant와 completion 벡터를 정렬한 뒤 비교해서 완주 목록에 이름이 없는 선수를 반환하도록 했다. 정렬해서 마지막에 있는 선수가 완주하지 못한 선수일 경우 for문을 그냥 빠져나오게 되므로 answer를 participant.back()으로 초기화해줬다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12..

문제링크: www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 풀이 분배 법칙을 사용해서 문제를 풀 수 있다. ( ( ) [ [ ] ] ) 의 경우에 2x(2+3x3)으로 계산되는데, 이는 결국 (2x2) + (2x3x3)과 같다. 왼쪽 괄호가 나오면 temp에 2나 3을 곱한 뒤 스택에 push 하고, 오른쪽 괄호가 나오면 temp를 2나 3으로 나눈 뒤 스택을 pop 한다. 이때 ( ( ) [ [ ] ] ) 표시된 괄호처럼 괄호 값이 '( )' 또는 '[ ..

문제링크: programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 people을 가벼운 사람 -> 무거운 사람 순서대로 정렬한 뒤, 보트에 탈 수 있는 (가장 가벼운 사람, 가장 무거운 사람)의 조합을 찾았다. 남아있는 사람들 중 가장 가벼운 사람과도 함께 보트에 타지 못하면 그 사람은 무조건 혼자 보트에 타야 된다. light: 남아있는 사람들 중 가장 가벼운 사람 heavy: 남아있는 사람들 중..

문제링크: programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 k개의 수를 제거한다는 것은 (number.length() - k)개의 수를 뽑는 것과 같다. 뽑아야 되는 숫자의 자릿수를 n이라고 하면, number에서 뒤에서부터 (n - 1)개의 수를 남겨두고 나머지 수 중에서 제일 큰 수를 뽑으면 된다. 다음 수는 방금 뽑은 수 다음부터 뒤에서 (n - 2)개의 수를 남겨두고 제일 큰 수를 뽑는다. 이를 n개 수를 뽑을 때까지 반복한다. n: 뽑아야 되는 숫자의 개수 picked: 이전에 뽑은 숫자의 index number = "4177252841"일 때 풀이 6번째 자리 => number 뒤에서..