c++ 알고리즘 문제 질문

프로그래머스의 알고리즘 문제를 c++ 로 풀고있는데 어디가 틀렸는지 잘 모르겠습니다. ㅜㅜ

아래는 문제입니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
participant completion return
[leo, kiki, eden] [eden, kiki] leo
[marina, josipa, nikola, vinko, filipa] [josipa, filipa, marina, nikola] vinko
[mislav, stanko, mislav, ana] [stanko, ana, mislav] mislav
입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

아래는 제가 작성한 코드인데 예시는 잘 돌아가는데 제출을 하면 틀렸다고 나옵니다…

#include <string>
#include <iostream>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	int k;
    string answer = "";

    for (string &i: participant)
    {	
		k = 0;
		for (string &j: completion)
		{
			if (i == j)
            {
				k++;
                j = "";
            }
		}
		if (!k)
        {
			answer = i;
		    break;
        }
    }
    return answer;
}

안녕하세요.

동명이인이 있는경우는 어떻게 처리되나요?

바로 답변을 하실거 같아서 간단하게 글을 썼었는데요.

더 자세하게 말을 하자면,

그 코드에서
만약 같은이름 A가 양쪽 리스트에

[A, A, A …] [A,A,A …] 3개씩 있거나

또는

[A, A, A …] [A,A …] 3개 2개 있을 때 어떻게 될지 생각해보세요.

N 이 100000 이기 때문에 N^2 으로는 제한시간 100초가 아니면 풀 수 없습니다.

설령 100초라도 이 알고리즘은…

맞아요.

따라서 정렬을 하는게 좋아보이네요 :smiley:

1 Like