[백준] 25192번 인사성 밝은 곰곰이

park geonwoo·2024년 9월 26일

목록 보기

13/32

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

풀이

이 문제는 새로운 사용자가 입장(ENTER)할 때마다, 그 이후 처음 채팅하는 유저들은 모두 곰곰티콘으로 인사를 한다는 조건을 바탕으로, ENTER 이후 처음으로 채팅을 남긴 유저의 수를 세는 문제입니다. 이 문제에서 중요한 점은 각 새로운 입장(ENTER) 이후에 중복된 닉네임은 곰곰티콘으로 인사하지 않는다는 것입니다.

해결 전략

채팅 기록 관리:
- ENTER가 입력될 때마다 새로운 그룹이 시작됩니다. 따라서, ENTER 이후의 채팅은 새로운 유저들만 곰곰티콘으로 인사할 수 있습니다.
- 이미 인사한 유저는 중복되지 않게 처리해야 합니다. 이를 위해 집합(Set)을 사용하면 중복 처리를 간단하게 할 수 있습니다.
집합(Set)을 사용한 중복 처리:
- HashSet을 사용하여, ENTER 이후 첫 번째로 채팅을 입력한 유저를 기록합니다. 이미 기록된 유저는 두 번 인사하지 않도록 해야 합니다.
- ENTER가 나오면 HashSet을 초기화하고, 그 이후 등장하는 유저들은 다시 처음 인사할 수 있게 처리합니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 채팅 기록 수
        int N = Integer.parseInt(br.readLine());
        
        // 중복된 닉네임을 처리하기 위한 집합
        Set<String> userSet = new HashSet<>();
        int greetingCount = 0; // 곰곰티콘 인사 횟수
        
        // 채팅 기록 처리
        for (int i = 0; i < N; i++) {
            String input = br.readLine();

            if (input.equals("ENTER")) {
                // 새로운 입장(ENTER)이 있으면 새로운 그룹을 시작 -> Set 초기화
                userSet.clear();
            } else {
                // 처음으로 채팅한 유저만 곰곰티콘을 사용하므로 Set에 없을 경우만 카운트
                if (!userSet.contains(input)) {
                    greetingCount++;
                    userSet.add(input);
                }
            }
        }
        
        // 결과 출력
        System.out.println(greetingCount);
    }
}

코드 설명

입력 처리:
- 입력의 첫 번째 줄에는 채팅 기록의 수 N이 주어집니다.
- 이후 N개의 줄에 걸쳐서 ENTER 또는 유저의 닉네임이 문자열로 주어집니다.
중복 처리:
- Set<String> 자료구조인 userSet을 사용하여, 중복된 유저 이름을 관리합니다. 이는 ENTER가 나올 때마다 초기화되어 새로운 유저 그룹을 시작합니다.
- 유저가 곰곰티콘으로 인사한 적이 없는지를 userSet을 통해 확인하고, 해당 유저가 처음 등장할 때만 카운트를 증가시킵니다.
곰곰티콘 인사 횟수 계산:
- ENTER가 나오면 Set을 초기화하여 새로운 유저 그룹을 관리합니다.
- 새로운 유저가 처음 채팅을 할 때만 곰곰티콘 인사를 하므로, userSet에 해당 유저가 없을 경우에만 카운트를 증가시킵니다.

시간 복잡도 분석

입력 처리:
- 입력은 총 N번이 주어지며, 각 입력에 대해 문자열 비교를 수행합니다. 문자열 비교는 입력 문자열의 길이에 비례하는 시간이 소요됩니다.
집합(Set) 사용:
- HashSet의 삽입 및 조회 연산은 평균적으로 O(1) 시간에 처리됩니다. 따라서 각 유저의 이름을 Set에 추가하거나 조회하는 작업은 O(1) 시간에 수행됩니다.
전체 시간 복잡도:
- 각 입력에 대해 최대 O(1) 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(N)입니다. 이는 N이 최대 100,000이므로 매우 효율적입니다.