본문 바로가기

Problem Solving/프로그래머스

 (42)
[프로그래머스/C++] 단속카메라 풀이 (greedy를 스마트하게) 문제 이해 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다. 차량의 진입..
[프로그래머스/약수 찾기] 약수의 개수와 덧셈 (나를 위한 기록) 문제 설명 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ left ≤ right ≤ 1,000 입출력 예 left right result 13 17 43 24 27 52 입출력 예 설명 입출력 예 #1 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다. 수 약수 약수의 개수 13 1, 13 2 14 1, 2, 7, 14 4 15 1, 3, 5, 15 4 16 1, 2, 4, 8, 16 5 17 1, 17 2 • 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 ..
[프로그래머스/파이썬] 최소직사각형 해설 및 증명 문제 문제 설명 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다. 명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다...
[프로그래머스/파이썬] 2018 KAKAO BLIND RECRUITMENT[1차] 비밀지도 문제 해석 문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 ..
[프로그래머스/파이썬] 성격 유형 검사하기 문제 해석 문제 풀이 결국 각 문항마다 점수를 부여하는데 (매우 비동의 3점) ~ (모르겠음 0점) ~ (매우 동의 3점) 이라고 생각하면 각 문항에 대해 한 가지 성격 유형을 음수 다른 나머지를 양수로 지정하고 계산하면 되는 것이다. 조금 복잡하지만 최대한 간단한 방법은 map을 이용하는 방법이라고 생각했다. 요즘 특히 프로그래머스 lv.1에 map을 이용한 풀이 문제가 참 많아서 바로 map을 떠올리기도 했다. (이렇게 유형타면 실제 코테에서 말아먹을텐데... 자꾸 게으르게 편한 방법을 생각한다.) 우선 나는 한가지 성격 유형을 map으로 지정해주고 그 유형이 앞글자라면 동의를+3점으로 그 유형이 뒷글자라면 비동의를 +3점으로 처리하였다. 이후 각 점수에 대한 결과로 양수면 지정된 성격 유형을 반대라..
[프로그래머스/C++] 달리기 경주 풀이 문제 해석 문제 풀이 처음에 이름을 부른 이후 추월을 어떻게 계산해주어야 할까 고민하다가 단순 구현인가 하고 callings의 길이를 보았더니 100만이라 각 플레이어가 불릴 때마다 배열을 swap해주는 형태는 시간 초과가 날 것 같았다. 그럼 배열을 O(1)이나 O(nlogn)만에 찾아줄 수 있는 방법이 필요했다. map 사용을 생각하였으나 하나로 풀 방법을 몰라 2개로 구현했었다. 하나에는 선수의 이름을 넣으면 등수를 알려주고, 다른 것에는 등수를 넣으면 이름을 알려주도록 짰는데 다른 정답 코드들을 보니 map하나로도 충분하다. 코 드 #include #include #include using namespace std; vector solution(vector players, vector callin..
[프로그래머스/C++] 디스크 컨트롤러 풀이 문제 해석 문제 풀이 운영체제 시간에 배운 CPU Job scheduling 문제 같았다. 처음에 activity selection problem으로 생각해서 헤맸는데 우선순위 큐 문제이다. job을 시작 시간 기준으로 오름차순 정렬한다. 현재 시간보다 작거나 같은 job을 모두 우선순위 큐에 넣는다. 우선순위 큐는 빨리 끝나는 job을 top으로 올리도록 설정한다. job을 실행한 후 큐에서 pop한다. 2~4번을 큐가 빌 때까지 반복한다 코 드 #include using namespace std; struct compare { bool operator()(vector lhs, vector rhs) { return lhs[1] > rhs[1] ; } }; int solution(vector jobs) ..
[프로그래머스/C++] 2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기 문제 해석 문제 풀이 결국 어느지점까지 찍고 돌아와야 하니 가장 먼곳을 가장 적게 다녀오는 것이 핵심이겠다고 생각했다. 택배를 배송하고 나면 수거할 공간이 생기니 자명하게 최대 갯수만큼 배송하고 최대갯수만큼 수거하는 것이 좋을 것이다. 가장 먼곳에서 최대한 많은 갯수를 동시에 배송하고 수거하는 것이 핵심이라 보고 greedy하게 뒷배열부터 처리해주는 결정을 했다. 또한 횟수가 남는다면 그 다음번에 그 횟수만큼 차감한 후 계산하면 되겠다고 생각하였다. 처음 짠 코드는 배송과 수거를 분리하여 고려하고 둘 중에 횟수가 많은 쪽을 정답으로 처리해주었는데 4, 4, [25, 24, 51, 0], [51, 0, 0, 49] 에서 반례가 생겼다. 다시 생각해보니 매 순간마다 더 많이 다녀와야하는 곳이 어디인지 고려하..

티스토리툴바