[코드트리] 가로등 설치 (코드트리, 2025 하반기 오후 2번, B형)

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 
삼성 A형 전체 링크
삼성 B형 전체 링크
 
참고
- B형 필수 : 우선순위 큐 Priority Queue
- BOJ 10825 : 국영수
 
https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/street-light-installation/description

이후 설명 및 입/출력은 링크 참고

 
이 문제는
 
1. 가로등 사이의 거리
2. (가장 왼쪽의 가로등 - 1) * 2,
3. (N - 가장 오른쪽의 가로등) * 2
 
중 가장 큰 값을 구하는 문제다.
 
가장 왼쪽 또는 오른쪽 가로등이 제거될 때, 가로등 index를 갱신하면 2 / 3 번 값을 항상 구할 수 있다.
1.은 우선순위 큐를 이용해서 가장 큰 값을 구하면 된다.
이때, 도로의 정보에 제거된 가로등이 있는 경우는 무시하면 된다.
 
예제 2에 대한 출력에 대해 먼저 정리해보자.

12
100 10 2 1 10       -> 가로등 1 10 설치
400                 -> 10 - 1 = 9가 가장 크므로 9 출력
200                 -> (1 + 10) / 2 = 5.5 -> 6에 가로등 설치 -> 1 6 10
400                 -> 6 - 1 = 5가 가장 크므로 5 출력
200                 -> (1 + 6) / 2 = 3.5 -> 4에 가로등 설치 -> 1 4 6 10
400                 -> 10 - 6 = 4가 가장 크므로 4 출력
200                 -> (6 + 10) / 2 = 8 -> 8에 가로등 설치 -> 1 4 6 8 10
400                 -> 4 - 1 = 3이 가장 크므로 3 출력
300 3               -> 세번째로 설치된 6 삭제 -> 1 4 8 10
400                 -> 8 - 4 = 4가 가장 크므로 4 출력
300 1               -> 첫번째로 설치된 1 삭제 -> 4 8 10
400                 -> 4 - 1 (가장 왼쪽) = 3 → 가장 자리이므로 * 2 = 6 출력

 
왼쪽 가로등과 오른쪽 가로등의 index, 그리고 그 사이의 거리의 절반을 length에 저장한다.
가장 왼쪽의 가로등은 해당 가로등의 위치 - 1 이 저장되고,
가장 오른쪽의 가로등은 N - 가로등의 위치가 저장된다.

struct DISTANCE
{
	float length;
	int left;
	int right;
};

 
가로등의 위치를 lamp에, 그리고 가로등 양 옆에 있는 가로등의 index는 nextIndex와 prevIndex에 저장한다.

int lamp[100100 * 2]; // lamp[가로등 index] = 위치
int nextIndex[100100 * 2];
int prevIndex[100100 * 2];

 
가장 왼쪽의 가로등의 index는 first에 저장하고, 가장 오른쪽의 가로등의 index는 last에 저장한다.
lcnt 변수로 추가될 가로등의 index를 관리한다.

int first, last, lcnt;

 
우선순위 큐의 우선순위 조건은 다음과 같다.

int isPriority(DISTANCE a, DISTANCE b)
{
	if (a.length != b.length) return a.length > b.length;
	return lamp[a.left] < lamp[b.left];	
}

---

마을 상태 확인
 
가로등 위치를 lamp에 저장하고, 가로등 사이의 거리를 우선순위 큐에 추가한다.
그리고 각 가로등의 양 옆을 nextIndex, prevIndex에 저장한다.

void input()
{
	scanf("%d %d", &N, &M);
	for (int m = 1; m <= M; m++)
	{
		int L;

		scanf("%d", &L);

		lamp[m] = L;
	}

	for (int m = 1; m <= M; m++)
	{
		float length = (lamp[m + 1] - lamp[m]) / 2.0f;

		push({ length, m, m + 1 });
	}

	for (int m = 1; m <= M; m++)
	{
		nextIndex[m] = m + 1;
		prevIndex[m] = m - 1;
	}

	first = 1;
	last = M;
	lcnt = M + 1; // 추가될 가로등 시작 index
}

---

가로등 추가
 
가장 긴 도로를 우선순위 큐에서 뽑는다.
이때, 가로등이 제거된 경우 (lamp에 -1로 표기)는 무시한다.
제거되지 않은 경우는 도로를 2개로 나눠서 다시 우선순위 큐에 넣는다.
이때 newPos는 올림 처리를 해야하므로 1을 더하고 2로 나눈다.

void add() 
{
	while (hn) 
	{
		DISTANCE d = pop();

		// 제거된 가로등 무시
		if (lamp[d.left] == -1 || lamp[d.right] == -1) continue;

		int left = d.left;
		int right = d.right;

		int newIndex = lcnt++;
		int newPos = (lamp[left] + lamp[right] + 1) / 2;

		lamp[newIndex] = newPos;

		// left -> newIndex -> right
		nextIndex[left] = newIndex;
		nextIndex[newIndex] = right;

		// left <-- newIndex <-- right
		prevIndex[right] = newIndex;
		prevIndex[newIndex] = left;

		float leftLength = (float)((newPos - lamp[left]) / 2.0f);
		float rightLength = (float)((lamp[right] - newPos) / 2.0f);

		push({ leftLength, left, newIndex });
		push({ rightLength, newIndex, right });

		return;
	}
}

---

가로등 제거
 
주어진 index의 가로등을 삭제 표시 한다. (-1)
그리고 양 옆의 lamp의 index를 구한다.
이때, 제거되는 인덱스가 가장 왼쪽이거나 오른쪽 가로등이면 first / last를 갱신하면 된다.
그리고 nextIndex, prevIndex를 갱신하고, 제거된 가로등 (d)의 양 옆에 있는 가로등의 거리를 우선순위 큐에 추가한다.

