[Programmers] Level 3

문제 목록 바로가기 : https://programmers.co.kr/learn/challenges

[1차] 추석 트래픽

Link : https://programmers.co.kr/learn/courses/30/lessons/17676

solution

로그 문자열에서는 응답완료시각, 처리시간이 주어진다.
각 로그 문자열에서 응답시작시각과 응답완료시각을 구해서 조건에 맞춰 완전 탐색을 돌려주면 된다.
기준이 되는 로그의 응답완료시각을 $start$라 하면 $[start, start+999]$에 포함되는 구간을 카운트하면 된다.
1000이 아닌 999를 더하는 이유는 처리시간이 시작 시각과 끝 시각을 포함하기 때문이다.
$1 <= N <= 2000$이므로 $O(n^2)$에도 통과할 수 있다.

ms가 포함되는 바람에 숫자가 좀 커져서 더러워 보이지만 시작 시간과 처리 시간만 계산을 잘하면 금방 풀 수 있다.

2 x n 타일링

Link : https://programmers.co.kr/learn/courses/30/lessons/12900

solution

DP 유형에서 기초 문제로 꼽힌다.
다음의 점화식을 만족한다.

$f(n) = f(n-1) + f(n-2)$

네트워크

Link : https://programmers.co.kr/learn/courses/30/lessons/43162

solution

노드들을 DFS로 돌면서 집합의 개수를 세는 문제다.
DFS를 수행하면 시작점과 연결된 노드들을 모두 체크할 수 있다.
즉, 한 집합을 모두 돌 수 있다는 말이므로 체크 되지않은 모든 노드들에 대해 DFS가 동작한 횟수가 집합의 개수가 된다.

단어 변환

Link : https://programmers.co.kr/learn/courses/30/lessons/43163

solution

시작 문자열로부터 최종적으로 변환할 문자열까지 정해진 규칙을 따라 변환해야한다.
words에 있는 단어 중 철자가 1개만 다른 문자열로 1번씩 변환이 가능하며 이 때 최종 결과까지의 최소 변환 횟수를 출력한다.
BFS는 미로 찾기 등의 문제에만 익숙해져 있어서 조금 당황스러웠지만 방식은 크게 다르지 않다.

먼저 어떤 문자열을 기준으로 잡자. 그럼 words에 변환 가능한 단어가 존재할 것이다. (없을 수도 있다)
존재한다고 가정할 때 두 문자열을 이웃으로 묶어줘야 한다. 나는 인덱스를 이용했다.
시작 문자열부터 시작해야하기 때문에 먼저 push를 해준 뒤 이웃을 묶어줬다.

int solution(string begin, string target, vector<string> words) {
  words.push_back(begin);
  for(int i=0; i<words.size()-1; i++){
      for(int j=i+1; j<words.size(); j++){
          if(onediff(words[i], words[j])){
              node[i].push_back(j);
              node[j].push_back(i);
          }
      }
  }
  ...
}

그 다음은 전형적인 BFS 문제로 바뀌게 된다.

가장 먼 노드

Link : https://programmers.co.kr/learn/courses/30/lessons/49189

solution

지나간 노드들을 visited로 체크하면서 BFS를 통해 가장 먼 노드까지 이동하면 된다.
처음엔 DFS로 풀어보려 했는데 돌려보니 이미 지나간 노드를 다시 거치는 경우가 발생했다.
최종적으로는 시간 초과를 받았다. DFS말고 BFS로 해보니 시간 문제없이 바로 통과할 수 있었다!