백준 20291번 [파일 정리](C++)-yes6686- 티스토리

백준 문제 풀이: 20291 [파일 정리]

---

문제 링크: https://www.acmicpc.net/problem/20291

문제 설명:

주어진 파일 목록에서 확장자의 종류별 개수를 계산하고, 이를 사전순으로 정렬하여 출력하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 파일의 개수 N이 주어집니다. (1 ≤ N ≤ 50,000)
• 둘째 줄부터 N개의 줄에 파일 이름이 주어집니다. 파일 이름은 확장자를 포함하며, 확장자는 항상 '.' 뒤에 위치합니다.

출력 조건:

• 확장자의 이름과 해당 확장자가 등장한 횟수를 사전순으로 한 줄에 하나씩 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    map<string, int> mp; // 확장자와 등장 횟수 저장
    string filename;

    // 파일 입력 및 확장자 처리
    for (int i = 0; i < n; i++) {
        cin >> filename;
        size_t pos = filename.find_last_of('.'); // 마지막 '.'의 위치 찾기
        string extension = filename.substr(pos + 1); // '.' 이후의 문자열 추출
        mp[extension]++; // 확장자 개수 증가
    }

    // 결과를 사전순으로 정렬
    vector<pair<string, int>> sorted(mp.begin(), mp.end());
    sort(sorted.begin(), sorted.end());

    // 출력
    for (const auto &entry : sorted) {
        cout << entry.first << ' ' << entry.second << '\n';
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 주어진 파일 이름에서 확장자를 추출하고, 이를 사전순으로 정렬하여 확장자의 개수를 출력합니다.

• 확장자 추출:
  • `find_last_of('.')`를 사용하여 마지막 '.'의 위치를 찾습니다.
  • `substr(pos + 1)`을 사용하여 '.' 뒤의 문자열(확장자)을 추출합니다.
• 확장자 개수 저장:
  • `map`을 사용하여 확장자 이름을 키로, 해당 확장자의 등장 횟수를 값으로 저장합니다.
• 정렬 및 출력:
  • `map`을 `vector`로 변환한 뒤, 사전순으로 정렬합니다.
  • 정렬된 결과를 출력합니다.

시간 복잡도 분석:

• 입력 및 확장자 추출: O(N).
• 정렬: O(K log K), K는 고유 확장자의 개수 (최대 N).
• 출력: O(K).

전체 시간 복잡도는 O(N + K log K)로 효율적으로 처리 가능합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
8
input.txt
notes.txt
document.docx
image.png
input.txt
image.jpeg
notes.txt
code.cpp

출력:
cpp 1
docx 1
jpeg 1
png 1
txt 3

파일의 확장자는 사전순으로 정렬되며, 각 확장자의 개수가 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!