백준 13414번: 수강신청 (JAVA) <List와 Set>

 

문제 해석

 

과목 수강 가능 인원 K와 수강신청 버튼 누른 횟수 L, 수강신청 버튼을 누른 학생의 학번이 입력값으로 주어지고

한 번 누른 학생도 또 누를 수 있다. 대신 그 경우 수강신청 우선순위가 마지막에 누른 시점으로 밀려난다.

수강신청 성공한 학생들을 출력한다.

 

알고리즘

 

버튼을 누른 학생들을 조건을 검사하고 순서대로 List에 담는다.

조건은 List에 버튼을 누른 학생의 학번이 이미 존재하면 해당 학번을 삭제한다.

하지만 List를 사용할 시 ArrayList와 LinkedList 모두 시간 초과가 나온다.

검색해본 결과 Set을 사용해야 함을 알 수 있었다.

조건을 실행할 때 contains() 함수를 사용하는데 List는 O(N), Set은 O(1)의 시간 복잡도가 나오기 때문이다.

 

코드