코딩생존기

단어 배열에서 시작단어와 한 글자만 다른것을 찾아서 변환하고 최종단어까지 도달가능할때까지의 단계를 구하는 문제 

한글자만 다른 것을 찾아가는 과정을 반복하는 것이라 DFS를 생각해보았다. 이 과정에서 한글자만 다른 것을 찾는게 함수 내부에 구현하기보다 따로 함수를 만들어주는 게 편해서 그렇게 해보았다.

그리고 가질 수 있는 최대의 단어개수보다 시도횟수가 많으면 안되고 다 순회했을 때도 답이 없을 경우엔 0을 return하게 해준다.

#include <string>
#include <vector>
#include <algorithm>
int answer = 50;
bool visited[50];

using namespace std;

bool diff_st(string a, string b) {            //두 문자열 비교해서 다른 문자가 1개인지 판별
    int diff = 0;

    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            diff++;
        }
    }

    if (diff == 1) {
        return true;
    }
    else return false;
}
void dfs(string begin, string target, vector<string> words, int cnt) {
    if (answer <= cnt) {
        return;
    }

    if (begin == target) {
        answer = min(answer, cnt);                 //answer은 최대길이 값보다 작은 것 중에 최소값
        return;
    }


    for (int i = 0; i < words.size(); i++) {
        if (diff_st(begin, words[i]) && !visited[i]) {                //다른 문자가 한개라면
            visited[i] = true;
            dfs(words[i], target, words, cnt + 1);
            visited[i] = false;
        }
    }

    return;
}
int solution(string begin, string target, vector<string> words) {

    dfs(begin, target, words, 0);

    if (answer == 50) {             //만약 모두를 탐색했는데도 target에 도달하지 못했을 경우
        return 0;
    }
    return answer;
}

주어진 항공권을 모두 사용해서 여행경로를 만드는 문제 =>

DFS를 통해 그래프 처럼 그려가며 갈 수 있는 모든 경로를 방문하면서 정답에 추가해주면 될 것 같다.

다시 확인하고 넘어가는 DFS => 재귀함수로 구현 visited 를 사용하여 방문한곳 체크해주기!

그리고 알파벳 순서로 정렬-> 기본 sort사용 

