[백준] 1270 전쟁 - 땅따먹기

1. 문제

www.acmicpc.net/problem/1270

1270번: 전쟁 - 땅따먹기

2. 접근방법

세상 이상한 문제다.

 

한 줄 마다 번호 여러개를 주고 과반수가 넘는 번호가 있는지 찾는 문제인데

자바 Hashmap을 이용해서 번호에 값을 매핑시켜 그 중 과반수가 있는지 찾아봤는데

메모리 초과가 떠서 당황했다가 자바로 풀린적이 없길래 깔끔하게 포기 했었다.

 

 

그러다 최근에 파이썬 공부할 일이 있어 공부하는 김에 다시 파이썬 딕셔너리를 활용해서 풀어봤는데

시간이 엄청 걸리긴 하지만 풀리긴 풀렸다. 

 

어찌 되었든

풀이 방법은 숫자의 갯수를 잘 세서 초과하는 숫자가 있는지 찾아내기

 

숫자를 잘 세는 방법은 파이썬의 딕셔너리를 활용할 것

 

3. 파이썬 코드

N = int(input())
for i in range(N):
    a = list(map(int,input().split()))
    c= a[0]
    a = a[1:]
    b= {}
    d = True
    for j in a:
        try:
            b[j] = b[j]+1
            if(b[j] > c/2 ):
                print(j)
                d= False
                break
        except:
            b[j] = 1
    if(d):
        print('SYJKGW')

4. 마치며

자바로 왜 메모리초과가 뜨는지 이유를 알고 싶은데 알 방법이 없어서 이상하게만 느껴지는 문제

뭔가 입력과 관련 있는 것 같긴한데..