[백준] 26069 붙임성 좋은 총총이

park geonwoo·2024년 10월 16일

코딩테스트

목록 보기

25/32

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

문제를 효율적이고 간결하게 해결하기 위해 집합(Set) 자료구조를 활용한 그리디 알고리즘(Greedy Algorithm) 접근 방식을 사용하겠습니다. 이 접근 방식은 각 만남 기록을 순차적으로 처리하면서, 무지개 댄스를 추는 사람의 집합을 업데이트하여 최종적으로 무지개 댄스를 추는 사람의 수를 계산합니다.

문제 이해

문제 요약

목표: 주어진 N개의 만남 기록을 순서대로 처리하여, 마지막 기록 이후 무지개 댄스를 추는 사람의 수를 구하는 것입니다.
특징:
- 초기 상태: ChongChong만 무지개 댄스를 추고 있습니다.
- 만남 규칙:
  - 두 사람이 만났을 때, 만난 사람 중 적어도 한 명이 무지개 댄스를 추고 있으면, 그 만남 이후로 두 사람 모두 무지개 댄스를 추게 됩니다.
  - 한 번 무지개 댄스를 추기 시작하면, 계속해서 추게 됩니다.
입력:
- 첫 번째 줄: 만남 기록의 수 N (1 ≤ N ≤ 1,000)
- 다음 N줄: 각 줄에 두 사람의 이름 A_i와 B_i가 공백으로 구분되어 주어집니다.
  - 이름은 숫자와 영문 대소문자로 이루어진 최대 길이 20의 문자열이며, 서로 다릅니다.
  - ChongChong은 반드시 한 번 이상 등장합니다.
출력:
- 마지막 기록 이후 무지개 댄스를 추는 사람의 수을 출력합니다.

예제 분석

예제 입력 1:

12
bnb2011 chansol
chansol chogahui05
chogahui05 jthis
jthis ChongChong
jthis jyheo98
jyheo98 lms0806
lms0806 pichulia
pichulia pjshwa
pjshwa r4pidstart
r4pidstart swoon
swoon tony9402
tony9402 bnb2011

예제 출력 1:

해석:

초기 상태: ChongChong만 무지개 댄스를 추고 있음.
각 만남을 순서대로 처리하면서, 무지개 댄스를 추는 사람의 수를 업데이트.
최종적으로 10명이 무지개 댄스를 추고 있음.

해결 방법

접근 방식

이 문제는 그리디 알고리즘(Greedy Algorithm)과 집합(Set) 자료구조를 사용하여 해결할 수 있습니다. 그리디 알고리즘은 매 순간 최적의 선택을 하여 전체 문제를 해결하는 방법으로, 여기서는 가능한 빨리 무지개 댄스를 추는 사람의 수를 확장해 나갑니다.

알고리즘 단계

초기화:
- 무지개 댄스를 추는 사람을 저장할 dancers 집합을 초기화합니다.
- 처음에는 ChongChong만 무지개 댄스를 추고 있으므로, dancers = {"ChongChong"}으로 설정합니다.
만남 기록 처리:
- 각 만남 기록을 순서대로 처리합니다.
- 두 사람 A와 B가 만났을 때, 만난 두 사람 중 적어도 한 명이 dancers 집합에 속해 있으면, 두 사람 모두 dancers 집합에 추가합니다.
최종 결과:
- 모든 만남 기록을 처리한 후, dancers 집합의 크기를 출력합니다.

구현 세부 사항

집합(Set):
- 집합은 고유한 원소들의 모임을 효율적으로 관리할 수 있는 자료구조로, in 연산이 평균적으로 O(1)의 시간 복잡도를 가집니다.
- 이 문제에서는 무지개 댄스를 추는 사람들을 dancers 집합에 저장하고, 새로운 사람이 추가될 때 중복 없이 관리할 수 있습니다.
그리디 선택:
- 만남 기록을 순서대로 처리하면서, 가능한 빨리 무지개 댄스를 추는 사람의 수를 확장해 나갑니다.
- 이는 최종적으로 필요한 무지개 댄스를 추는 사람의 수를 정확하게 계산할 수 있게 합니다.

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다:

def count_dancers(N, meetings):
    # 초기 상태: ChongChong만 무지개 댄스를 추고 있음
    dancers = set(["ChongChong"])

    for A, B in meetings:
        # 만남 중 적어도 한 명이 무지개 댄스를 추고 있으면, 두 사람 모두 추가
        if A in dancers or B in dancers:
            dancers.add(A)
            dancers.add(B)

    return len(dancers)

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    meetings = []

    for _ in range(N):
        parts = input().strip().split()
        if len(parts) < 2:
            # 만약 한 줄에 두 이름이 모두 주어지지 않았다면, 추가로 입력 받기
            parts += input().strip().split()
        A, B = parts
        meetings.append((A, B))

    result = count_dancers(N, meetings)
    print(result)

if __name__ == "__main__":
        main()

