대기하는 차(truck_weight)가 1대 이상 존재하고, 차가 도로위에 올라갈 수 있다면 도로에 진입시킨다.
(도로가 견딜 수 있는 무게를 고려한다.)
도로에 올라가있는 차량 리스트를 queue로 확인 한다. ( queue count )
도로에 올라가있는 차량은 1초에 1씩 이동한다.
도로를 지나고 있는 차량의 남은 거리를 queue로 관리한다. ( queue bridge_on )
차를 pop해서 차의 남은 거리를 1씩 감소시키고, 다시 push 한다.
대기차가 없어도 도로에 차가 있다면 차가 1씩 이동하고 있으므로 시간은 1초씩 계속 흐른다.
코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
// 시간
int answer = 0;
// 도로 위 차
queue<int> count;
// 차마다 가야할 남은 거리 (도로를 얼마나 더 가야 하는지)
queue<int> bridge_on;
// 도로 위의 차 무게 합계
int current_weight = 0;
int i = 0;
while(true){
//차들이 가야할 거리
int togo_size = bridge_on.size();
// 차를 도로에 진입시킨다.
for(i = 0; i < togo_size; i++){
// 제일 앞에 가고있는 차의 남은 거리
int len_front = bridge_on.front();
bridge_on.pop();
if(len_front <= 1){ // 남은 거리가 1 이하라면, 이 차의 무게를 제외시킨다
current_weight -= count.front();
count.pop();
continue;
} else{
// 거리 감소시키고 다시 push
bridge_on.push(--len_front);
}
}
// 도로의 제한무게 만큼 차를 집어넣는다. 대기 차량이 1개 이상 있어야 함.
if(truck_weights[0] + current_weight <= weight && truck_weights.size() > 0 ) {
count.push(truck_weights[0]); // 도로에 차 추가
current_weight += truck_weights[0]; // 현재 도로 무게에 차 무게 추가
truck_weights.erase(truck_weights.begin()); // 대기 차량 삭제
bridge_on.push(bridge_length); // 이 차가 지나야할 도로 거리 추가
}
answer++; // 시간이 지나감
if(count.size() == 0 && truck_weights.size() == 0){
break;
}
}
return answer;
}
예를 들어, 5의 배수를 지워야한다면 5_2, 즉 10부터 지우는게 아니라 5의 제곱 25부터 지운다.
25 + (1 * 5), 25 + (2 * 5), 25 + (3 * 5) , ... 그러면 이전에 지워진 배수들을 건너 뛰게 된다.
코드
#include <stdio.h>
#include <vector>
using namespace std;
// 소수 찾기 프로그래머스
/*
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
n은 2이상 1000000이하의 자연수입니다.
*/
int arr[1000001];
// arr[0]과 arr[1]은 사용하지 않는다. 0과 1은 소수가 아니기 때문.
// 소수면 0, 소수가 아니면 1값을 갖는다.
int solution(int n) {
int answer = 0;
int i = 0, j = 0;
for (i = 2; i * i <= n; i++)
{
if (arr[i] == 0){ // i가 소수라면, i의 배수는 소수가 아니다.
// 유의: i의 제곱부터 지우기 시작한다.
for (j = i * i; j <= n; j += i)
arr[j] = 1; // 소수가 아니므로 1값 할당.
}
}
for(i = 2; i <= n; i++){ // 소수로 남겨진 것들의 개수를 센다
if(arr[i] == 0) answer++;
}
return answer;
}
문제에 나와있는 테스트케이스에서 [3, 0, 9, 2, 6] 이라면, 답은 3이라고 생각했다. 하지만, 다른분들의 풀이법을 읽어보니 인용수 배열중에 답이 꼭 있는것이 아니었다. 그리고 정렬을 하면 수월했다. 정렬 해두고, 현재 인덱스보다 작아진다면 탈출하면 답이 나온다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
// H-index (프로그래머스)
int solution(vector<int> citations){
int answer = 0;
// 정렬
sort(citations.begin(), citations.end(), greater<int>());
while(answer < citations.size()){
if(citations[answer] <= answer){ // 인덱스 보다 작아지는 순간 종료
break;
}else{
answer++;
}
}
return answer;
}
왕자 N명이 있고, 이 중에서 공주를 구하러 갈 왕자를 정하기로 했다. 왕자들의 나이 순으로 1번 부터 N번까지 번호를 매기고 동그랗게 둘러 앉는다. 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7번 왕자가 공주를 구하러간다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.
입력설명 첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다. 8 3
출력설명 첫 줄에 마지막 남은 왕자의 번호를 출력합니다. 7
구조
인덱스를 1부터 이용하기 위해 벡터를 n+1 크기로 생성한다. 0의 개수를 k 번째 까지 센다. 개수는 cnt 변수에 누적한다. k번째 왕자의 값을 1로 변경한다. break point 가 n-1 이 되면 중단한다.
void Insert(Heap* H, int newData) {
// 1. 최고 깊이 최 우측 노드와 그 것의 부모 노드 인덱스
int currentPosition = H->usedSize;
int parentPosition = GetParent(currentPosition);
// 2. 만약, 힙이 꽉차있다면, 용량 증가
if (H->capacity == H->usedSize) {
H->capacity *= 2;
H->nodes = (HeapNode*)realloc(H->nodes, sizeof(HeapNode) * H->capacity);
}
// 3. 최고 깊이 최 우측 노드에 새 노드 삽입
H->nodes[currentPosition].data = newData;
// 4. 힙 순서 속성 유지할 때까지 비교 반복
// 탈출 조건 : 자신이 루트 노드가 된다(인덱스 0). 또는 자신의 값이 부모보다 크거나 같다.
while (currentPosition != 0 && H->nodes[currentPosition].data < H->nodes[parentPosition].data) {
SwapNodes(H, currentPosition, parentPosition); // 자리 교환
currentPosition = parentPosition; // 1번 처럼 인덱스 갱신
parentPosition = GetParent(currentPosition);
}
// 5. 용량 증가
H->usedSize++;
return;
}
힙의 최소값 삭제하기
최소값은 항상 루트노드가 가지고 있다.
함수는 일단 루트노드의 최소값을 기억해 두는 것으로 시작한다.
루트노드 자리에 최고 깊이 최 우측 노드를 복사해서 옮겨둔다.
새로 온 노드는 힙 순서 속성을 만족할 때 까지 자신의 자식 노드와 비교하여 교환을 반복한다.
void DeleteMin(Heap* H, HeapNode* root) {
int parentPosition = 0; // 루트노드 자신이 부모로 시작. 루트니까 인덱스 0.
int leftPosition = 0;
int rightPosition = 0;
// root에 최소값을 저장해둔다.
memcpy(root, &H->nodes[0], sizeof(HeapNode));
memset(&H->nodes[0], 0, sizeof(HeapNode));
H->usedSize--; // 최우측 노드 인덱스
SwapNodes(H, 0, H->usedSize); // 루트 자리에 최고 깊이 최우측 노드를 옮겨온다.
leftPosition = GetLeftChild(0); // 루트 노드의 왼쪽 자식, 오른쪽 자식 인덱스
rightPosition = leftPosition + 1;
while (1) { // 힙 순서 속성을 만족할 때 까지 루트는 자기 자식과 비교한다.
int selectedChild = 0; // 1. 부모노드(루트노드)와 교환할 노드의 인덱스를 찾아본다
if (leftPosition >= H->usedSize) {
// 실제 노드 개수보다 왼쪽자식 인덱스가 같거나 크다
// 유의점 : 노드 인덱스는 0부터 시작. 사용량은 1부터 시작
// 즉, 루트노드는 잎노드가 된 상황.
break;
}
if (rightPosition >= H->usedSize) {
// 사용 인덱스보다 오른쪽 자식인덱스가 크다
// 즉, 루트노드에게 오른쪽 자식은 존재하지 않고 왼쪽자식만 있는것임.
selectedChild = leftPosition; // 타겟은 왼쪽자식
}
else { // 양쪽 자식 존재
if (H->nodes[leftPosition].data < H->nodes[rightPosition].data) {
// 왼쪽 자식이 작다. 타겟은 왼쪽자식
selectedChild = leftPosition;
}
else { // 오른쪽 자식이 작다. 타겟은 오른쪽 자식
selectedChild = rightPosition;
}
}
// 2. 값을 보고 교환할 필요가 있는지 확인한다
if (H->nodes[selectedChild].data < H->nodes[parentPosition].data) {
SwapNodes(H, selectedChild, parentPosition);
parentPosition = selectedChild; // 타겟이 새 부모가 된다.
}
else {
break;
}
// 3. 왼쪽 자식, 오른쪽 자식 인덱스를 갱신한다.
leftPosition = GetLeftChild(parentPosition);
rightPosition = leftPosition + 1;
}
// 4. 용량의 반 이하만 쓰고 있다면, 힙 용량을 반으로 줄인다.
if (H->usedSize < (H->capacity/2)) {
H->capacity /= 2; // 줄일 용량
H->nodes = (HeapNode*)realloc(H->nodes, sizeof(HeapNode) * H->capacity);
}
}
힙 예제 전체 코드
헤더파일 heap.h Insert() 와 Delete()를 포함한 함수가 구현된 heap.cpp 테스트 해보는 heap_test.cpp
