문제 86
세 명이 모이면 한 명은 세종대생이다
세종이는 "세 명이 모이면 한 명은 세종대생이다."라는 말을 좋아한다. 세종이는 이 말이 사실인지 확인하기 위해 $N$명의 소속을 기록하였다. $N$명 중 서로 다른 $3$명을 어떻게 선택하더라도, 그중 적어도 한 명이 세종대생인지 확인해보자.
소속이 sejong인 사람은 세종대생이고, 그렇지 않다면 세종대생이 아니다.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(3 \le N \le 100\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 각 사람의 소속을 의미하는 알파벳 소문자로 이루어진 문자열 $S$가 주어진다. $(1 \le \lvert S \rvert \le 100)$
출력
첫 번째 줄에 문제의 조건을 만족하면 Yes를, 그렇지 않다면 No를 출력한다.
예제 입력 1
3 sejong hanyang konkuk
예제 출력 1
Yes
예제 입력 2
3 sejong sejong sejong
예제 출력 2
Yes
예제 입력 3
3 hanyang konkuk hongik
예제 출력 3
No
노트
$\lvert S \rvert$는 문자열 $S$의 길이를 의미한다.
여담으로, $3$명의 출제진 중 세종대생은 한 명뿐이다.
공식 해설
조건을 만족하지 않는 경우는 세종대생이 아닌 사람만 세 명 고를 수 있을 때이다. 즉 세종대생이 아닌 사람이 세 명 이상이면 No이다.
반대로 세종대생이 아닌 사람이 두 명 이하라면 어떤 세 명을 골라도 적어도 한 명은 세종대생이다. 따라서 각 소속이 정확히 sejong인지 비교하고, 다른 소속의 사람 수가 $2$ 이하인지 확인하면 된다.
입력 문자열 길이의 합을 $L$, 가장 긴 문자열 길이를 $D$라 하자. 문자열을 하나씩 처리하면 시간복잡도는 $O(L)$, 공간복잡도는 $O(D)$이다.
구현 · 언어별 풀이
C++ 구현
소속을 string으로 하나씩 읽어 s != "sejong"인 사람 수를 센다. 모든 입력을 처리한 뒤 이 수가 $2$ 이하인지에 따라 Yes 또는 No를 출력한다.
C 구현
문자열을 한 사람씩 읽고 strcmp(word,"sejong") != 0인 횟수를 센다. 다른 소속이 두 명 이하인지 판단하므로 모든 이름을 저장하거나 정렬하지 않는다.
Python 구현
각 줄의 단어가 "sejong"인지 비교해 다른 사람 수를 누적한다. 전체 문자열 리스트나 소속별 Counter는 필요 없다. 문자열 비교가 상수 횟수의 숫자 계산을 대체하지 않는다.
Java 구현
각 소속을 읽어 word.equals("sejong")로 비교한다. String의 ==는 내용 비교가 아니므로 사용하지 않는다. 다른 소속 수만 저장한다.
Rust 구현
word != "sejong"인 횟수만 센다. str 비교는 내용을 비교하며 소속 문자열을 모두 복사해 저장할 필요가 없다. 최종 개수가 2 이하인지 판정한다.
JavaScript 구현
각 소속 문자열이 정확히 'sejong'인지 비교하고 아닌 사람 수만 센다. 마지막에 그 수가 $2$ 이하인지로 Yes·No를 정한다. 이름의 일부가 들어 있는지만 검사하는 includes는 조건과 다르다.
최대 $100\,000$줄이므로 고정 크기 Buffer로 토큰을 읽거나 줄 단위로 처리하면 전체 소속 배열이 필요 없다. 다른 사람을 이미 세 명 찾았더라도 남은 입력을 별도 자료구조에 넣을 이유는 없다. 숫자 계수와 문자열 하나의 비교만으로 충분하다.