[TIL] 2026-06-04 — 알고리즘 심화: map·set·문자열·스택 7문제

오후 알고리즘 심화수업에서 자료구조(map·set) → 문자열 인덱스 변환 → 스택 흐름으로 7문제를 풀었다. 관통하는 아이디어: 문자 - 기준문자(c - '0', c - 'a', c - 'A')로 문자를 배열 인덱스로 바꾸는 변환이 거의 모든 문제에서 재등장했다.

오늘 한 일 요약

자료구조 → 문자열 → 스택 순으로 7문제를 풀었다. 숫자 카드(map)·회사 사람(set)·첫끝 글자·숫자의 합·알파벳 찾기·다이얼(구현 vs 그리디)·괄호(스택 vs 카운터). 마지막으로 심화 과제(백준 2852 ‘NBA 농구’ 시뮬레이션)를 풀어 구글 폼에 제출했다.

1. 숫자 카드 (백준 10815) — map

상근이가 가진 카드를 등록해두고, 질의마다 존재 여부를 0/1로 출력.

map<int, bool> m;
for (int i = 0; i < n; i++) { int a; cin >> a; m[a] = true; }
// 질의
cout << m.count(b) << ' ';   // 있으면 1, 없으면 0

• map::count(key) 는 key가 있으면 1, 없으면 0 — 출력 형식과 그대로 일치해 if 불필요.
• map은 RB-Tree라 삽입·조회 O(log N). 값 범위가 -1000만~1000만이라 배열 인덱싱은 부담 → map/set이 자연스럽다.
• 존재 여부만 필요하면 set이 더 정석, unordered_map/unordered_set은 평균 O(1)로 더 빠르다.

2. 회사에 있는 사람 (백준 7785) — set + 역순 출력

enter면 등록, leave면 제거. 마지막에 남은 사람을 사전 역순으로 출력.

set<string> s;
if (s2 == "enter") s.insert(s1);
else               s.erase(s1);
// 역순 출력
for (auto it = s.rbegin(); it != s.rend(); ++it)
    cout << *it << endl;

• set은 오름차순 자동 정렬 → rbegin()/rend()로 뒤에서부터 순회하면 역순 출력이 공짜.
• *it(set) vs it->first(map): set 원소는 값 하나(string)라 *it. map은 원소가 pair라 it->first(키)·it->second(값).
• ++it vs it++: for 증감식에선 반환값을 안 쓰므로 결과 동일. 후위(it++)는 복사본을 만들어 객체 반복자에서 손해 → 관용적으로 전위(++it) 권장.

3. 첫 글자 + 마지막 글자 — 문자열 인덱싱

테스트 케이스마다 문자열의 첫·마지막 글자를 이어 출력. 한 글자(O)는 OO.

while (t--) {
    string s; cin >> s;
    cout << s.front() << s.back() << endl;   // = s[0], s[s.size()-1]
}

• while (t--): 현재 t를 조건으로 쓰고(후위) 1 감소 → T번 정확히 반복. while(--t)는 T-1번이라 부족.
• front()/back() ↔ s[0]/s[s.size()-1] 동일.

4. 숫자의 합 (백준 11720) — 문자→숫자 변환

숫자들이 공백 없이 붙어 들어옴. 자릿수가 매우 길 수 있어 문자열로 받아 각 자리를 더한다.

int sum = 0;
for (int i = 0; i < n; i++) sum += s[i] - '0';   // 문자 → 숫자

• s[i] - '0': '5'(아스키 53) - '0'(48) = 5. 정수형으로 받으면 오버플로로 틀린다. 문자열은 길이 무관하게 안전.
• 범위 기반 for문 for (char c : s) sum += c - '0'; 로도 동일.

5. 알파벳 찾기 (백준 10809) — 배열 vs find+캐스팅

a~z 각 알파벳이 처음 등장하는 위치, 없으면 -1.

// (A) 배열 방식
int a[26]; for (int i = 0; i < 26; i++) a[i] = -1;
for (int i = 0; i < (int)s.size(); i++) {
    int idx = s[i] - 'a';            // 'a'~'z' → 0~25
    if (a[idx] == -1) a[idx] = i;    // 처음 등장할 때만 기록
}

// (B) find + (int) 캐스팅 트릭
cout << (int)s.find(alpa[i]) << ' ';

• string::find는 못 찾으면 npos(unsigned long long 최댓값) 반환. (int)로 캐스팅하면 비트가 잘려 -1이 되어 “없으면 -1”이 if 없이 해결.
• ⚠️ 캐스팅 없이 if (s.find(x) == -1)로 비교하면 틀린다(unsigned 비교). (int) 캐스팅 또는 == string::npos로 비교해야 한다.
• 복잡도: 배열 O(길이) vs find O(26×길이). 입력이 짧아(≤100) 둘 다 무방.

