[프로그래머스(Programmers)][자바(java)] (Lv2) 7주차 - 입실 퇴실 <위클리 챌린지>

 

https://programmers.co.kr/learn/courses/30/lessons/86048

코딩테스트 연습 - 7주차

 

문제 풀이

 

import java.util.*;

public class Solution {

	public static int[] solution(int[] enter, int[] leave) {
		int n = enter.length, l, e, i = 0, j = 0;
		Set<Integer> hs = new HashSet<>();
		int ans[] = new int[n];
		while( i < n ) {
			l = leave[i++];
			if( hs.contains(l) )
				hs.remove(l);
			else {
				while( j < n ) {
					e = enter[j++];
					if( e == l )
						break;
					hs.add(e);
				}
			}
			ans[l-1] += hs.size();
			for( int p : hs )
				ans[p-1]++;
		}
		return ans;
	}
}

 

문제에 나온 예시 중 2번을 대표로 예를 들겠음.

enter	leave	result
[1,4,2,3]	[2,1,3,4]	[2,2,1,3]

순서대로 들어온 사람의 명단과 나간 사람의 명단이 주어짐

사무실에 있는 사람들을 담을 Set<Integer> 생성,
각각의 사람마다 같이 있던 사람들의 명 수를 담을 배열 ans[] 생성 ( 사람의 번호 - 1 => 인덱스 )

leave를 중심으로 볼 때,

set	1	4
enter	1	4	2	3
leave			2	1	3	4

첫 번째로 나간 2는 세 번째로 들어왔다. 따라서 그 전에 들어왔던 1, 4와 같이 있었던 것이 확실해 진다.
( 2와 같이 있었던 사람은 1, 4 두 명 )
( 1과 같이 있었던 사람 중 한 명은 2 )
( 4와 〃 )

set		4
enter	1	4	2	3
leave		2	1	3	4

2, 1이 나간 후 세 번째로 나간 3은 제일 마지막에 들어왔다. 따라서 아직 안 나간 4와 같이 있었을 것이다.
( 3과 같이 있었던 사람은 4 한 명 )
( 4와 같이 있었던 사람 중 한 명은 3 )

이렇게 leave 배열을 순차적으로 탐색하며
그 사람( leave[i] )이 Set에 있다면 빼주고, 없다면 그 전에 들어와 있던 사람( enter[j] )들을 Set에 넣어줌
그 후 ans[leave[i]]에 그 사람과 사무실에 같이 있던 사람들의 명 수( set.size() )를 더해주고,
사무실에 있는 사람들 각각( for( int p : hs ) ) ans[p]에 그 사람도 카운트 해줌

i	leave[i]	set.contains(leave[i])	set	ans[]
0	2	false	[1, 4]	ans[2] += 2; ans[1]++; ans[4]++;
1	1	true	[4]	ans[1] += 1; ans[4]++;
2	3	false	[4]	ans[3] += 1; ans[4]++;
3	4	true	[]	ans[4] += 0;

i	ans[i]
0	2
1	2
2	1
3	3