백준 / 전쟁 - 땅따먹기 / 1270번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 전쟁 - 땅따먹기 / 1270번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/1270

 

문제 설명

---

나의 풀이

# 땅의 개수
n = int(input())

answer = []

for _ in range(n):
    win = {}
    war = list(map(int, input().split()))
    # 길이를 구할 변수
    formation = len(war)
    # 과반수를 구해야 하므로 짝수와 홀수의 경우를 나눈다.
    # ex) 7의 과반수는 4이므로 2로 나누고 1를 더해줌
    if formation % 2 == 0:
        formation //= 2
    else:
        formation //= 2
        formation += 1
    # 해쉬를 이용한 문제이므로 딕셔너리를 사용해준다.
    for i in war:
        if not win.get(i):
            win[i] = 1
        else:
            win[i] += 1
        # 중간에서 만약 과반수가 발생한다면 종료한다.
        if win.get(i) and win[i] >= formation:
            answer.append(str(i))
            break
    # 과반수가 발생하지 않았을 때
    max_value = max(win.values())
    if max_value < formation:
        answer.append("SYJKGW")

for i in answer:
    print(i)

---

※ 알아야 할 것

딕셔너리와 리스트의 시간 복잡도

1. 딕셔너리 (dict)
   • 삽입/업데이트: 해시맵 기반으로 구현되므로 평균적으로 삽입과 조회가 O(1) 시간 복잡도를 가집니다. 즉, 새로운 숫자를 추가하거나 카운트를 증가시키는 작업은 평균적으로 상수 시간에 처리됩니다.
   • 최악의 경우: 해시 충돌이 빈번하게 발생할 경우 O(n)에 가까워질 수 있지만, 이 상황은 거의 드물기 때문에 실질적으로는 평균 O(1)로 작동합니다.
2. 리스트 (list)
   • 탐색: 리스트에서 특정 값을 찾기 위해서는 전체 리스트를 순차적으로 검색해야 하므로 O(n)의 시간이 소요됩니다.
   • 삽입/업데이트: 리스트의 끝에 값을 추가하는 작업은 O(1)이지만, 특정 위치에 값을 삽입하거나 삭제할 때는 O(n) 시간이 필요합니다.