JArchive 프로그래밍 일기

문제 링크 

문제 유의 사항

반드시 모든 티켓을 사용해야 한다. 

반드시 시작 공항은 ICN 이다. 

모든 티켓을 사용할 수 있는 입력만 주어진다. 

가능한 경로가 여러개 나와도, 알파벳순으로 우선하는 경로를 선택한다. (== 탐색 전 정렬 필요) 

리뷰 

DFS 구현 시, 탐색 함수 매개변수와 종료 조건이 중요하다. 

탐색 목표 : 목적지, 몇번째 방문인지. 

탐색 종료 조건 : 티켓 개수가 방문 순서와 똑같으면 모든 티켓을 사용한 것이니까 종료. 

탐색 가능 조건 : 목적지를 시작점으로 하는 티켓이 있는지 확인 && 미방문인지 확인 

1) 모든 티켓을 검사. 

탐색 가능 조건이 있다면, 방문 표시하고 답 벡터에 넣는다. DFS 탐색 시작. 

DFS탐색은 true/ false 를 리턴한다.

탐색 해보고 만약 실패라면, 다시 미방문 표시 

2) 탐색 가능 조건이 없다면, 답 벡터에서 빼고 false 리턴. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

vector<string> routes; // 정답 경로 벡터
bool visit[100002]; // 방문 체크

bool DFS(string start, int cnt, vector<vector<string>> &tickets){

  if(cnt == tickets.size()) return true; // 탐색 끝나면 true

  for(int i = 0; i < tickets.size(); i++){ // 시작점 타겟이 있는지 확인 
    if(visit[i] == false && start == tickets[i][0]){ // 미방문이고, 시작점 타겟이 맞으면, 방문!
      visit[i] = true;
      routes.push_back(tickets[i][1]); // 방문한 도착지를 답 벡터에 푸시
      bool res = DFS(tickets[i][1], cnt+1, tickets);
      if(res) return true;
      visit[i] = false;
    }
  }
  
  routes.pop_back(); // 갈 곳이 없으면, 가장 최근 도착지를 벡터에서 제거 
  return false;
}

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

  sort(tickets.begin(), tickets.end()); // 알파벳 순 앞서는 경로 선택
  routes.push_back("ICN"); // 항상 시작은 ICN
  DFS("ICN", 0, tickets);  //시작점이 "ICN"인 티켓을 탐색

  return routes;
}

문제 링크 

첫 번째 풀이 : 시작점을 기준으로 정렬했다.

end_point는 차가 나가는 지점을 저장한다. 

answer 는 감시카메라 개수 변수다. 

차 2대가 {1, 3} {4, 5} 이 순서로 오는 경우

두 차는 겹치지 않으니까 answer++ 로 카메라를 추가해줘야 한다. 

그리고 마지막 차가 나가는 지점은 5가 된다. end_point = r[1];

차 2대가 {1, 6} { 2, 3} 이 순서로 오는 경우

두 번째 차가 빨리 나가버린다. 

이 때는 종료지점이 더 짧은 3으로 end_point를 갱신해줘야 한다. 

차 2대가 {1, 6} { 2, 3} {4, 9} 이 순서로 오는 경우

 {1, 6} { 2, 3} 을 감시하는 카메라 말고, 하나 더 필요하다. 

새로운 차 { 4, 9 }를 감시하려면,  이미 감시한 {1, 6} 이 아니라, {2, 3}과 {4, 9}가 겹치는지를 확인해야 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> routes) {
  int answer = 1; // 차가 1대 이상이니까 카메라는 최소 개수 1
  int end_point = routes[0][1]; // 현재 차가 나가는 지점

  sort(routes.begin(), routes.end());
  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){ // 현재 차와 다음 차가 겹치지 않으면, 카메라 추가
      answer++;
      end_point = r[1]; // 다음 차 나가는 지점으로 갱신
    }

    // 현재 차가 end_point 보다 먼저 나간다면? 나가는 지점을 현재 차로 수정  
    if(r[1] <= end_point) end_point = r[1];
  }
  return answer;
}

두 번째 풀이 : 종료 지점으로 정렬했다. 

여기서는 감시카메라 개수를 0 으로 초기화 한다. 

마지막 지점은  end_point = -30001 ; 가장 작은 수로 초기화 한다. 

따라서 자동차가 1개 여도, 감시카메라 개수를 1 추가한다. 

주어진 배열

종료 지점이 빠른 순으로 정렬하면 아래와 같다. 

자동차 1개일 때는 첫 번째 자동차만 감시하면 된다.

여기서 감시카메라 개수는 1이다. 이때 end_point = -15 

두 번째 자동차 시작점은 -18이다.  end_point 보다 작다. 따라서 감시카메라를 추가하지 않아도 된다. 

세 번째 자동차의 시작점은 -14 니까 end_point 보다 크다. 감시카메라를 추가해야한다. 

이 때 end_point는 세 번째 자동차의 종료지점으로 갱신한다. 

end_point 는 자동차가 겹치는 마지막 지점으로 이해하면 수월하다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(vector<int> &a, vector<int> &b) {
  return a[1] < b[1]; // 종료 지점 기준으로 정렬
}

int solution(vector<vector<int>> routes) {
  int answer = 0;
  sort(routes.begin(), routes.end(), cmp);
  int end_point = -30001; // 초기값은 가장 작은 수

  for(auto r : routes){ // end_point: 현재 차,  r: 다음 차
    if(end_point < r[0]){
      answer++;
      end_point = r[1];
    }
  }
  return answer;
}

문제 링크 

