백준 20920 - 영단어 암기는 괴로워

https://www.acmicpc.net/problem/20920

20920번: 영단어 암기는 괴로워

알고리즘 보다는 C++의 STL 기능을 이해하고 있어야 풀 수 있는 문제

이 문제에서는 문자열이 등장한 횟수를 기록하고 확인해야 하는데 vector만으로는 시간 내에 해결할 수 없다.

따라서 map 컨테이너를 사용한다.

 

먼저 단어를 입력받아, 일정 길이 이상의 단어에 대해
해당 단어가 map에 존재하는 지 확인(count != 0)하고,
존재하지 않으면 {키, 값(등장한 횟수)} 순서쌍, 즉 {문자열, 0}을 map에 삽입한다.
만약 이미 존재하면 값에 1을 더한다.

문자열과 등장 횟수 정리를 마쳤으면
문제에서 주어진 정렬 기준을 적용할 vector를 생성해, << vector의 자료형은 순서쌍
map의 원소를 하나씩 복사한다.

sort 함수를 사용해 vector의 원소를 직접 생성한 정렬 기준을 이용해 비교한다.
비교자 compare는 다음과 같다.

bool compare(pair<string, int>& a, pair<string, int>& b)
    if (a.second == b.second) { // 1번 우선순위에서 결정 X
        if (a.first.length() == b.first.length()) // 2번 우선순위에서 결정 X
            return a.first.compare(b.first) < 0 ? true : false; //3번 우선순위로 결정
        else
            return a.first.length() > b.first.length();
    else
        return a.second > b.second;

 

배운 내용 :

1. sort

<algorithm> 헤더 파일 필요

문법 : 정렬 시작 구간, 정렬 종료 구간, (비교자)

비교자 : 정렬할 컨테이너의 요소 2개를 참조 연산자를 포함한 인자로 받아, 설정할 비교 조건에서 뒤의 원소가 더 클 때 true를 반환한다.

 

2. map

<map> 헤더 파일 필요

키-값 형식으로 값을 저장할 수 있는 컨테이너. 해시테이블이라고도 한다.

 

 

3. item : vector

Javascript의 foreach처럼 해당 컨테이너의 원소에 순서대로 모두 접근하는 듯? auto와 연계하여 자료형을 명시하지 않고도 사용할 수 있다.

 

4. 문자열 compare 메소드
a.compare(b) : a - b와 유사 (a가 크면 양수)
인자로 string 객체도 전달 가능하다.

C++ 문법 강좌를 정독하자