코드 분석

1. 함수 정의

`count_dancers(N, meetings)`

목적: 주어진 만남 기록을 순서대로 처리하여, 최종적으로 무지개 댄스를 추는 사람의 수를 계산합니다.
매개변수:
- N: 만남 기록의 수
- meetings: 만남 기록 리스트. 각 요소는 두 사람의 이름을 튜플로 저장한 형태입니다.
반환값: 무지개 댄스를 추는 사람의 수 (int)

주요 변수

dancers: 무지개 댄스를 추는 사람들의 집합. 초기에는 {"ChongChong"}으로 시작합니다.

2. 만남 기록 처리

for A, B in meetings:
    if A in dancers or B in dancers:
        dancers.add(A)
        dancers.add(B)

설명:
- 각 만남 기록 (A, B)을 순서대로 처리합니다.
- 두 사람 중 적어도 한 명이 dancers 집합에 속해 있으면, 두 사람 모두 dancers 집합에 추가합니다.
- 이는 그리디하게 가능한 빨리 무지개 댄스를 추는 사람의 수를 확장해 나가는 방식입니다.

3. 결과 반환

return len(dancers)

설명:
- 모든 만남 기록을 처리한 후, dancers 집합의 크기를 반환합니다.
- 이는 최종적으로 무지개 댄스를 추는 사람의 수를 의미합니다.

4. 메인 함수

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    meetings = []

    for _ in range(N):
        parts = input().strip().split()
        if len(parts) < 2:
            # 만약 한 줄에 두 이름이 모두 주어지지 않았다면, 추가로 입력 받기
            parts += input().strip().split()
        A, B = parts
        meetings.append((A, B))

    result = count_dancers(N, meetings)
    print(result)

설명:
1. 입력 처리:
  - 첫 번째 줄에서 N을 입력받습니다.
  - 다음 N개의 줄에서 두 사람의 이름 A와 B를 입력받아 meetings 리스트에 저장합니다.
  - 한 줄에 두 이름이 모두 주어지지 않은 경우, 추가로 입력을 받아 A와 B를 완성합니다.
2. 함수 호출 및 결과 출력:
  - count_dancers 함수를 호출하여 최종 결과를 계산합니다.
  - 결과를 출력합니다.

5. 코드 실행 예제

예제 입력 1:

12
bnb2011 chansol
chansol chogahui05
chogahui05 jthis
jthis ChongChong
jthis jyheo98
jyheo98 lms0806
lms0806 pichulia
pichulia pjshwa
pjshwa r4pidstart
r4pidstart swoon
swoon tony9402
tony9402 bnb2011

처리 과정:

초기 상태: dancers = {"ChongChong"}
1번 만남: bnb2011 meets chansol → 둘 다 무지개 댄스를 추지 않음 → 변화 없음
2번 만남: chansol meets chogahui05 → 둘 다 무지개 댄스를 추지 않음 → 변화 없음
3번 만남: chogahui05 meets jthis → 둘 다 무지개 댄스를 추지 않음 → 변화 없음
4번 만남: jthis meets ChongChong → ChongChong이 무지개 댄스를 추고 있으므로, jthis도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis"}
5번 만남: jthis meets jyheo98 → jthis가 무지개 댄스를 추고 있으므로, jyheo98도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98"}
6번 만남: jyheo98 meets lms0806 → jyheo98가 무지개 댄스를 추고 있으므로, lms0806도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806"}
7번 만남: lms0806 meets pichulia → lms0806가 무지개 댄스를 추고 있으므로, pichulia도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia"}
8번 만남: pichulia meets pjshwa → pichulia가 무지개 댄스를 추고 있으므로, pjshwa도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia", "pjshwa"}
9번 만남: pjshwa meets r4pidstart → pjshwa가 무지개 댄스를 추고 있으므로, r4pidstart도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia", "pjshwa", "r4pidstart"}
10번 만남: r4pidstart meets swoon → r4pidstart가 무지개 댄스를 추고 있으므로, swoon도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia", "pjshwa", "r4pidstart", "swoon"}
11번 만남: swoon meets tony9402 → swoon이 무지개 댄스를 추고 있으므로, tony9402도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia", "pjshwa", "r4pidstart", "swoon", "tony9402"}
12번 만남: tony9402 meets bnb2011 → tony9402가 무지개 댄스를 추고 있으므로, bnb2011도 무지개 댄스를 추게 됨 → dancers = {"ChongChong", "jthis", "jyheo98", "lms0806", "pichulia", "pjshwa", "r4pidstart", "swoon", "tony9402", "bnb2011"}

최종 결과: 10명이 무지개 댄스를 추고 있음.

출력:

시간 복잡도 및 효율성

시간 복잡도

