3015번 - 오아시스 재결합
제출번호 : 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까지 내린 상황인데도 정답처리 되었습니다.
엣지 케이스 데이터가 추가되면 좋을 것 같아 말씀 남깁니다 ..
아래는 통과된 코드입니다.
재채점했습니다.
댓글을 작성하려면 로그인해야 합니다.
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까지 내린 상황인데도 정답처리 되었습니다.
엣지 케이스 데이터가 추가되면 좋을 것 같아 말씀 남깁니다 ..
아래는 통과된 코드입니다.