DFS를 풀 때 매개변수를 줄면 코드 짜는 나도 덜 헷갈리고 메모리도 덜 소모한다. 

탐색할 때 불변하는 값은 전역변수로 해두었다. (컴퓨터 총 개수)

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

bool checked[202]; // 방문 체크 배열
int node_cnt; // 컴퓨터 총 개수

void dfs(int current, vector<vector<int>> &computers){
  checked[current] = true;

  for(int i = 0; i < node_cnt; i++){
    if(!checked[i] && computers[current][i] == 1) // 미방문이고 서로 연결됬다면 탐색하자 
      dfs(i, computers);
  }
}

int solution(int n, vector<vector<int>> computers) {
  int answer = 0;
  node_cnt = n; // 컴퓨터 개수를 전역변수로 만든다

  for(int i = 0; i < n; i++){ // 모든 노드에서 탐색 시작
    if(!checked[i]){ // 미방문이라면 탐색 시작
      answer++;
      dfs(i, computers);
    }
  }
  return answer;
}

문제 링크 

저번에 BFS로 푼 것을 DFS로 다시 풀어봤다.

DFS는 재귀함수의 매개변수를 뭐로 할지와 종료조건이 중요하다. 

문제 설명에 '최소'라는 단어가 나오면 BFS 또는 이분탐색으로 풀 수 있는 가능성이 있다. 

DFS로 이 문제를 풀 땐 아무래도 단어목록을 매개변수로 넘겨야 하다보니 BFS가 더 직관적이었다. 

DFS로 푼 코드 

#include <bits/stdc++.h>
using namespace std;

string tg; // 목표
int answer = 50;  // 최소 횟수 저장
bool checked[52]; // 단어 확인 여부

bool diff_one(string cur, string w){// 단어 cur와 w를 비교 
  int diff_cnt = 0;
  for(int i = 0; i < w.size(); i++){
    if(cur[i] != w[i]) diff_cnt++;
  }
  return (diff_cnt == 1); // 1글자만 다른 단어라면 true 
}

void dfs(string s, vector<string> words, int cnt){

  if(answer <= cnt) return; // 백트래킹 
  if(s == tg) { 
    answer = min(cnt, answer); // 타겟 찾았다면 최소 횟수를 갱신하고 종료
    return;
  }

  int w_len = words.size();
  for(int i = 0; i < w_len; i++){
  
    if(diff_one(s, words[i]) && !checked[i]){ // 1글자만 다르고, 확인 안해본 단어라면 
      checked[i] = true;
      dfs(words[i], words, cnt + 1);
      checked[i] = false;
    }
  }
}

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

  tg = target; // 시작단어와 타겟단어 전역변수
  dfs(begin, words, 0); // begin 단어부터 탐색 시작 
  if(answer == 50) answer = 0; // 타겟 못찾음
  return answer;
}

문제 링크 

리뷰 

문자열 길이가 100만 이하다. 그래서 효율성을 고려해야한다. 

그리고 자연수라는 조건이 있다. 자연수는 0 포함임을 유의하자! 

맞았습니다 코드

#include <iostream>
#include<string>
#include<stack>
using namespace std;

int solution(string s){
  int answer = 0;
  int len = s.length();
  int i = 0;
  stack<char> st;

  if(s.empty() || len % 2 == 1) return 0;
  while(i < len){
    if(st.empty() || st.top() != s[i]) {
      st.push(s[i]);
    }
    else if(st.top() == s[i]) {
      st.pop();
    }
    i++;
  }
  answer = (st.size() != 0) ? 0 : 1;
  return answer;
}

문제 링크 

맞았습니다 코드 

#include <string>
#include <vector>
#include <queue>
using namespace std;

bool check[51]; // 확인 여부 

int solution(string begin, string target, vector<string> words) {
  int min_cnt = 1e9; // 최소 이동 횟수 
  int vector_size = words.size();
  int word_size = begin.size();

  queue<pair<int,string>> qu;
  qu.push({0, begin});

  while(!qu.empty()){
    int cnt = qu.front().first;
    string current_s = qu.front().second; // 비교 문자열
    qu.pop();

    for(int i = 0; i < vector_size; i++){
      // 이미 확인한 문자 지나감
      if(check[i]) continue;

      // 현재 문자열과 i번째 문자열이 1개만 다른지 확인
      int diff_cnt = 0;
      for(int d = 0; d < word_size; d++){
        if(words[i][d] != current_s[d]) diff_cnt++;
      }

      if(diff_cnt == 1){
        if(words[i] == target) { min_cnt = cnt + 1; break; } // 찾음
    
        qu.push({cnt+1, words[i]}); // 1개만 다르니까 여기로 이동 
        check[i] = true; // 이동했으니까 표시 
      }
    }
  }
  if(min_cnt == 1e9) min_cnt = 0;
  return min_cnt;
}

문제 링크 

숫자를 제거했을 때, 맨 앞에 0이 위치하면 안된다. 

맞았습니다 코드 

#include <string>
#include <vector>
using namespace std;


string solution(string number, int k) {
    string answer = "";
    int len = number.length() - k; // 첫 번째 숫자로서 가능한 인덱스 
    int start_idx = 0; // 비교를 시작할 인덱스 

    for (int i = 0; i < len; i++) {

        char max_num = number[start_idx];
        int max_idx = start_idx;

        for (int j = start_idx ; j <= k+i; j++) {
            if (max_num < number[j]) {
                max_num = number[j];
                max_idx = j;
            }
        }
        start_idx = max_idx + 1;
        answer += max_num;
    }
    return answer;
}