void remove(int d)
{
	lamp[d] = -1; // 삭제 표기

	int leftLamp = prevIndex[d];
	int rightLamp = nextIndex[d];

	// 끝처리
	if (d == first) first = rightLamp;
	if (d == last) last = leftLamp;

	// left --> right
	nextIndex[leftLamp] = rightLamp;

	// left <-- right
	prevIndex[rightLamp] = leftLamp;

	float length = (lamp[rightLamp] - lamp[leftLamp]) / 2.0f;

	push({ length, leftLamp, rightLamp });
}

---

최적 위치 계산
 
마찬가지로 제거된 가로등은 무시하고, 해당 정보는 다시 힙에 넣는다.
그리고 이 도로의 길이와 가장 왼쪽 / 오른쪽 가로등에 대한 정보를 비교해서 가장 큰 값을 찾고 리턴하면 된다.

int max(int a, int b) 
{
	return (a > b) ? a : b;
}

int calculate() 
{
	while (hn)
	{
		DISTANCE d = pop();

		// 제거된 가로등은 무시
		if (lamp[d.left] == -1 || lamp[d.right] == -1) continue;

		push(d);

		int leftLength = lamp[first] - 1;
		int rightLength = N - lamp[last];
		int answer = max(leftLength * 2, rightLength * 2);

		answer = max(answer, (int)(d.length * 2));

		return answer;

	}

	return -1; // for debug
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

#define INF (0x7fff0000)

#define INIT (100)
#define ADD (200)
#define REMOVE (300)
#define CALCULATE (400)

int Q;
int N, M;

struct DISTANCE
{
	float length;
	int left;
	int right;
};

DISTANCE heap[100100 * 2];
int hn;

int lamp[100100 * 2]; // lamp[가로등 index] = 위치
int nextIndex[100100 * 2];
int prevIndex[100100 * 2];

int first, last, lcnt;

int isPriority(DISTANCE a, DISTANCE b)
{
	if (a.length != b.length) return a.length > b.length;
	return lamp[a.left] < lamp[b.left];	
}

DISTANCE pop()
{
	DISTANCE ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn].length = -1;
	heap[hn--].left = INF;

	for (int i = 1; i * 2 <= hn;)
	{
		if (isPriority(heap[i], heap[i * 2]) && isPriority(heap[i], heap[i * 2 + 1])) break;
		else if (isPriority(heap[i * 2], heap[i * 2 + 1]))
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(DISTANCE x)
{
	DISTANCE tmp;

	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (isPriority(heap[i / 2], heap[i])) return;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

void input()
{
	scanf("%d %d", &N, &M);
	for (int m = 1; m <= M; m++)
	{
		int L;

		scanf("%d", &L);

		lamp[m] = L;
	}

	for (int m = 1; m <= M; m++)
	{
		float length = (lamp[m + 1] - lamp[m]) / 2.0f;

		push({ length, m, m + 1 });
	}

	for (int m = 1; m <= M; m++)
	{
		nextIndex[m] = m + 1;
		prevIndex[m] = m - 1;
	}

	first = 1;
	last = M;
	lcnt = M + 1; // 추가될 가로등 시작 index
}

void add() 
{
	while (hn) 
	{
		DISTANCE d = pop();

		// 제거된 가로등 무시
		if (lamp[d.left] == -1 || lamp[d.right] == -1) continue;

		int left = d.left;
		int right = d.right;

		int newIndex = lcnt++;
		int newPos = (lamp[left] + lamp[right] + 1) / 2;

		lamp[newIndex] = newPos;

		// left -> newIndex -> right
		nextIndex[left] = newIndex;
		nextIndex[newIndex] = right;

		// left <-- newIndex <-- right
		prevIndex[right] = newIndex;
		prevIndex[newIndex] = left;

		float leftLength = (float)((newPos - lamp[left]) / 2.0f);
		float rightLength = (float)((lamp[right] - newPos) / 2.0f);

		push({ leftLength, left, newIndex });
		push({ rightLength, newIndex, right });

		return;
	}
}

void remove(int d)
{
	lamp[d] = -1; // 삭제 표기

	int leftLamp = prevIndex[d];
	int rightLamp = nextIndex[d];

	// 끝처리
	if (d == first) first = rightLamp;
	if (d == last) last = leftLamp;

	// left --> right
	nextIndex[leftLamp] = rightLamp;

	// left <-- right
	prevIndex[rightLamp] = leftLamp;

	float length = (lamp[rightLamp] - lamp[leftLamp]) / 2.0f;

	push({ length, leftLamp, rightLamp });
}

int max(int a, int b) 
{
	return (a > b) ? a : b;
}

int calculate() 
{
	while (hn)
	{
		DISTANCE d = pop();

		// 제거된 가로등은 무시
		if (lamp[d.left] == -1 || lamp[d.right] == -1) continue;

		push(d);

		int leftLength = lamp[first] - 1;
		int rightLength = N - lamp[last];
		int answer = max(leftLength * 2, rightLength * 2);

		answer = max(answer, (int)(d.length * 2));

		return answer;

	}

	return -1; // for debug
}

int main()
{
	scanf("%d", &Q);
	
	for (int q = 0; q < Q; q++)
	{
		int COMMAND;

		scanf("%d", &COMMAND);

		if (COMMAND == INIT) input();
		else if (COMMAND == ADD)
		{
			add();
		}
		else if (COMMAND == REMOVE)
		{
			int d;

			scanf("%d", &d);

			remove(d);
		}
		else if (COMMAND == CALCULATE)
		{
			printf("%d\n", calculate());
		}
	}

	return 0;
}