문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/64064
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
풀이, 코드 (dfs,set)
틀린코드 하나와 맞는 코드 하나를 올려 어떠한 생각으로 이렇게 바꿨는지에 대한 설명도 진행하겠습니다.
맞은 코드만 필요하신분은 맨 아래의 코드를 참조하시면 됩니다.
처음 문제를 접글할때 dfs를 사용하여 만약 엔트리가 완성이 된다면 (즉, 유효한 인자의 갯수가 된다면) 저장을 하는 형식으로 진행을 하였습니다.
틀린코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int visited[10] ={0,};
int answer = 0;
//주어진 조건에 따른 *를 제외한 길이와 문자가 일치하지 않을때 return false
bool matchPattern(string &pattern, string &s){
if(pattern.length() != s.length()){
return false;
}
for(int i = 0; i < pattern.length();i++){
if(pattern[i] != s[i] && pattern[i] != '*'){
return false;
}
}
return true;
}
void dfs(vector<string> user_id, vector<string> banned_id,int idx){
if(idx == banned_id.size()){
answer++;
return;
}
for(int i = 0; i < user_id.size();i++){
if(!matchPattern(banned_id[idx],user_id[i])|| visited[i] == 1){ //일치x 바로 넘어가버림
continue;
}
//패턴이 일치할경우 진행
visited[i] = 1;
dfs(user_id,banned_id,idx + 1);
visited[i] = 0;
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
dfs(user_id, banned_id,0);
return answer;
}
결과에서 fail이 나고 결괏값이 두배로 증폭이 되는 현상을 발견했습니다.
왜 그런건지 위의 코드를 보고 문제와 코드를 한번 보시고 고민해보시면 좋을것 같습니다.
맞은 코드
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int visited[10] ={0,};
set<int> s;
//주어진 조건에 따른 *를 제외한 길이와 문자가 일치하지 않을때 return false
bool matchPattern(string &pattern, string &s){
if(pattern.length() != s.length()){
return false;
}
for(int i = 0; i < pattern.length();i++){
if(pattern[i] != s[i] && pattern[i] != '*'){
return false;
}
}
return true;
}
void dfs(vector<string> user_id, vector<string> banned_id,int idx){
if(idx == banned_id.size()){
//이부분에서 중복에 대한 처리를 해줘야해서 set으로 처리
int num = 0;
for(int i = 0; i < user_id.size();i++){
if(visited[i] == 1){
num *= 10;
num += i;
}
}
s.insert(num);
return;
}
for(int i = 0; i < user_id.size();i++){
if(!matchPattern(banned_id[idx],user_id[i])|| visited[i] == 1){ //일치x 바로 넘어가버림
continue;
}
//패턴이 일치할경우 진행
visited[i] = 1;
dfs(user_id,banned_id,idx + 1);
visited[i] = 0;
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
dfs(user_id, banned_id,0);
int answer = s.size();
return answer;
}
정담은 바로 중복에 있었습니다. 두배로 증식이 되었을때에 대해서 바로 아..! 중복에 대해서 처리를 안하였구나 라는 생각이 들었습니다.
문제에서 주어진 예시를 보시게 되면
제재 아이디
제재 아이디
결국 틀린 코드에서는 결과가
frodo, crodo,abc123
frodo, crodo,frodoc
crodo,frodo,abc123
crodo,frodo,frodoc
의 4가지의 형태로 나오게 되는 것입니다.
이것을 우리는 중복에 대해서 어떻게 처리를 해야할까요?
set을 사용해 줍시다.
이 것에 대한 중복을 제거하기 위해 위의 코드를 보시게 되면
//이부분에서 중복에 대한 처리를 해줘야해서 set으로 처리
int num = 0;
for(int i = 0; i < user_id.size();i++){
if(visited[i] == 1){
num *= 10;
num += i;
}
}
s.insert(num);
return;
숫자를 넣어주게 되며 중복에 대해서는 무시하게되는 set을 사용하여 갯수를 나중에 s.size()를 return 하는 모습을 보실 수 있습니다.
인덱스를 기준으로 8자리까지이므로 int배열에 유효하다고 판단하여 *10을 한 후 인덱스를 더해준 후 set에 insert한 형식으로 진행을 하였습니다.
결국 문제의 예시 중복되는 상황
frodo, crodo,abc123
crodo,frodo,abc123
에 대해서 인덱스!! 로 판단하기 때문에 두개의 num의 값은 같아지므로 중복을 제거할 수 있습니다.
댓글