[java] sw expert academy - 점심 식사시간

문제

SWEA - 점심 식사시간
모든 사람이 계단을 통해 이동을 완료하는 최소 시간을 구하는 문제.

풀이

아 정말 생각보다 시간이 오래걸렸다.. 하..
49/50일때의 허무함이란..ㅋ

계단은 반드시 2개이며 사람의 수는 최대 10이다
먼저, 순열을 사용해서 각 인원이 1번계단을 이용할 지, 2번계단을 이용할 지 구했다
각 순열의 결과에 따라 계단을 내려갔을 때 걸리는 시간 중 최소 시간을 구하면 된다

우선 최소시간을 구할 때 Info라는 객체를 만들어 사용했다
계단입구에 도착했다고 가정하고 값을 저장했다

A라는 사람이 1번 계단을 사용한다고 하면,
Info(int time, boolean start, int no)
time - 시간(초기값 :A와 1번 계단과의 거리)
start - 계단을 내려가기 시작한 여부
no - 사용하는 계단의 번호

이 Info는 info라는 우선순위 큐에 시간순으로 정렬되어 담겨있다

계단을 이용하는 사용자는 time+1을 결과에 저장한다

계단을 이용중이지 않은 사용자는
계단을 내려갈 수 있으면 start=true하고 계단 내려가는 시간까지 더해서
다시 큐에 추가한다
계단 이용자의 수를 1 증가시킨다
계단을 내려갈 수 없으면 시간을 1 증가시킨다(지연시간)
다시 큐에 추가한다

Info가 비워질 때 까지 반복한다

문제에서 사람과 계단까지의 거리는 dfs, bfs쓸 필요없이 문제에 나와있는 공식을 이용하면 된다
다만 가장 많이 틀리는 원인은 A 사용자가 계단이용 끝냄과 동시에 B사용자가 계단을 내려갈 경우 인 것 같다

계단은 3명이라는 이용자 제한이 있어서 A, D, E가 사용중이고
A가 계단 사용을 끝냄과 동시에 B 사용자가 계단을 내려가려 할 때 처리를 해줘야한다

B 사용자가 진입하기 이전에 A 사용자가 계단 이용을 끝내야 3명 이용 규칙을 지킬 수 있다
B 사용자가 A 사용자 차례보다 먼저라면 대기시간이 1 증가하게 된다(최소 시간 X)

info객체를 정렬할 때 time 기준으로 정렬하는데,
time이 같은 경우 계단 사용중인 사람을 우선으로 정렬했다

소스코드(Info 클래스)

class Info implements Comparable<Info> {
	int time;
	boolean start;
	int no;

	public Info(int time, boolean start, int no) {
		super();
		this.time = time;
		this.start = start;
		this.no = no;
	}

	@Override
	public int compareTo(Info o) {
		if (this.time == o.time) {
			return this.time + (this.start ? 0 : 1) - o.time + (o.start ? 0 : 1);
		}
		return this.time - o.time;
	}

}

소스코드(계단 내려가는 부분)

	private static void doSimulation() {
		PriorityQueue<Info> info = new PriorityQueue<>();
		for (int i = 0; i < p.length; i++) {
			info.add(new Info(getDist(people.get(i), stairs.get(p[i])), false, p[i])); // 객체 추가
		}

		int max = 0;
		int cnt[] = new int[2]; // 계단 이용자 수 

		while (!info.isEmpty()) {
			Info curr = info.poll();
			if (curr.start) { // 계단 완주
				cnt[curr.no]--;
				max = Math.max(curr.time + 1, max);
			} else {
				if (cnt[curr.no] == 3) { // 모든 계단이 사용중
					curr.time++;
				} else { // 내려갈 수 있어
					cnt[curr.no]++;
					curr.start = true;
					curr.time += stairs.get(curr.no).time;
				}
				info.add(curr);
			}
		}
		ans = Math.min(max, ans);
	}