백준 17349번 Python / 구현

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

 

문제링크

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

17349번: 1루수가 누구야

 

풀이

import sys
input = sys.stdin.readline

answer = []
not_answer = []
predict = []
for i in range(9):
    predict.append(list(map(int, input().split())))

for i in range(9):
    first_base = []
    not_first_base = []
    if predict[i][0] == 1:
        predict[i][0] = 0
    else: predict[i][0] = 1

    for j in range(9):
        if predict[j][0] == 1:
            first_base.append(predict[j][1])
        else:
            not_first_base.append(predict[j][1])

    tmp = set(first_base)
    first_base = list(tmp)
    tmp = set(not_first_base)
    not_first_base = list(tmp)

    for k in first_base:
        if len(first_base) == 1 and k in first_base and k not in not_first_base:
            answer.append(k)
        else:
            not_answer.append(k)

    if len(first_base) == 0:
        for l in range(1, 10):
            if l not in not_first_base:
                answer.append(l)

    if predict[i][0] == 0:
        predict[i][0] = 1
    else: predict[i][0] = 0


tmp = set(answer)
answer = list(tmp)
tmp = set(not_answer)
not_answer = list(tmp)

if len(answer) == 1:
    print(answer[0])
elif len(not_answer) == 9:
    print(-1)
elif len(answer) == 0:
    tmp = []
    for i in range(1, 10):
        if i not in not_answer:
            tmp.append(i)
    if len(tmp) == 1:
        print(tmp[0])
    else:
        print(-1)
else:
    print(-1)

코드가 더럽습니다ㅠㅠ

문제를 풀다 중간중간 오답처리가 되어 반례를 찾고 해결하느라 아주 오래 걸린 문제였습니다.

푸는 원리는 다음과 같습니다.

1. 입력한 값을 리스트로 받습니다.

예) [ [1, 2], [0, 2], ... ]

 

2. 9개의 값들에서 하나만 거짓이라고 가정해야 하기 때문에 for문으로 순회하며 하나씩 바꾸고 바꿨을 때의 경우를 밑의 두 번째 for문으로 순회하며 경우의 수를 체크합니다.

 

3. 하나를 거짓말이라고 가정해 바꾼 뒤, 모든 리스트의 원소에 대해서 1루수가 맞다는 주장은 first_base 변수에 넣어주고, 아니라는 주자은 not_first_base 변수에 넣어줍니다.

 

4. set() 함수를 통해 중복의 경우를 제거합니다.

 

5. 1루수가 맞다는 주장에 한 개의 원소만 있으며, 해당 원소가 1루수가 아니다는 주장에 없으면 answer 리스트에 추가합니다 그 외는 not_answer 리스트에 추가합니다.

 

6. 1루수가 맞다는 주장에 한 개의 원소도 존재하지 않으면, 1루수가 아니다라는 주장에 없는 원소를 answer 리스트에 추가합니다.

 

7. 한 번의 2중 for문이 끝나면 거짓이었던 원소를 다시 원상태로 되돌리고 다음 순서의 원소를 거짓말이라 가정하고 반복합니다.

 

8. 모든 for문의 순회가 끝나면, set() 함수를 통해 answer과 not_answer 리스트의 중복을 제거합니다.

 

9. 최종 조건에 따라 답을 출력합니다.

len(answer) == 1의 경우는 정답일 수 있는 경우가 1개이기 때문에 바로 출력

len(not_answer) == 9인 경우는 모든 경우가 정답일 수 없으므로 -1을 출력

len(answer) == 0인 경우의 조건문은

0 1

0 1

0 1

0 2

0 2

0 2

0 3

0 3

0 3 과 같은 예제를 처리하기 위한 조건(이 경우, 1루수가 4 5 6 7 8 9가 될 수 있으므로 -1이 나와야 함)

 

6번과 같은 경우는

0 1

1 1

0 2

0 3

0 4

0 5

0 6

0 7

0 7 과 같은 예제를 처리하기 위한 조건입니다.

개인적으로, 정말 까다롭고 귀찮은 문제였습니다. 푸는 데 너무 오래 걸려서 힘들었습니다...