ccy0111   2년 전

제출번호 : 73019491

알고리즘 분류에 따라 스택으로 푸는데, 스택의 크기를 N에 관계없이 터무늬없게 작게 제한해도 문제가 풀리는 것 같습니다.

c++ 로 작성했으며, 스택에는 두개의 int형 변수를 가진 구조체가 쌓입니다. 첫번째 int에는 키, 두번째 int에는 연속으로 해당 키가 나온 횟수를 나타냈습니다.

가령 입력이 

5

5 5 2 2 5 

면

스택에는 순서대로 (5, 2) , (2, 2) ... 이런 식으로 쌓이게 됩니다.

이론상 입력이 N일때, 스택에는 

최소 1(N명의 키가 전부 같을 때) 스택이 쌓이고

최대 N스택 (N명의 키가 중복없이 내림차순으로 입력될 때) 스택이 쌓여야 합니다. 

이 문제에서 N의 크기는 1 ≤ N ≤ 500,000 이고,

해당 제출번호는 스택의 사이즈를 17까지 내린 상황인데도 정답처리 되었습니다. 

엣지 케이스 데이터가 추가되면 좋을 것 같아 말씀 남깁니다 .. 

아래는 통과된 코드입니다.

startlink   2년 전

재채점했습니다.

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