https://school.programmers.co.kr/learn/courses/30/lessons/178871?language=cpp
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
C++을 이용하여 처음으로 푼 알고리즘 문제이다.
처음 접근 방법은 단순히 완전탐색을 이용하여 callings의 값을 가지는 players 의 인덱스 값을 찾은 뒤
바로 앞 인덱스 i - 1 과 i 를 스왑하는 방법으로 문제를 풀이 했다.
vector<string> solution(vector<string> players, vector<string> callings) {
vector<string> answer;
int size = players.size();
string temp;
for (string call : callings){
for (int i = 1; i < size; i++){
if ( players[i] == call)
{
temp = players[i-1];
players[i-1] = call;
players[i] = temp; // temp를 이용한 swap 방식 Cpp에서 swap 함수를 지원하더라
// swap ( players[i-1], players[i] );
}
}
}
answer = players;
return answer;
}
처음으로 Cpp 을 이용하니 파이썬의 방식과 겹치는 부분과 헷갈리는 부분이 존재하였다. 많이 익숙해질 필요가 있겠다.
대표적으로 for문을 사용할 때와 디버그를 위해 결과물을 출력할 때 조금 복습이 된것 같다.
int main() {
vector<string> players = {"mumu", "soe", "poe", "kai", "mine"};
vector<string> callings = {"kai", "kai", "mine", "mine"};
for (string i : solution(players,callings)){
cout << i << endl;
}
return 0;
}
하지만 테스트 케이스를 통과후 채점을 해보았는데 시간 초과로 오답이였다.
2중 for문을 이용한 완전탐색으로 구현하다 보니, 시간복잡도가 너무 컸나보다.
이부분도 문제의 제약 조건으로 파악했어야 했다.
파이썬에서는 딕셔너리 자료구조형으로 시간을 줄이는 방법이 있는데,
Cpp에서도 Hash map을 이용하면 같은 원리로 시간복잡도를 줄일 수 있었다.
다음에는 hash map을 사용하고 익히는 시간을 가져야겠다.