기존코드(테스트 1,2번 실패)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001]={0};
vector<string> answer;
void dfs(vector<vector<string>> tickets,string ap){		//항공권과 현재공항
    answer.push_back(ap);			
    
    for(int i=0;i<tickets.size();i++){
        if(visited[i]) continue;			//방문한곳이면 continue;
        if(tickets[i][0]==ap){				//방문하지않은곳 중에
            visited[i]=true;				//방문처리				
            dfs(tickets,tickets[i][1]);		//연결된 다음공항으로 
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(),tickets.end());
    dfs(tickets,"ICN");				//시작은 언제나 ICN
    return answer;
}

1,2번이 실패했는데 

반례를 보니 

반례
    `입력`
    [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
    `정답`
    ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

가다가 모든 항공권을 다 사용하지 않았는데 dfs함수가 끝나버리는 경우가 있어서 백트레킹이 필요하다고 한다.

백트레킹은 pop_back과 방문처리하는 배열을 통해 다시 할 수  있다.

고친 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001] = { 0 };
bool isall = false;			//항공권 다 사용했는 지 확인할 변수 
int ticketcnt = 0;			//항공권 사용한 횟수
vector<string> answer;
void dfs(vector<vector<string>> tickets, string ap) { //항공권, 현재 공항
    answer.push_back(ap);

    if (ticketcnt == tickets.size()) isall = true;          //항공권을 다 사용했다면
    for (int i = 0; i < tickets.size(); i++) {
        if (visited[i]) continue;                   //방문한곳이면 continue;
        if (tickets[i][0] == ap) {                  //방문하지않은곳 중에
            visited[i] = true;                      //방문처리
            ticketcnt++;                            //항공권사용수 증가
            dfs(tickets, tickets[i][1]);
            if (!isall) {                               //항공권 다 사용하지않았다면
                answer.pop_back();                      //백트레킹
                visited[i] = false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(), tickets.end());
    dfs(tickets, "ICN");                //시작은 언제나 ICN
    return answer;
}

연결된 컴퓨터끼리는 하나의 네트워크이고 연결되지않은 컴퓨터 하나씩 네트워크가 추가된다.

즉 연결된 컴퓨터를 세면 된다 => DFS

#include <string>
#include <vector>

using namespace std;
bool visited[201]={0};
void dfs(int n, vector<vector<int>> computers,int cur){     //연결된함수 모두 방문처리 => 재귀함수로
    visited[cur]=true;
    //재귀함수
    for(int i=0;i<n;i++){               //연결된 함수 찾으려고 전체 순회
        if(!visited[i]&&computers[cur][i]==1){          //연결되고 방문x일때
            dfs(n,computers,i);
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    //연결된 네트워크를 확인해야함. => dfs 로 
    for(int i=0;i<n;i++){
        if(!visited[i]){
            dfs(n,computers,i);
            answer++;
        }
    }
    return answer;
}

전형적인 BFS문제

BFS 문제를 풀어보면서 이런 맵 탐색이나 미로 탐색에는 큐를 써서 많이 푸는 것 같다.

1. 처음으로 방문처리와 거리값을 체크할 배열을 0으로 초기화해준다. (n,m은 각각 1 이상 100이하의 자연수여서 최대101개가 들어갈 수 있게 해준다.)

2. 반시계방향, 시계방향으로 돌면서 맵을 탐색할 때 쓸 방향 배열(x,y)을 선언해준다. 

3. 초기값을 큐에 넣어주고 while문과  for문을 통해 맵을 탐색하고 위치에서 이상이 있을때(지도사이즈 이상의 위치, 방문한 곳, 벽인지 체크) continue 해주고 각 위치에 대한 값을 넣어준다.

#include<vector>
#include<queue>
using namespace std;
int dx[4]={1,0,-1,0};       //반시계방향 아래부터
int dy[4]={0,1,0,-1};
int width,height;
bool visited[101][101]={0};
int bfs[101][101]={0};

queue<pair<int,int>> q;
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    width=maps[0].size();           //가로
    height=maps.size();              //세로
    
    q.push({0,0});              //시작
    visited[0][0]=1;
    bfs[0][0]=1;
    
    while(!q.empty()){
        
        int curX=q.front().first;
        int curY=q.front().second;
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx=curX+dx[i];
            int ny=curY+dy[i];
            
            if(nx>=height||nx<0||ny>=width||ny<0) continue;     //사이즈 이상
            
            if(visited[nx][ny]) continue;           //방문여부 체크
                
            if(maps[nx][ny]==0) continue;              //벽인지 체크
            
            visited[nx][ny]=1;
            q.push({nx,ny});
            bfs[nx][ny]=bfs[curX][curY]+1;
        }
    }
    
    if(!bfs[height-1][width-1]) answer=-1;
    else answer=bfs[height-1][width-1];
    
    return answer;
}

초기생각

문제의 설명을 읽어보면 A가 1이고 Z가 26이라 Map을 사용하여 1부터 26까지 사전으로 등록해주는게 좋을 것 같다고 생각하였다. 

그리고 LZW압축 과정이 처음에는 이해가 잘 되지않았는데 천천히 읽어보니  문자열에서 사전에 등록돼있는 것 중 가장  긴 문자열을 찾은 후 그 문자열에 맞는 사전에서의 번호를 answer에 추가하고 사전에 없는 단어를 추가해주면 되는 것이었다.

근데 이렇게 생각하니 사전에 등록돼있는 것 중 가장 긴 문자열을 어떻게 찾아야하나 고민을 하다가 사전에 등록되어 있는 것을 찾을 생각보다 사전에 등록되어 있지않은 걸 찾으면 그 전에까지는 등록된 것이니 그 부분만 잘라서 쓰면 되겠다라는 해답이 나왔다.

● 사전에 등록하는 부분에서는 num이라는 전역변수를 사용하여 뒤에 수도 추가될 수 있게 하였다.

알고리즘은 생각하면서 하나의 방법도 좋지만 여러 방법을 생각해보는게 좋을 것 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, int> dic;
int num = 1;
vector<int> solution(string msg) {
    vector<int> answer;
    //A ~ Z 까지 사전에 등록
    for (char c = 'A'; c <= 'Z'; c++) {
        string s = "";
        s += c;
        dic[s] = num++;
    }
    //사전추가 과정
    string sum="";
    for(int i=0;i<msg.length();i++){
        sum+=msg[i];
        if(dic[sum]==0){            //만약 사전에 등록되지않은 단어라면
            dic[sum]=num++;             
            sum=sum.substr(0,sum.length()-1);           //사전에 등록되지않은거 바로 앞에까지는 등록된 단어
            answer.push_back(dic[sum]);                 //등록된 단어의 번호 push_back
            sum="";                                     //단어 초기화
            i--;                                        //사전에 등록되지 않은 수의 인덱스에서 시작 
        }
    }
    answer.push_back(dic[sum]);             //마지막 단어
    
    return answer;
}

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

접두어 즉 다른번호의 시작이 되는 번호가 있으면 false 없으면 true를 반환하는 문제이다. 그래서 길이 기준으로 sort하고 처음 접근할 때 반복문을 돌면서 앞의 단어의 길이만큼 substr해서 같은 단어가 있으면 false 를 반환해주게 만들었다.  \

기존코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {                    //기존에 생각한 코드 시간이 너무 오래걸림 
    bool answer = true;

    sort(phone_book.begin(), phone_book.end());
    for (int i = 0; i < phone_book.size(); i++) {
        string check = phone_book[i];
        for (int j = i + 1; j < phone_book.size(); j++) {
            if (phone_book[j].substr(0, check.length()) == check) {
                return false;
            }
        }
    }

    return true;
}

하지만 효율성 3,4번에서 시간초과가 떠서 실패했다. for문이 2번 도는게 O(n^2)라서 시간초과가 뜬 것이다. 

그런데 sort 가 길이기준으로만 정렬해주는 줄알았는데 사전 기록 기준으로도 정렬을 해준다고 해서 그렇게 된다면 앞의 값과 그 뒤에 값이 사전 기록상으로 비슷한 원소가 오기 때문에 비교를 인접 원소만 해주면 된다고 한다!

고친버전

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {

    sort(phone_book.begin(), phone_book.end());          //이렇게 정렬을 하면 사전순으로 정렬된다 즉 1 1 처럼  같은 숫자대로 정렬
    for (int i = 0; i < phone_book.size() - 1; i++) {
        if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size())) {
            return false;
        }
    }

    return true;
}

※문제설명

휴대폰의 자판은 컴퓨터 키보드 자판과는 다르게 하나의 키에 여러 개의 문자가 할당될 수 있습니다. 키 하나에 여러 문자가 할당된 경우, 동일한 키를 연속해서 빠르게 누르면 할당된 순서대로 문자가 바뀝니다.

예를 들어, 1번 키에 "A", "B", "C" 순서대로 문자가 할당되어 있다면 1번 키를 한 번 누르면 "A", 두 번 누르면 "B", 세 번 누르면 "C"가 되는 식입니다.

같은 규칙을 적용해 아무렇게나 만든 휴대폰 자판이 있습니다. 이 휴대폰 자판은 키의 개수가 1개부터 최대 100개까지 있을 수 있으며, 특정 키를 눌렀을 때 입력되는 문자들도 무작위로 배열되어 있습니다. 또, 같은 문자가 자판 전체에 여러 번 할당된 경우도 있고, 키 하나에 같은 문자가 여러 번 할당된 경우도 있습니다. 심지어 아예 할당되지 않은 경우도 있습니다. 따라서 몇몇 문자열은 작성할 수 없을 수도 있습니다.

이 휴대폰 자판을 이용해 특정 문자열을 작성할 때, 키를 최소 몇 번 눌러야 그 문자열을 작성할 수 있는지 알아보고자 합니다.

1번 키부터 차례대로 할당된 문자들이 순서대로 담긴 문자열배열 keymap과 입력하려는 문자열들이 담긴 문자열 배열 targets가 주어질 때, 각 문자열을 작성하기 위해 키를 최소 몇 번씩 눌러야 하는지 순서대로 배열에 담아 return 하는 solution 함수를 완성해 주세요.

단, 목표 문자열을 작성할 수 없을 때는 -1을 저장합니다.

=> keymap- 키보드, targets 치려고 하는 문자열 

키보드를 누르면서 targets를 만들수 있는 최소의 개수 찾기 불가능 하다면  -1 

●오답코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    int index;
    for(int i=0;i<targets.size();i++){
        answer.push_back(0);
        for(int j=0;j<targets[i].size();j++){
            char c=targets[i][j];
            int len=keymap[i].size()+1;
            for(int x=0;x<keymap.size();x++){
                for(int y=0;y<keymap[x].size();y++){
                    if(keymap[x][y]==c){
                        len=min(len,y+1);
                        break;
                    }
                }
            }
             answer[i]+=len;
        }
    }
    for(int i=0;i<answer.size();i++){
        if(answer[i]%answer.size()==0){
            answer[i]=-1;
        }
    }
    return answer;
}

★ 어려웠던 점 

targets 와 keymap을 돌면서 최소의 인덱스를 저장하면 된다는 것은 알겠는데 여기서 어떤 값과 비교를 해야될지와 targets의 문자가 keymap에 없었을 때의 처리의 문제가 어려웠다.

=> 1. 비교값은 keymap의 제한사항에서의 최대 길이보다 1 크게 해서 min값을 계속 갱신하여 줄 수 있도록 하였다.  

2. 1,0의 값으로 문자열이 같은게 있었는지 없었는지 판단할 수 있도록 하였다. 

★정답코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    int index;
    for(int i=0;i<targets.size();i++){
        answer.push_back(0);
        for(int j=0;j<targets[i].size();j++){
            char c=targets[i][j];
            int len=101;
            int h=1;
            for(int x=0;x<keymap.size();x++){
                for(int y=0;y<keymap[x].size();y++){
                    if(keymap[x][y]==c){
                        len=min(len,y+1);
                        h=0;
                        break;
                    }
                }
            }
            if(h){
                answer[i]=-1;
                break;
            }
             answer[i]+=len;
        }
    }
    return answer;
}