[코드트리] 해적 선장 코디 (코드트리, 2025 하반기 오전 2번, B형)

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

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

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

 
공격 준비
 
공격력이 가장 높고, 같은 공격력인 경우 id가 작은 선박을 구하기 위해 우선순위 큐를 사용한다.
우선순위 조건은 다음과 같다.

SHIP heap[100100];
int hn;

int isPriority(SHIP a, SHIP b)
{	
	if (a.pw != b.pw) return a.pw > b.pw; // 공격력이 큰 선박 우선	
	return a.id < b.id; // id가 작은 선박 우선
}

 
선박의 정보는 다음과 같이 관리한다.

struct SHIP
{
	int id;
	int pw;
	int r;
	int last;
};

 
또한 선박 정보의 갱신을 위해 unordered_map을 이용한다.

unordered_map<int, SHIP> shipInfo;

 
공격 준비 코드는 다음과 같다.
최초 공격 시간은 재장전 시간 (1 ~ 10)보다 작은 값으로 설정해서 초기화한다.

void input()
{
	scanf("%d", &N);

	timer = hn = 0;

	for (int i = 0; i < N; i++)
	{
		int id, p, r;

		scanf("%d %d %d", &id, &p, &r);

		SHIP x = { id, p, r, -10 };

		push(x);

		shipInfo[id] = x;
	}
}

---

지원요청
 
타이머를 증가하고, 새로운 선박의 정보를 우선순위 큐에 넣고 unordered_map에 추가한다.

void request(int id, int p, int r)
{
	timer++;

	SHIP x = { id, p, r, -10 };
	
	push(x);

	shipInfo[id] = x;
}

---

함포 교체
 
우선순위 큐에서 id를 찾아서 갱신하는 대신, shipInfo만 갱신하고, 새로운 선박을 우선순위 큐에 추가한다.
우선순위 큐에서 pop을 한 선박이 shipInfo의 pw와 값이 같은지 확인해서 최신 정보를 가지는 선박인지 확인할 수 있다.

void change(int id, int pw)
{
	timer++;

	shipInfo[id].pw = pw;

	push({ id, pw, 0, -100 });
}

---

공격 명령
 
공격 가능한 최대 5개의 선박을 구해야 한다.
pop된 선박과 shipInfo의 pw가 다르다면 무시한다. (이중 우선순위 큐 참고)
그리고 현재 timer를 체크해서 공격이 불가능하다면 임시 배열에 추가한다.
공격이 가능하다면 damage를 누적하고, shipInfo의 last를 갱신하고 공격한 선박을 따로 배열로 관리한다.
공격 불가능한 선박과 정보가 갱신된 선박 모두 우선순위 큐에 다시 추가하고 결과를 출력하면 된다.

void attack()
{
	timer++;

	int tcnt, acnt, damage;
	
	tcnt = acnt = damage = 0;

	while (hn != 0 && acnt < 5)
	{
		SHIP tmp = pop();
		
		int power = tmp.pw;
		int id = tmp.id;
		SHIP ship = shipInfo[id];

		// 현재 정보와 다른 경우는 제거
		if (ship.pw != power) continue;

		if (timer < ship.r + ship.last) // 공격 불가
		{
			tmpShip[tcnt++] = ship;
			continue;
		}

		damage += ship.pw;
		shipInfo[id].last = timer;
		attackShip[acnt++] = ship;
	}

	for (int i = 0; i < tcnt; i++) push(tmpShip[i]);
	for (int i = 0; i < acnt; i++) push(attackShip[i]);

	printf("%d %d ", damage, acnt);

	for (int i = 0; i < acnt; i++)
		printf("%d ", attackShip[i].id);

	putchar('\n');
}

---

전체 코드는 다음과 같다.

#include <stdio.h>
#include <unordered_map>

using namespace std;

#define INF (0x7fff0000)

#define INIT (100)
#define REQUEST (200)
#define CHANGE (300)
#define ATTACK (400)

int T;
int N;
int timer;

struct SHIP
{
	int id;
	int pw;
	int r;
	int last;
};

unordered_map<int, SHIP> shipInfo;
SHIP tmpShip[10000];
SHIP attackShip[5];
SHIP heap[100100];
int hn;

int isPriority(SHIP a, SHIP b)
{	
	if (a.pw != b.pw) return a.pw > b.pw; // 공격력이 큰 선박 우선	
	return a.id < b.id; // id가 작은 선박 우선
}

SHIP pop()
{
	SHIP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn].pw = -1;
	heap[hn--].id = 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(SHIP x)
{
	SHIP 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", &N);

	timer = hn = 0;

	for (int i = 0; i < N; i++)
	{
		int id, p, r;

		scanf("%d %d %d", &id, &p, &r);

		SHIP x = { id, p, r, -10 };

		push(x);

		shipInfo[id] = x;
	}
}

void request(int id, int p, int r)
{
	timer++;

	SHIP x = { id, p, r, -10 };
	
	push(x);

	shipInfo[id] = x;
}

void change(int id, int pw)
{
	timer++;

	shipInfo[id].pw = pw;

	push({ id, pw, 0, -100 });
}

void attack()
{
	timer++;

	int tcnt, acnt, damage;
	
	tcnt = acnt = damage = 0;

	while (hn != 0 && acnt < 5)
	{
		SHIP tmp = pop();
		
		int power = tmp.pw;
		int id = tmp.id;
		SHIP ship = shipInfo[id];

		// 현재 정보와 다른 경우는 제거
		if (ship.pw != power) continue;

		if (timer < ship.r + ship.last) // 공격 불가
		{
			tmpShip[tcnt++] = ship;
			continue;
		}

		damage += ship.pw;
		shipInfo[id].last = timer;
		attackShip[acnt++] = ship;
	}

	for (int i = 0; i < tcnt; i++) push(tmpShip[i]);
	for (int i = 0; i < acnt; i++) push(attackShip[i]);

	printf("%d %d ", damage, acnt);

	for (int i = 0; i < acnt; i++)
		printf("%d ", attackShip[i].id);

	putchar('\n');
}

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

		scanf("%d", &COMMAND);

		if (COMMAND == INIT) input();
		else if (COMMAND == REQUEST)
		{
			int id, p, r;

			scanf("%d %d %d", &id, &p, &r);

			request(id, p, r);
		}
		else if (COMMAND == CHANGE)
		{
			int id, pw;

			scanf("%d %d", &id, &pw);

			change(id, pw);
		}
		else if (COMMAND == ATTACK)
		{
			attack();
		}
	}

	return 0;
}