1루수가 누구야
문제
어느 무더운 여름날, 선린 야구부 앞으로 의문의 음료수가 도착했다!
"이거 마시고 힘내! - 1루수에게 😍"
선수들은 서로 자기가 1루수라며 누가 1루수다 아니다로 싸우기 시작했다. 총 9명이 싸우고 있는데, 9명 중 한 명이 거짓말을 하고 있는 것 같다! 선수들은 아래 중 하나를 주장하고 있다. (편의상 선수들은 1, 2, ..., 9의 등번호로 구분하자.)
- 1 A: 선수 A가 1루수이다.
- 0 A: 선수 A는 1루수가 아니다.
선수들의 설전을 지켜보던 감독님이 답답해서 한마디 했다.
"1루수가 누구야 2루수 이름이 뭐야 3루수는 몰라"
당신은 이제 '정확히 한 명이 거짓말을 하고 있다'는 가정과 '1루수는 정확히 한 명 존재한다'는 사실을 바탕으로 논리적 추론을 통해 특정 인물이 반드시 1루수라는 결론을 이끌어내야 한다. 학생들의 주장만으로 이러한 결론을 이끌어내는 것이 불가능할 수도 있다는 사실에 유의하자.
1루수가 누구야
입력
9개의 줄에 걸쳐, 각 줄마다 0 또는 1이 주어지고 A가 주어진다. (1 ≤ A ≤ 9)
출력
논리적 추론을 통해 1루수를 유일하게 특정할 수 있으면 해당 선수의 등번호를 출력한다.
1루수가 누군지 알 수 없다면 -1을 출력한다.
구현 문제라서 분기를 생각하였다.
일단은 전체다 탐색을 해야 하기 때문에 1~9까지 거짓말을 했을 경우를 다 파악하였다.
그리고 거짓말한 사람을 정했으면 1~9까지 말을 들어보고 판단하기
그렇게 해서 판단하는 기준은 다 탐색하였을 때 가능성 있는 사람이 1명이거나 가능성 없는 사람이 8명일 때,
1루수가 1명으로 특정된다.
이 과정에서 모순이 일어나는 경우를 제외해주었다.
하지만 틀린 경우가 하나 있었다. (90% 쯤에서 틀렸다)
in:
0 1
1 1
0 2
0 3
0 4
0 5
0 6
0 7
0 7
out:
-1
이 경우 1 이 출력 되었는 데 그 이유는 가능성 있는 사람이 없고 가능성 없는 사람이 7명 이하일 경우 결과적으로 1명으로 특정할 수 가 없다.
이 경우 답을 도출할 수 없기 때문에 -1 인 경우를 추가해주었다.
import sys
input = sys.stdin.readline
# 사람을 저장
# 숫자로 인덱스 받기위해 0 인덱스를 없애기 위해서
people = [-1]
for _ in range(9):
num, A = map(int,input().split())
people.append((num, A))
# 답이 될 수 있는 걸 다 담기 위해서
result = []
# 1~9번까지 거짓말 하는 사람
for i in range(1,10):
# 1루수인사람을 찾기 위해
num_list = [-1] * 10
flag = 0
# 1~9까지 확인
for j in range(1,10):
# 거짓말하는 사람이면 바꿔서
if i == j :
num, A = people[j]
num = 1-num
else:
num, A = people[j]
# 1이면 추가
if num:
# 이미 제외되었다면 모순이기 때문에
# 다음 숫자로 넘어가기
if num_list[A] == 0:
flag = 1
break
num_list[A] = 1
# 0이면 제외
else:
# 이미 추가되었다면 모순이기 때문에
# 다음 숫자로 넘어가기
if num_list[A] == 1:
flag = 1
break
num_list[A] = 0
# 모순이 일어나면 바로 다음으로
if flag:
continue
# 다 순회하고나서 대상이 1명이라면 결과에 추가
if num_list.count(1) == 1:
result.append(num_list.index(1))
# 아닌 대상이 8명이라면 나머지 한명 추가
elif num_list.count(0) == 8:
result.append(num_list.index(-1,1))
# 1이 없다면 여러 명이 결과에 추가되기 때문에
# 이 경우는 결국 -1이기 때문에
# re를 초기화하고 탐색을 종료
elif 1 not in num_list:
result = []
break
# 다 돌고나서 결과가 1명이라면 그 한명이 정답
if len(set(result)) == 1:
print(result[0])
# 없거나 여러명이라면 -1
else:
print(-1)
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
백준 20157(화살을 쏘자!) - 해결 (0) | 2022.01.26 |
---|---|
백준 4386(별자리 만들기) - 해결 (0) | 2022.01.19 |
백준 1757(달려달려) - 해결 (0) | 2022.01.16 |
백준 1013(Contact) - 해결 (0) | 2022.01.09 |
백준 14204(표 정렬) - 해결 (0) | 2022.01.08 |