집합 초기화:
- dancers = set(["ChongChong"])
- 시간 복잡도: O(1)
만남 기록 순회:
```
for A, B in meetings:
    if A in dancers or B in dancers:
        dancers.add(A)
        dancers.add(B)
```
- 반복 횟수: N (1 ≤ N ≤ 1,000)
- 각 반복 내 연산:
  - A in dancers와 B in dancers: 평균적으로 O(1)의 시간 복잡도를 가집니다.
  - dancers.add(A)와 dancers.add(B): 평균적으로 O(1)의 시간 복잡도를 가집니다.
- 전체 시간 복잡도: O(N)
최종 결과 계산:
- len(dancers)
- 시간 복잡도: O(1)

총 시간 복잡도: O(N)

N이 최대 1,000이므로, 매우 효율적으로 동작합니다.

공간 복잡도

집합(dancers):
- 최대 2*N개의 고유한 사람이 있을 수 있으므로, 공간 복잡도는 O(N)입니다.
- 하지만, N이 최대 1,000이므로, 공간 사용량은 매우 작습니다.
만남 기록 리스트(meetings):
- N개의 튜플을 저장하므로, 공간 복잡도는 O(N)입니다.

총 공간 복잡도: O(N)

알고리즘 및 자료구조 설명

알고리즘: 그리디 알고리즘 (Greedy Algorithm)

특징:
- 최적 부분 구조: 각 단계에서 최적의 선택을 함으로써 전체 문제의 최적해를 구할 수 있습니다.
- 지역 최적화: 현재 상황에서 최선의 선택을 함으로써, 전체적인 최적해에 도달합니다.
이 문제에서의 적용:
- 각 만남 기록을 순서대로 처리하면서, 가능한 빨리 무지개 댄스를 추는 사람의 수를 확장해 나갑니다.
- 이는 전역적인 최적해(최종적으로 무지개 댄스를 추는 사람의 수)를 보장합니다.

자료구조: 집합(Set)

용도:
- 고유 원소 저장: 무지개 댄스를 추는 사람들을 중복 없이 저장합니다.
- 효율적인 검색: in 연산을 통해 특정 사람이 무지개 댄스를 추고 있는지 빠르게 확인할 수 있습니다.
장점:
- 빠른 접근 속도: 평균적으로 O(1) 시간 내에 원소의 존재 여부를 확인할 수 있습니다.
- 중복 방지: 같은 사람이 여러 번 추가되는 것을 자동으로 방지합니다.
단점:
- 순서 유지 불가: 집합은 원소의 순서를 유지하지 않습니다. 하지만 이 문제에서는 순서가 중요하지 않습니다.

추가적인 고려 사항

입력 처리:
- 만약 한 줄에 두 사람의 이름이 모두 주어지지 않은 경우를 대비하여, 추가로 입력을 받는 로직을 포함시켰습니다.
- 이는 코딩 테스트 환경에서 입력이 여러 줄에 걸쳐 주어질 수 있기 때문에, 안정적인 입력 처리를 보장합니다.
고유성 보장:
- 문제에서 모든 사람의 이름이 고유하다고 명시되었으므로, 집합에 추가할 때 이름의 중복을 신경 쓸 필요가 없습니다.

결론

제공된 파이썬 코드는 그리디 알고리즘과 집합(Set) 자료구조를 활용하여, 주어진 만남 기록을 효율적으로 처리함으로써 최종적으로 무지개 댄스를 추는 사람의 수를 정확하게 계산합니다. 시간 복잡도는 O(N), 공간 복잡도는 O(N)으로, 주어진 문제의 제한 사항 (N ≤ 1,000) 내에서 매우 효율적으로 동작합니다.

알고리즘: 그리디 알고리즘을 사용하여, 가능한 빨리 무지개 댄스를 추는 사람의 수를 확장해 나갑니다.
자료구조: 집합(Set)을 사용하여, 무지개 댄스를 추는 사람들을 중복 없이 관리하고, 효율적으로 검색합니다.
시간 복잡도: O(N)
공간 복잡도: O(N)

이 접근 방식은 문제의 요구사항을 정확하게 만족시키며, 코드가 간결하고 이해하기 쉬워서 코딩 테스트 환경에서도 효과적으로 사용할 수 있습니다.

추가 팁

집합의 사용법:
- 추가: set.add(element)
- 존재 여부 확인: element in set
- 삭제: set.remove(element) 또는 set.discard(element)
- 합집합: set1 | set2
- 교집합: set1 & set2
그리디 알고리즘 적용 시 주의사항:
- 항상 현재 단계에서 최적의 선택이 전체 문제의 최적해로 이어지는지 확인해야 합니다.
- 반례를 통해 알고리즘의 정당성을 검증하는 것이 중요합니다.
코딩 테스트 준비:
- 다양한 그리디 알고리즘 문제를 풀어보며, 그리디 선택의 근거를 명확히 이해하는 것이 중요합니다.
- 집합(Set)과 같은 효율적인 자료구조의 사용법을 숙지하고, 이를 적절히 활용하는 연습을 해야 합니다.

park geonwoo

이전 포스트

[백준] 강의실 2

다음 포스트