PS 시나브로

문제 : https://www.acmicpc.net/problem/27516

문제 요약 : 특정 속도로 던졌을 때 맞출 수 있는 과녁의 최대 개수 출력

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_27516.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long gcd(long long lA, long long lB)
{
	if (lB % lA == 0) return lA;
	return gcd(lB % lA, lA);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long lX, lY;
	cin >> lX >> lY;

	vector<pair<long long, long long>> vecMinus;
	vector<pair<long long, long long>> vecPlus;

	int iN;
	cin >> iN;
	while (iN--)
	{
		long long lTempX, lTempY;
		cin >> lTempX >> lTempY;

		lTempX -= lX;
		lTempY -= lY;
		if (lTempX == 0 || lTempY >= 0) continue;

		if (lTempX < 0)
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			long long lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecMinus.push_back({ lTempX, lTempY });
		}
		else
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			int lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecPlus.push_back({ lTempX, lTempY });
		}
	}

	int iAns = 0;
	if (vecMinus.size() > 0)
	{
		sort(vecMinus.begin(), vecMinus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});

		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecMinus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecMinus[i].first == vecMinus[i - 1].first && vecMinus[i].second == vecMinus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	if (vecPlus.size() > 0)
	{
		sort(vecPlus.begin(), vecPlus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});
		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecPlus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecPlus[i].first == vecPlus[i - 1].first && vecPlus[i].second == vecPlus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	cout << iAns << "\n";
	return 0;
}

과녁의 위치에서 사격자의 위치를 빼서 상대위치로 변환해준다.

발사자는 x축에 평행하게 던지므로 x값이 0인 경우를 제외 한다.

중력이 작용하기 때문에 y값이 0과 같거나 큰 경우를 제외 한다.

x의 위치가 음수인 경우는 양수인 경우와 동시에 맞출 수 없다.

마찬가지로 양수인 경우는 음수인 경우와 동시에 맞출 수 없다.

그러므로 두개의 집합으로 따로 생각 해 준다.

t(시간) 이후 X와 Y의 좌표는 다음과 같다.

x = v_x * t

y = 0.5 * g * t^2

따라서 v_x의 속도로 발사 했을 때 저 그래프에 있는 과녁은 모두 동시에 맞게 된다.

이것을 확인하기 위해 x를 제곱하여 선형적으로 확인 할 수 있게 한다

즉, x^2/y 값이 같은 경우 동시에 맞는다 이것을 기약분수로 나타내기 위해

유클리드 호제법을 이용해 분모분자를 나누고 기록 해둔다

기록한 값들을 내림차순 혹은 오름차순으로 정리하고

같은 개수를 체크 해 가장 많은 개수가 나온 경우를 출력한다

문제 : https://www.acmicpc.net/problem/7785

문제 요약 : 회사원의 출퇴근 기록을 입력받아 남아있는 사람 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_7785.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        ArrayList<String> enter = new ArrayList<String>();
        ArrayList<String> leave = new ArrayList<String>();
		int n,i,l,r,lsz,rsz;
		n = Integer.parseInt(br.readLine());
		while(n-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			if(st.nextToken().equals("enter")) {
				enter.add(name);
			}else {
				leave.add(name);
			}
		}
		Collections.sort(enter, Collections.reverseOrder());
		Collections.sort(leave, Collections.reverseOrder());
		lsz = enter.size();
		rsz = leave.size();
		l = r = 0;
		while(true) {
			if(l==lsz) break;
			if(r==rsz) {
				for(i=l;i<lsz;i++) sb.append(enter.get(i)+"\n");
				break;
			}
			if(enter.get(l).equals(leave.get(r))) {
				l++;
				r++;
			}else {
				sb.append(enter.get(l++)+"\n");
			}
		}
		System.out.println(sb);
	}
}

출입과 퇴근을 나누어 입력받은 뒤 각각 내림차순 정렬을 시킨 뒤

각각 첫번째원소부터 다음과 같은 방법으로 진행하였다.

출근과 퇴근의 원소값이 같다면 출근과 퇴근을 한 칸 이동한다.

출근과 퇴근의 원소 값이 다르다면 남아있는 사람으로 출력 후 출근을 한 칸 이동한다.

출근 인원을 다 확인했을 경우 종료

퇴근 인원을 다 확인했을 경우 남아있는 출근 인원을 모두 출력 후 종료

예제[변형] )

Baha enter

Askar enter

Baha leave

Artem enter

AAAAA enter

Artem leave

추가 )

문제 출제자의 의도는 위 방법 아닌 HashMap을 이용하여

출퇴근 로그를 기록하고 남은 값들을 내림차순 정렬하여 출력하는 것 같다.

오답노트 )

단순히 우선순위 큐를 이용해 문제를 해결하고자 했지만

출퇴근 로그의 수가 최대 1000000 개 입력될 수 있기 때문에

우선순위큐 삽입/제거 과정에서 시간이 오래 걸려 시간초과를 받은 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n;
		n = Integer.parseInt(br.readLine());
        PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());
		while(n-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String name = st.nextToken();
			if(st.nextToken().equals("enter")) {
				pq.add(name);
			}else {
				pq.remove(name);
			}
		}
		while(!pq.isEmpty()) sb.append(pq.poll()+"\n");
		System.out.println(sb);
	}
}