시간복잡도 역산과 stringstream 입력 파싱

코딩 테스트에서 시간을 잃는 지점은 크게 둘이다. 복잡도를 잘못 잡아 제출 후 시간 초과로 죽거나, 입력 파싱을 손으로 짜다 풀이 전에 시간을 태우거나. 이 글에서는 그 둘을 각각 막는 방법을 이야기하려 한다 — 앞부분은 입력 최대값에서 허용 복잡도를 역산하는 기준, 뒷부분은 stringstream으로 공백·구분자·진법 파싱을 표준 라이브러리에 넘기는 방법이다.

알고리즘 효율성 — 연산 횟수로 성능을 읽는다

알고리즘 성능은 절대 시간이 아니라 연산 횟수 기준으로 판단한다. PC 성능은 제각각이지만, 입력이 커질수록 결국 연산 수의 증가 추이가 성능을 결정하기 때문이다. 반복문 횟수만이 아니라 비교·대입·산술 연산이 전부 비용이고, 대용량 배열 비교 같은 것도 무시할 수 없다 — 실제 코테에서 자주 걸리는 지점이다.

입력이나 탐색 위치에 따라 최선/최악의 경우가 갈리는데, 코테는 항상 최악 기준(Big-O)으로 판단한다. 빅오는 점근적 표기법(입력이 충분히 클 때의 증가 추세만 보고 상수·저차항을 제거하는 방식)으로 최악 기준의 상한을 나타내며, 최고차항만 남겨 가장 타이트한 상한을 고른다. 예: 3N²+2N → O(N²).

시간을 가늠할 때는 1초 ≈ 1억 연산으로 잡는다. N=1,000,000이면 O(N log N) 이하로 설계해야 한다는 계산이 나온다.

복잡도별 대표 패턴은 코드로 봤다.

O(N) — 선형 탐색: 배열 전수 탐색이라 최악 O(N).

for (int i = 0; i < size; i++)
    if (arr[i] == target) return i;

O(N²) — 2차원 순회: 이중 반복문.

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += arr[i][j];

O(log N) — 절반 감소: 반복마다 범위가 절반으로 줄어 로그로 증가.

while (N > 1) { N /= 2; }

O(2^N) — 모든 조합: 완전 탐색/브루트포스, N이 커지면 폭발적으로 증가.

for (int a = 0; a < 2; a++)
    for (int b = 0; b < 2; b++)
        for (int c = 0; c < 2; c++) {}

적용 전략은 하나로 요약된다. 입력 최대값을 먼저 확인하고 허용 복잡도를 역산한 뒤 구현에 들어간다. 시간복잡도 상한을 정하는 게 구현보다 먼저다.

입출력 데이터 다루기 — 파싱은 표준 라이브러리에 맡긴다

코딩테스트는 알고리즘보다 입력 파싱에서 시간을 잃는 경우가 많다. 공백·구분자·진법 등 다양한 형식을 빠르게 처리하는 습관이 필요하다.

먼저 반올림/올림/내림. round / ceil / floor의 차이를 정확히 알아야 하는데, 특히 음수 처리 방식이 달라 예외 케이스 대비가 필요하다. round는 0.5를 away from zero(0에서 먼 쪽) 기준으로 반올림한다.

round(-2.5); // -3

ceil은 항상 위쪽 정수, floor는 항상 아래쪽 정수다.

ceil(-3.2);  // -3
floor(-3.7); // -4

stringstream은 문자열을 입력 스트림처럼 처리할 수 있게 해준다. cin과 동일한 >> 방식으로 데이터를 추출한다.

공백 기준 분리는 >> 연산자가 자동으로 토큰화해 준다.

stringstream ss;
ss >> a >> b >> c;

특정 문자 기준 분리는 getline + 구분자.

while (getline(ss, token, ',')) {}

진법 변환도 stringstream으로 된다. 10진수 → 16진수는 hex 조작자를 넣어 출력하고,

ss << hex << decimal;

16진수 → 10진수는 hex 설정 후 >>로 파싱한다.

ss >> hex >> decimal;

결론: 파싱/형변환을 직접 구현하지 말고 표준 라이브러리를 활용한다. 시간이 줄고, 실수가 줄고, 가독성이 좋아진다.

핵심 요약 — 코테 성능은 절대 시간이 아니라 연산 횟수(최악 기준 Big-O)로 판단하고, 1초 ≈ 1억 연산 기준으로 입력 최대값에서 허용 복잡도를 역산한 뒤 구현에 들어간다는 순서를 잡았다. 입력 파싱은 stringstream 등 표준 라이브러리로 처리해 시간과 실수를 줄인다.