배열 저장 전략 — 단일 순회·고정 배열·인덱스 마킹

배열 기초 문제 세 개를 이어서 풀었는데, 난이도는 비슷한데도 저장 전략이 셋 다 달랐다. 하나는 배열을 아예 안 쓰고, 하나는 고정 배열을 쓰고, 하나는 값을 인덱스로 써서 정렬까지 생략한다. 이 글에서는 그 갈림길을 문제 조건에서 어떻게 읽어내는지를 이야기하려 한다. 문제별 풀이 전문은 백준 10818·백준 10807·백준 5597에 따로 정리돼 있다.

BOJ 10818 | 최솟값과 최댓값

최종코드

N개의 정수가 주어졌을 때 최솟값과 최댓값을 출력하는 문제다.

값을 전부 배열에 담을 필요가 없다는 게 포인트였다. 첫 번째 값으로 minVal, maxVal을 둘 다 초기화한 뒤, 이후 값을 읽으면서 조건문으로 바로 비교해 갱신했다. 배열 없이 O(1) 공간으로 끝난다. std::min/std::max 대신 직접 조건문을 쓴 건 함수 호출을 줄이려는 선택이었다.

항목	내용
ios::sync_with_stdio(false)	C와 C++ 스트림 동기화 해제로 입출력 속도 향상
cin.tie(nullptr)	cin과 cout 묶음 해제로 불필요한 flush 방지
단일 순회 (Single Pass)	배열 저장 없이 입력과 동시에 min/max 갱신

• 시간복잡도: O(N)
• 공간복잡도: O(1)

---

BOJ 10807 | 개수 세기

최종코드

N개의 정수 중 특정 값 v가 몇 번 등장하는지 세는 문제다.

이번엔 10818과 달리 배열 저장이 필요했다. 찾을 값 v가 입력의 마지막에 주어지기 때문에, 숫자들을 먼저 담아 두고 나중에 비교해야 한다. N이 100 이하로 작고 고정이라 vector 대신 스택 고정 배열 int arr[100]을 썼고, 저장 후 한 번 순회하며 arr[i] == v를 카운팅했다.

항목	내용
ios::sync_with_stdio(false)	빠른 입출력
cin.tie(nullptr)	불필요한 flush 방지
고정 크기 배열 int arr[100]	힙 할당 없이 스택에서 처리, vector 대비 오버헤드 없음
선형 탐색	정렬 없이 O(N) 순회로 카운팅

• 시간복잡도: O(N)
• 공간복잡도: O(N) (고정 크기 100이므로 사실상 O(1))

---

BOJ 5597 | 과제 안 내신 분..?

최종코드

1~30번 중 28명의 번호가 주어질 때, 제출하지 않은 2명의 번호를 오름차순으로 출력하는 문제다.

bool submitted[31] 배열을 출석부처럼 썼다. 입력받은 번호를 submitted[x] = true로 마킹하고, 마킹이 끝나면 1부터 30까지 순서대로 돌면서 false인 인덱스를 출력한다. 인덱스 순서 자체가 오름차순이라 별도 정렬이 필요 없다는 게 이 풀이의 핵심이다.

항목	내용
ios::sync_with_stdio(false)	빠른 입출력
cin.tie(nullptr)	불필요한 flush 방지
bool arr[31] = {}	0(false)으로 일괄 초기화되는 C++ 값 초기화
인덱스 마킹 (Index Marking)	해시처럼 번호를 인덱스로 직접 사용, 탐색 O(1)
순차 탐색으로 정렬 대체	1~30 순서 순회로 별도 정렬 없이 오름차순 출력

• 시간복잡도: O(1) (입력 28회 + 탐색 30회 = 상수)
• 공간복잡도: O(1) (고정 크기 31 배열)

---

정리 — 조건에서 전략을 읽는 표

기법	설명	적용 문제
ios::sync_with_stdio(false) • cin.tie(nullptr)	대용량 입력 시 속도 개선 필수	전체 공통
고정 크기 배열	N이 작고 고정일 때 vector 대신 사용, 힙 할당 오버헤드 없음	10807, 5597
인덱스 마킹	값을 인덱스로 직접 사용해 O(1) 접근 (해시 테이블 원리)	5597
단일 순회 (Single Pass)	배열 저장 없이 입력과 동시에 처리	10818
정렬 대신 순차 탐색	범위가 작고 고정일 때 정렬 없이 오름차순 보장	5597

핵심 요약 — 문제 조건에 따라 저장 전략이 달라진다는 것. 비교 대상이 입력 중에 확정되면 배열 없이 단일 순회로 되고, 마지막에 주어지면 저장이 필요하며, 값의 범위가 작으면 인덱스 마킹으로 정렬까지 생략할 수 있다.