dlsxor48   2달 전

1946번_신입사원 문제 

작성해본 알고리즘은 정확히 동작하는 것 같은데 계속 '시간초과' 판정이 뜹니다. 어느 부분에서 시간을 줄여야 할지 도저히 감이 잡히질 않네요ㅠㅜ 어떤분 말씀으로는 3중 for문을 사용하는 경우에 대게 시간초과가 뜬다고 하시던데, 제가 생각한 로직구현에는 3중 for문이 들어가지 않고 작성하는 방법이 떠오르지 않아서 답답하네요ㅠ

시간 단축 방법이나, 소스 내 잘못된 부분에 관해 조언 부탁드립니다.


*로직

서류 점수(resume) 등수와 면접 점수(interview) 등수 두가지 변수를 가지는 구조체에서, 서류 점수 등수를 기준으로 오름차순 정렬을 수행합니다.

그 후 서류 점수 2등부터 꼴등인 신입사원까지 순차적으로 for문을 돌며, 본인보다 높은 서류 등수를 가진 신입사원들의 면접 등수를 본인의 면접 등수와 비교합니다. 이 때 본인 보다 높은 서류 등수를 가진 모든 신입사원들의 면접 등수보다 높은 경우에만 신입사원(cnt)이 추가되도록 tempCnt변수를 이용하였습니다.

중첩된 for문(2nd j for문) 내부의 if문들 중 일부는 시간단축을 위해 추가하였습니다.


고수님들의 많은 조언 부탁드려요~


- 그 후 서류 점수 2등부터 꼴등인 신입사원까지 순차적으로 for문을 돌며, 본인보다 높은 서류 등수를 가진 신입사원들의 면접 등수를 본인의 면접 등수와 비교합니다. 이 때 본인 보다 높은 서류 등수를 가진 모든 신입사원들의 면접 등수보다 높은 경우에만 신입사원(cnt)이 추가되도록 tempCnt변수를 이용하였습니다.


이 부분에서, '면접 등수가 본인보다 높은 서류 등수를 가진 모든 신입사원들의 면접 등수보다 높다' 를, '면접 등수가 본인보다 높은 서류 등수를 가진 신입사원들의 면접 등수들 중 가장 높은 등수보다 높다' 라고 생각해도 무방하다는 점에 착안하면, 현재까지 확인한 사원들 중 가장 높은 면접 등수를 가진 사원 단 한 명에 대한 면접 등수만 저장하며 비교해나가는 방식으로 내부의 비교 for문을 통째로 지우는 것이 가능합니다.


또한, 입력량이 많은 문제이기 때문에 cin, cout이 시간 초과를 발생시킬 우려가 있습니다. scanf/printf를 사용하시거나,

ios::sync_with_stdio(false);를 메인 함수 내에 호출하신 뒤 cin/cout을 사용하는 방식을 택해보세요.

dlsxor48   2달 전

정말 좋은방법이네요^^ 불필요한 비교 for문이 있었군요..ㅎㅎ

말씀해주신 조언들도 참고해서 다시 작성해봐야겠습니다.

좋은 답변 감사드립니다~ 수고하세요ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.