Koala 1주차:브루트포스 알고리즘(Defaultdict/1270번, 전쟁-땅따먹기)

코알라 1주차 브루트 포스 관련 예제에서 시간 복잡도를 해결하기 위해 딕셔너리를 사용했는데 "defaultdict"라는, 내가 처음보는 자료구조를 만나게 되었다. 시간복잡도 문제를 해결하기 위해선 list보다 dictinary를 사용하는 것이 바람직한 경우가 많은데, defaultdict를 사용하면 조금 더 편리하게 dictionary 자료구조를 이용할 수 있기에 관련된 문제와 함께 개념을 이해해보았다.

 

 

 

1. defaultdict란?

형태는 dictionary와 마찬가지로 [key:value]로 구성이 되는데 그냥 dictionary와 다른점은 이름에도 나와있듯이 디폴트 값을 미리 정해주는 dictionary를 만드는 것이다.

 

 

사용하는 법은 매우 간단한데,

from collections import defaultdict

 

collections 모듈에 있는 defaultdict를 가져와주고,

 

test_defaultdict = defaultdict(int)

 

이렇게 dictionary를 생성할 때 "defaultdict(int)"를 해주면 value값의 디폴트값이 '0'이 된다!!

defaultdict() 안에 있는 괄호에는 int(0), str(''), list([]) 등이 들어갈 수 있는데 각각 괄호 안에 들어간 것들로 디폴트값이 선정되게 된다.

 

 

 

 

2. defaultdict의 사용

from collections import defaultdict

word = "python is good"
word_count = defaultdict(int)

for letter in word:
    word_count[letter] += 1

print(word_count)


#defaultdict 사용하지 않았을 경우

word = "python is good"
word_dict = dict()

for i in word:
  if i not in word_dict:
    word_dict[i] = 1
  else:
    word_dict[i] += 1

print(word_dict)

 

defaultdict를 사용하면 조금 더 직관적으로 코드를 짤 수 있다는 장점을 가지는 것 같다.

 

 

 

 

 

 

 

3. 관련된 문제 : 1270 전쟁-땅따먹기

 

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

 

 

 

 

 

 

 

3-1. 잘못된 풀이(시간초과)

import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    list1 = list(map(int,input().split()))
    n = list1[0]
    list2=list1[1:]
    num = max(set(list2), key=list2.count)
    number = list2.count(num)
    if (n//2)<number:
        print(num)
    else:
        print('SKJKGW')

 

문제 시간 제한이 보통 1초~2초를 주는데 10초 주길래 그냥 냅다 리스트 만들어서 max함수 쓰고 count 함수 썼다.

제대로 시간복잡도를 고려하지 않은 풀이라 예제는 옳게 출력이 되지만 시간초과가 떴다.

 

max()와 count()는 일일이 다 하나하나 비교해야하는 함수이기 때문에 O(n)의 시간복잡도를 가진다. 그리고 그것을 포괄하는 for문이 있기 때문에 내가 쓴 코드는 O(n**2+n**2)=O(n**2)이 된다. 문제에서 최대로 요구하는 땅의 병사수가 10만이기 때문에 이미 100억을 넘어버린다.

 

 

3-2. defaultdict를 이용한 풀이

리스트를 막무가내로 써서 시간초과가 날 때 가장 해결하기 쉬운 방법이 dictionary를 이용하는 것인 것 같다. dictionary는 key와 value가 일대일로 상응하는 구조이기 때문에 dictionary를 활용한 탐색의 경우 O(1)의 시간 복잡도를 가진다.

 

 

from collections import defaultdict
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    dict1 = defaultdict(int)
    list1 = list(map(int,input().split()))
    n = list1[0]
    list2 = list1[1:]
    for i in list2:
        dict1[i] += 1
    if max(dict1.values()) > n//2:
        print(max(dict1, key=dict1.get))
    else:
        print('SYJKGW')

 

dictionary를 사용하므로써 따로 일일이 세어줄 필요가 없게되면서 시간 초과라는 문제를 해결할 수 있게 되었다.

 

 

 

 

 

* 참고한 사이트

https://00h0.tistory.com/24

[Python] defaultdict란?

https://velog.io/@kimwoody/Python-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%99%80-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%EC%9D%98-%EC%A3%BC%EC%9A%94-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] 리스트와 딕셔너리의 주요 연산 시간 복잡도

https://lighter.tistory.com/23

[Python] 1270번 전쟁 - 땅따먹기

https://velog.io/@kjy5947/python-max%ED%95%A8%EC%88%98%EC%9D%98-key%EB%B3%80%EC%88%98-%EC%82%AC%EC%9A%A9

[python] max함수의 key변수 사용.

https://velog.io/@ash5541/get-get%EB%A9%94%EC%84%9C%EB%93%9C%EB%9E%80

파이썬 get() get메서드란?