[파이썬/python] 백준 1101번 카드 정리 1

N, M = map(int, input().split())
box = list()
for i in range(N):
    box.append(list(map(int, input().split())))

jocker = list()
one = list()

for b in box:
    already = False
    isOne = -1
    for index in range(M):
        if b[index] != 0:                          # check non-zeros
            if not already:
                already = True
                isOne = index
            else:                                  # two non-zeros exist
                if isOne != -1:
                    jocker.append(b)            # add to jocker
                isOne = -1
    if isOne != -1:
        one.append(isOne)

temp = list(set(one))
if len(jocker) == 0:
    if len(one) - len(temp) > 0:
        print(len(one) - len(temp) - 1)
    else:
        print(len(one) - len(temp))
else: print(len(jocker)-1 + len(one) - len(temp))

1101번 카드정리 1 입니다.

그리디 알고리즘으로 문제를 잘 읽는 것이 중요합니다.

문제를 풀기 위해 생각할 핵심은, '상자에 여러 개 색상의 카드가 있는 경우 모든 카드들을 집어서 조커 박스에 넣는다' 같습니다.

또 다른 고려사항으로, 두 개의 다른 상자에 빨간색의 카드만 있는 경우, 이 카드들을 옮겨줘야 합니다.

 

제가 생각해낸 알고리즘은 다음과 같습니다.

1. '두 색상 이상의 카드들이 들어있는 상자'는 jocker list에 넣어둡니다.

2. '한가지 색상만 있는 상자'는 one list에 넣어둡니다.

3. jocker - 1번의 이동으로 '두 색상 이상의 카드들이 있는 상자'의 카드들을 한 곳으로 모을 수 있으므로 횟수에 len(jocker)-1 합니다.

4. one list에서의 원소들 중 중복되는 요소들만큼 횟수를 더합니다.

 

예외 1 - jocker에 원소가 없는 경우, 횟수에 len(jocker)-1을 하지 않습니다.

예외 2 - jocker에 원소가 없는 경우, one list에서의 원소들 중 중복되는 요소들 - 1만큼 횟수를 더해야 합니다.

 

TIP - array list에 대해 list(set(array)) 명령어를 사용하여 중복되는 요소들을 제거할 수 있습니다.