[코드카타] 가운데 글자 가져오기

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/12903

문제 요약

• 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요.
• 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다.

내가 제출한 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
    string answer = "";
    int a=0;
    if(s.size()%2==0) 
    {
        a =s.size()/2;
        answer.push_back(s[a-1]);
        answer.push_back(s[a]);
    }
    else 
    {
        a = (s.size()-1)/2;
        answer.push_back(s[a]);                
    }
    return answer;
}

피드백

• a보다는 mid처럼 의미가 드러나는 변수명
  -a =s.size()/2;에서 static_cast<int>를 쓰기보단, 사실 a가 size_t로 가는 게 더 자연스럽다
• substr() 가 더 어울릴 것.

배운 점

• string.substr(시작index, 자를 문자 갯수)
  • s.substr((s.size() - 1) / 2, s.size() % 2 == 0 ? 2 : 1)

알고리즘 라이브 세션

도구 선택 가이드

• 같은 문제를 여러 자료구조로 풀어보기. 성능 차이 체감하기.
• 도구 선택의 세 가지 기준 (성능, 의도 표현, 요구사항 매칭) 을 이해
• 자료구조를 시간 복잡도와 특성 기준으로 비교/정리
• 추상 자료형(ADT) 개념 이해

자료구조	핵심 특성	접근	검색	삽입/삭제
vector	순서 있는 연속 배열	O(1)	O(n)	끝 O(1)
stack	LIFO (후입선출)	top만	—	O(1)
queue	FIFO (선입선출)	front만	—	O(1)
map	key-value, 정렬	O(log n)	O(log n)	O(log n)
set	key만, 정렬	—	O(log n)	O(log n)
unordered_map	key-value, 해시	O(1) 평균	O(1) 평균	O(1) 평균
unordered_set	key만, 해시	—	O(1) 평균	O(1) 평균

같은 문제, 다른 도구

출석부 관리

• 학생 30명
• 특정 학생 출석 여부 확인
• 전체 출석 학생 목록 출력
• 출석한 학생 수 세기
  
• 검색이 핵심이면 set 계열이 와따 - 정렬 필요없으면 unordered_set

Undo 기능

• 문자를 입력하고 Undo로 되돌리는 기능
• vector<char>와 stack<char>
• vector는 임의 접근, 중간 접근 가능(위험함)
• stack은 top만 접근 가능(구조가 실수를 막음)
• 성능이 같다면, 의도를 더 잘 표현하는 도구를 고르자. 주석을 잘 적는게 최고지만...항상 그럴 수 없으니

매출 집계

• 각 상품 몇개 팔렸는지
• 가장 많이 팔린 상품
• 전체 상품 목록을 이름순으로 출력
• vector<pair>, map, unordered_map
• 이름순 출력, 자동 정렬 >>> map

도구 선택의 세 가지 기준

1. 성능 - 이 연산을 얼마나 자주 하는가?
2. 의도 표현 - 읽는 사람이 의도를 알 수 있는가?
3. 요구사항 매칭 - 정렬?중복?key가 있는가?
   

CS 돋보기 - 시간 복잡도

추상 자료형(ADT) "설계도와 제품"

• stack은 사실 개념(규칙)이지, 특정 구현이 아니다. LIFO로 동작하면 그것이 stack. 인터페이스는 같지만, 구현 방식을 회사마다 다르게 할 수 있는 것 -> ADT라고 부름

실전에서는?

• 자료구조 선택은 FPS에 직결. 매 프레임 검색을 O(n) 검색으로 넣으면? 오브젝트 많을수록 선형급수적으로 프레임이 떨어짐.

  • TSet, TMap, TArray 왜 사용하는지 항상 고심할 것.

• 서버 비용에도 직결. 사용자 100만 명의 접속 상태를 관리하고 싶을 때? Vector 쓰면 100만, unordered_set 쓰면 1

• 코테 시간 초과의 가장 흔한 원인.

오늘의 핵심

• 같은 문제라도 자료구조에 따라 성능이 달라진다.
• 도구 선택의 세 가지 기준
• 정답은 없고, 좋은 선택이 있다.