수많은 마라톤 선수들이 마라톤에 참여하였는데, 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했음.
마라톤에 참여한 선수들의 이름이 담긴 배열 "participant"와 완주한 선수들의 이름이 담긴 배열 "completion"이 주어질 때, 완주하지 못한 선수의 이름을 구하시오.
<제한사항>
•마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하.
•completion의 길이는 participant의 길이보다 1 작음.
•참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있음.
•참가자 중에는 동명이인이 있을 수 있음.
19개의 풀이가 있습니다.
#python
from collections import Counter
participant = [] # 마라톤 출전 명단(일부러 빈 값으로 하였음.)
completion = [] # 완주자 명단(일부러 빈 값으로 하였음.)
def solution(participant, completion):
answer = Counter(participant) - Counter(completion)
return list(answer.keys())[0]
print(solution(participant, completion)) # solution() 함수 호출하여 반환 값 출력.
participant와 completion 리스트에는 어떠한 값이 들어갈지 모르므로 일부러 빈 값을 선언하였습니다. 리스트 값만 대입하면 정상 작동합니다.
Counter(participant) 는 Counter 클래스를 이용해 participant 배열에 있는 명단의 갯수를 파악한 후 dictionary 형태로 표현됩니다. 예를 들어 { 'woorim' : 3, 'jiho' : 2, 'soojin' : 1} 이면 배열 내 'woorim'은 3번, 'jiho'는 2번, 'soojin'은 1번 있는 것이죠. 또한 Counter 클래스는 집합 연산이 가능한 장점도 있습니다.
즉, answer = Counter(participant) - Counter(completion) 이렇게 하면 차집합 연산이 되어 participant 명단에는 없는 나머지 1인이 answer 변수에 저장됩니다. 저장 될 때는 { 'soojin' : 1 }과 같은 형태로 저장되므로 키 값만 따로 출력하도록 하면 되겠지요. 따라서, answer.keys()를 리스트로 형변환하고 0번지에 있는 값을 return하여 출력한 것입니다.
PHP
$fn = function(array $participant, array $completion) : string {
$result = '';
$cnt_p = count($participant);
$cnt_c = count($completion);
if (!(1 <= $cnt_p && $cnt_p <= 100000)) return $result;
if (!($cnt_c == $cnt_p - 1)) return $result;
$arr = [];
foreach ($participant as $v) {
if (!preg_match('/^[a-z]{1,20}$/i', $v)) return $result;
if (!isset($arr[$v])) $arr[$v] = 0;
$arr[$v]++;
}
foreach ($completion as $v) {
$arr[$v]--;
}
$arr = array_filter($arr);
$result = key($arr);
return $result;
};
print_r($fn(["abc", "def", "ghi", "jkl"], ["abc", "def", "jkl"])); // ghi
print_r($fn(["abc", "def", "ghi", "jkl"], ["jkl", "ghi", "def"])); // abc
print_r($fn(["abc", "def", "def", "ghi", "jkl"], ["jkl", "def", "abc", "ghi"])); // def
C#
using System;
using System.Collections.Generic;
using System.Text;
namespace CD242
{
class Program
{
static void Main()
{
// 참가자, 완주자 생성
int numPlayers = int.Parse(Console.ReadLine());
var generated = GeneratePlayers(numPlayers);
var participants = generated.Item1;
var completions = generated.Item2;
// 참가자 리스트에서 완주자 요소 제거
foreach (string completion in completions)
{
participants.Remove(completion);
}
string incomplete = participants[0];
Console.WriteLine(incomplete);
}
// 선수 이름 생성 및 (참가자, 완주자) 튜플 반환
static (List<string>, List<string>) GeneratePlayers(int players)
{
List<string> participants = new List<string>();
Random rnd = new Random();
for (int player = 0; player < players; player++)
{
int nameLength = rnd.Next(1, 21);
StringBuilder sb = new StringBuilder();
for (int len = 0; len < nameLength; len++)
{
sb.Append((char)rnd.Next('a', 'z' + 1));
}
participants.Add(sb.ToString());
}
List<string> completions = new List<string>(participants);
int removeIndex = rnd.Next(players);
completions.RemoveAt(removeIndex);
return (participants, completions);
}
}
}
from collections import defaultdict
def not_finished(participant, completion):
dic = defaultdict(int)
for name in participant:
dic[name] += 1
for name in completion:
dic[name] -= 1
if dic[name] <= 0:
del dic[name]
return list(dic).pop()
아마 공식적인 풀이는 이 방법이지 않을까 싶네요.
magical한 array를 이용해서 정답을 구한 함수입니다. build_data는 여러분들이 입력 데이터를 이것저것 넣어가보면서 테스트를 할 수 있게 만들려고 뭔가 이것저것 많은데....메인 아이디어는 main함수에 있습니다.
시간복잡도는 O(n + m) (m은 문자열의 총 길이) 이고, 동작하는 내용이 별로 없어서 실제로는 굉장히 빠를 것입니다.
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
void build_data(std::vector<std::string>& p, std::vector<std::string>& c) {
p.clear(); c.clear();
p.push_back("ABCDASDF");
p.push_back("Whatever you want");
p.push_back("length less then 20");
p.push_back("pichulia is god!");
p.push_back("same name");
p.push_back("same name");
p.push_back("substring of some");
p.push_back("substr");
p.push_back("ing of s");
int* random = new int[p.size()];
for (int i = 0; i < p.size(); i++)random[i] = i;
std::random_shuffle(random, random + p.size());
for (int i = 1; i < p.size(); i++)
c.push_back(p[random[i]]);
delete[] random;
printf("participant list :\n");
for (int i = 0; i < p.size(); i++)printf(" - %s\n", p[i].c_str());
printf("completion list :\n");
for (int i = 0; i < c.size(); i++)printf(" - %s\n", c[i].c_str());
}
int main()
{
int t = 9;
int tv = 0;
while (t--) {
std::vector<std::string> participant;
std::vector<std::string> completion;
build_data(participant, completion);
int n = participant.size();
char magical_array[22];
for (int i = 0; i < 22; i++)magical_array[i] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < participant[i].size(); j++) {
magical_array[j] ^= participant[i][j];
}
}
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < completion[i].size(); j++) {
magical_array[j] ^= completion[i][j];
}
}
printf("#%d Answer is ... %s!\n",++tv, magical_array);
}
}
participant = [ "john" , "ed" , "joe" , "rick" , "john"]
completed = ["john", "ed" , "joe" , "john"]
loser = ''
for i in range(len(completed)):
hasElem = participant.count(completed[i])
if hasElem > 0 :
indexOfElem = participant.index(completed[i])
participant.pop(indexOfElem)
else:
loser = participant[0]
print loser
파이썬 막 시작하느라 아직 미숙하지만 올려봅니다
participant=[]
completion=[]
fin=dict()
######(참가자 및 완주자의 이름을 하나씩 입력 받는다고 가정했을 때의 코드)######
num=int(input("마라톤 참가자의 인원수를 입력하십시오: "))
for k in range(num):
p=input("참가자 이름을 입력하십시오: ")
participant.append(p)
print("남은 입력수: "+str(num-(k+1)))
print("======"*6)
for n in range(num-1):
c=input("완주자 이름을 입력하십시오: ")
completion.append(c)
######(part와 comple의 명단 리스트를 받아서 가져온다면 #사이의 코드는 무시 )######
for name in participant:
fin[name]=fin.get(name,0)+1
for name in completion:
fin[name]-=1
if fin[name]==0:
del fin[name]
print(list(fin)[0])
print("마라톤 미완주 선수의 이름은 "+list(fin)[0]+"입니다.")
int count=0;
for(int i = 0; i < participant.length; i++) {
for(int j = 0; j < completion.length; j++) {
if(participant[i].compareTo(completion[j]) == 0) {
count++;
}
}
if(count == 0) {
System.out.println(participant[i]);
}
count=0;
}
String[] participant = new String[10];
String[] completion = new String[9];
// 테스트 데이터는 알아서 넣으시고
public static String getMan() {
boolean isOK = false;
for (int i=0; i<participant.length; i++) {
isOK = false;
for (int n=0; n<completion.length; n++) {
if (participant[i].equals(completion[n])) {
isOK = true;
break;
}
}
if (!isOK) man = participant[i];
}
return man;
}
// 미완주자가 1명이라 동명이인은 의미없음.
participant = [] completion = [] for someone in completion: participant.remove(someone) result = participant[0] print(result)
#파이썬
#이렇게 푸는것이 맞는건지 잘 모르겠습니다. 너무 간단하게 풀려서요 ㅠ
#실수로 참가자들의 이름을 대문자로 했는데, 고치기 귀찮아서 이건 그냥 대문자 그대로 하겠습니다
participant=['PARK', 'SMITH', 'YU', 'LEE', 'KENJI', 'SONG', 'PORORO', 'TAYO', 'SUE', 'SAM', 'BEN', 'TOM', 'TAYO', 'PORORO', 'PARK', 'DALE', 'LANCE', 'LANCE']
print ('\n참가자',participant)
completion=['PARK', 'SMITH', 'YU', 'LEE', 'KENJI', 'SONG', 'TAYO', 'SUE', 'SAM', 'BEN', 'TOM', 'TAYO', 'PORORO', 'PARK', 'DALE', 'LANCE', 'LANCE']
print ('\n완주자',completion)
not_com=participant
for i in range (len(completion)):
not_com.remove(completion[i])
print ('\n미완주자',not_com)
import random
number_participants = random.randrange(1, 100001) # 참가자 수 랜덤 선정
participant = []
completion = []
alph = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
for i in range(1, number_participants+1):
name_len = random.randrange(1, 21) # 이름 길이는 알파벳 1~20자 사이
new_name = ""
for j in range(1, name_len + 1): # 랜덤한 이름 만들기
new_name = new_name + random.choice(alph)
participant.append(new_name) # 참가자 리스트
completion.append(new_name) # 완주자 리스트와 참가자 리스트가 동일
del completion[random.randrange(0, number_participants+1)] # 미 완주자 랜덤하게 1명 제외
# 미 완주자 확인
p_set = set(participant)
c_set = set(completion)
print("총 참여자 수는 {}명이고, 미완주자는 {}입니다.".format(number_participants,p_set - c_set))
print()
# 문제에 충실한 풀이를 해봤습니다.
# 랜덤하게 10만명 내에서 참가자수 정하고, 이름도 랜덤하게 알파벳으로 20자 내에서 정하고, 완주 못한 사람을 랜덤하게 1사람 정했습니다. 당연히 프로그램 돌릴 때마다 결과값이 달라집니다.
from collections import Counter
import random
def marathon(p, c):
result = Counter(p) - Counter(c)
print(list(result.keys())[0])
if __name__ == '__main__':
participant = []
#completion = []
for i in range(100):
name = ''
for j in range(random.randint(1, 20)):
name += random.choice([chr(c) for c in range(97, 123)])
participant.append(name) # 최대 20개 길이의 이름 100개 생성
completion = participant.copy()
completion.remove(participant[random.randint(1, 100)])
marathon(participant, completion)
python 3.9.5입니다. 집합 자료형의 차집합을 이용했습니다. 소스 코드입니다.
def not_complete(participant, completion):
par_set = set(participant)
com_set = set(completion)
return tuple(par_set - com_set)[0]
a = input('input the participant list. ').split()
b = input('input the completion list. ').split()
print(not_complete(a, b))
실행 결과입니다.
input the participant list. a b c d e f g
input the completion list. d f c b g a
e
def solution(participant, completion):
def m_start(participant):
start = dict()
for i in participant:
if i in start:
start[i] += 1
else:
start[i] = 1
return start
start = m_start(participant)
def m_end(completion):
end = dict()
for i in completion:
if i in end:
end[i] += 1
else:
end[i] = 1
return end
end = m_end(completion)
for i in start:
if i in end:
if start[i] == end[i]:
pass
else:
return i
else:
return i
participant =['a','eda','dfadf','asd2','asd1ff']
completion =['a','eda','dfadf','asd2']
def fail (arr1,arr2):
a= set(arr1)
b= set(arr2)
return a-b
print(fail(participant,completion))
def nameOfUncompletion(participant, completion):
participant.sort()
completion.sort()
idx = 0
while idx < len(completion) and participant[idx] == completion[idx]:
idx += 1
if idx == len(completion):
print(participant[-1])
else:
print(participant[idx])
pArr = [ s for s in input("마라톤에 참여 선수들은?:(예: aa ss aaa) ").split(' ')]
cArr = [s for s in input("마라톤에 완주한 선수들은?: ").split(' ')]
cDic = dict()
for n in range(len(cArr)):
if cArr[n][0] not in cDic.keys():
cDic[cArr[n][0]] = []
cDic[cArr[n][0]].append(cArr[n])
pDic = dict()
for n in range(len(pArr)):
if pArr[n][0] not in pDic.keys():
pDic[pArr[n][0]] = []
pDic[pArr[n][0]].append(pArr[n])
if len(pDic[pArr[n][0]]) > len(cDic[pArr[n][0]]):
nameOfUncompletion(pDic[pArr[n][0]], cDic[pArr[n][0]])
break
### part = ['a', 'b', 'c', 'd', 'a', 'c', 'c', 'f', 'e', 'e']
### comp = ['a', 'b', 'c', 'd', 'a', 'c', 'c', 'e', 'e']
from collections import Counter
part = input().split()
comp = input().split()
lim_p = len(part) - len(set(part))
lim_c = len(comp) - len(set(comp))
multi_p = Counter(part).most_common(lim_p)
multi_c = Counter(comp).most_common(lim_c)
missing = ''
if multi_p == multi_c:
missing = list(set(part) - set(comp))[0]
else:
for el, cnt in multi_c:
for el_p, cnt_p in multi_p:
if el == el_p and cnt != cnt_p:
missing = el
print(missing)