6. 다이얼 (백준 5622) — 구현(시뮬레이션) vs 그리디

옛날 다이얼 전화기: 숫자 n을 돌리는 데 n+1초. 각 알파벳의 다이얼 숫자를 찾아 시간 합산.

// 룩업 테이블에 "최종 초"를 직접 저장 (권장)
int a[26] = { 3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10 };
int sum = 0;
for (char c : s) sum += a[c - 'A'];

• P~S(4개)는 8초, W~Z(4개)는 10초라 각각 4번씩 → 총 26칸. 다이얼 숫자를 저장하고 +1하기보다 최종 답을 미리 테이블에 박아두면 변환 단계가 사라진다.
• 그리디와 헷갈리는 점 — 그리디는 선택지가 있고 최적을 찾아야 하며 정당성 증명이 필요(거스름돈·회의실 배정). 다이얼은 각 글자의 숫자가 고정 → 선택 없음. 규칙대로 변환·합산하는 구현(시뮬레이션) 문제. 판별 기준: “무엇을 고를지 고민되면 그리디, 규칙대로 변환·합산이면 구현.”

7. 괄호 (백준 9012) — 스택 vs 카운터

VPS(올바른 괄호 문자열) 판정.

// 스택 방식
stack<char> s;
for (char c : str) {
    if (c == '(') s.push(c);
    else {
        if (!s.empty() && s.top() == '(') s.pop();
        else return "NO";          // 닫을 게 없는데 ')'
    }
}
return s.empty() ? "YES" : "NO";   // 다 짝지어졌으면 YES

• ⚠️ 마지막 검사는 입력 str이 아니라 스택 s 의 empty() — str.empty()로 쓰면 항상 NO가 나오는 버그(변수명 혼동 주의).
• 카운터(balance) 방식 — 괄호가 한 종류라 스택에 쌓이는 게 전부 (로 동일 → 개수만 세면 됨. balance++/--, balance < 0이면 NO, 끝에 balance == 0이면 YES. push/pop을 숫자 하나로 압축, 메모리 O(1).
• 4949 균형잡힌 세상과의 차이 — ()와 [] 두 종류라 “가장 최근에 연 괄호와 짝이 맞는지”를 봐야 함 → 스택 필수(카운터로는 불가).

	9012 괄호	4949 균형잡힌 세상
괄호 종류	1종	2종
풀이	카운터로 충분	스택 필요

C++ 문법 메모 (오늘 짚은 것)

• #define endl '\n' — std::endl은 줄바꿈+flush라 느림. '\n'은 flush 없이 줄바꿈만 → 빠름.
  • ⚠️ #define endl '\n';처럼 세미콜론을 넣으면 안 됨. cout << endl << x;가 cout << '\n'; << x;로 깨진다.
• map::count = 0 또는 1 (중복 불가).
• *it(set) vs it->first/it->second(map).
• ++it vs it++ — 결과 같을 땐 전위 권장(복사 비용).
• while (t--) = T번 반복 관용구.
• 인덱스 변환 관용구: c - '0'(숫자), c - 'a'/c - 'A'(알파벳).
• string::npos + (int) 캐스팅 = -1.

심화 과제

• 백준 2852 ‘NBA 농구’ — 두 팀의 득점 시각을 보고 각 팀이 이기고 있던 시간의 총합을 구하는 시뮬레이션. 풀어서 구글 폼 제출.

오늘 배운 것 정리

1. 인덱스 변환 관용구가 전체를 관통 — c - '0'/c - 'a'/c - 'A'로 문자를 0-기반 인덱스로 바꾸는 게 카드·알파벳 찾기·다이얼·숫자의 합을 모두 관통했다.
2. 존재 여부 조회는 map::count/set — 값 범위가 넓어 배열 인덱싱이 부담일 때 map/set이 자연스럽고, count가 0/1을 돌려줘 if 없이 출력과 맞아떨어진다.
3. set 역순 출력은 rbegin()/rend()로 공짜 — 자동 정렬된 컨테이너를 뒤에서부터 순회.
4. 긴 숫자는 문자열로 받아 자리합 — 정수형은 오버플로. s[i] - '0'로 자리수를 더한다.
5. string::npos + (int) 캐스팅 = -1 — “없으면 -1” 출력을 if 없이 처리하는 트릭. 단 unsigned 비교 함정 주의.
6. 구현 vs 그리디 판별 — “무엇을 고를지 고민되면 그리디, 규칙대로 변환·합산이면 구현(시뮬레이션).” 다이얼은 선택지가 없어 구현 문제.
7. 괄호 1종은 카운터, 2종은 스택 — 종류가 하나면 개수만 세는 카운터로 O(1) 메모리에 풀리지만, 두 종류 이상이면 “최근에 연 괄호”를 봐야 해 스택이 필수다.