Problem Solving

문제 https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-i 풀이 문제에서 주어진 조건에 따라서 스트링을 조작하면 되는 간단한 문제이다. 인티저에서 스트링으로, 스트링에서 인티저로 타입 컨버전만 조심하면된다. 주어진 정수 n을 스트링으로 변환한 다음, 앞에서부터 순회하여 "0"을 제거한 스트링 filtered를 만든다. filered를 인티저로 타입 컨버전 해서 x를 구한다. filered의 각 원소를 인티저로 컨버전 한 다음, 합을 구해서 sum을 구한다. x * sum을 리턴한다. 코드 class Solution: def sumAndMultiply(self, n: int) -> int: filtered = "".join(char for char in str(n) if char != "0") if not filtered: return 0 return int(filtered) * sum(map(int, filtered))

문제 https://leetcode.com/problems/remove-covered-intervals 풀이 여러 개의 구간이 주어지고, 다른 구간에 완전히 포함되는 구간을 제거한 이후, 남은 구간의 개수를 리턴하면 되는 문제이다. 가장 쉬운 방법은 브루트 포스이다. 구간의 개수가 최대 1000개이기 때문에, O(n^2) 방식을 사용해도 충분히 통과 가능하다. 하지만 정렬을 이용하면 쉽게 O(n * log(n)) 으로 풀 수 있다. 구간 시작 부분을 기준으로 오름차순 정렬한다. 시작 부분이 같은 경우엔 끝 부분을 기준으로 내림차순 정렬한다. 정렬된 배열을 앞에서부터 순회하며, 지금까지 등장한 끝 부분의 최대값(maxEnd)을 추적한다. 현재 구간의 끝이 maxEnd보다 크면, 이전 어떤 구간에도 포함되지 않는 새로운 구간이므로 카운트하고 maxEnd를 갱신한다. 현재 구간의 끝이 maxEnd보다 작거나 같으면, 이전 구간에 완전히 포함되는 구간이므로 제거한다. 1번에서 시작 부분 기준으로 정렬했기 때문에, 시작 조건은 자동으로 만족되어 끝 부분만 비교하면 충분하다. ...

문제 https://leetcode.com/problems/number-of-paths-with-max-score 풀이 2차원 그리드의 우하단에서 시작해 좌상단까지 이동하면서, 경로에 있는 숫자들의 합의 최대값과 그 최대값이 나오는 경로의 개수를 구하는 문제이다. 최단 거리를 찾는 문제가 아니므로 BFS나 Dijkstra는 필요 없고, 어떻게 경로의 수를 구할지가 핵심이다. 이동 방향은 문제에서 주어져 있으므로, 각 노드에서 인접한 노드들의 값을 활용해 특정 합(v)에 도달하는 경로의 개수를 구할 수 있다. 이런 문제를 효율적으로 푸는 방법은 결국 DP이다. 처음에 점화식을 이렇게 만들었다. dp[r][c][v]: row = r, column = c인 노드에서 지나온 경로에 있는 칸들의 합이 v가 되는 경로의 개수. 테스트 케이스는 통과할 수 있었지만, 실제 제출했을 때는 시간 초과가 되어서 통과하지 못했다. v 차원 때문에 dp공간이 너무 커지는 것이 문제였다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150365 풀이 분명히 배열(문자열)의 원소를 하나씩 채워나가야 하는 DFS 완전 탐색 스타일의 문제인데 k의 최대값이 2,500으로 너무 크다. 하지만 문제에서 주어진 조건들을 읽어보면 프루닝을 통해 백트래킹 문제로 만들 수 있다. 현재 위치와 종료 위치 사이의 맨하탄 거리가 남은 이동 횟수보다 적으면, 더 이상 탐색할 필요가 없다. 목표에 도달하지 못하는 분기이기 때문에, 분기를 버려야 한다. 남은 이동 횟수와 현재 위치와 종료 위치 사이의 맨하탄 거리의 차가 홀수인 경우에도 더 이상 탐색할 필요가 없다. 이동 횟수는 고정이고, 두 위치의 거리보다 크다면 이동 횟수를 어딘가에서 소모해야한다. 그런데 다른 위치로 갔다가, 다시 현재 위치로 돌아올때 소모하는 값은 2이므로, 홀수인 경우에는 목적지에 절대 도달할 수 없게 된다. 마지막으로, 탐색 순서를 잘 정했다면 처음으로 성공한 케이스가 곧 사전순에서 가장 앞선 순서가 된다. 한 번만 성공하게 되면 그 뒤의 모든 분기는 의미가 없어진다. 이렇게 프루닝을 하면 완전 탐색으로 절대로 해결 불가능한 문제를 풀 수 있게 된다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 풀이 문제를 간단히 하는 것이 중요하다. 이 문제에서 원하는 것은 S에서 시작해서 A와 B 노드로 가야하는데, 그 최단 거리를 요구하고 있다. 그러면 둘이 헤어지는 지점이 존재할 것이고, 이 헤어지는 지점은 S일 수도 있다(문제에서 주어진 내용이다). 그러면 헤어지는 지점을 M이라고 했을때, 우리가 구해야 하는 것은 S → M, M → A, M → B의 최단거리들의 합이다. 문제가 최단거리를 구하는 문제로 단순화 되었다. 음수 사이클이 존재하지 않으므로, 다익스트라 알고리즘이나 플로이드 워셜 알고리즘을 사용하면 된다. 만약 다익스트라를 사용한다면 M을 우리가 모르므로 모든 노드에 대해서 다익스트라 알고리즘을 적용해보고 M을 찾아야 한다. 플로이드 워셜은 모든 노드 상호간의 최단거리를 알 수 있고, 노드의 개수도 200개가 상한이기 때문에 플로이드 워셜을 쓰는 것이 훨씬 간단하게 풀 수 있다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/81303 풀이 이 문제에서 핵심은 삭제된 칸을 건너 뛰면서 칸을 옮기는 것이다. 칸을 옮기는 횟수가 최대 1,000,000 번이라고 제한되어 있지만, 명령의 개수도 200,000 개 이므로 칸을 단순히 부울리언 값으로 켜고 끄면서 이동하는 것은 최악의 경우에 굉장히 많은 시간이 걸릴 것이다. 여기서 생각해야할 점은 이 문제에서는 ‘랜덤 액세스’를 요구하지 않는다는 것이다. 문제에서 삭제된 칸을 복구할때 커서를 옮기지 않는다고 했으므로, 랜덤 액세스가 들어갈 부분은 처음 커서 위치를 지정하는 부분밖에 없다. 또한 중간에 있는 칸을 삭제하고 복구하는 작업들이 있으므로, 컨테이너 중간에서 삭제/삽입 연산이 쉬운 자료구조를 생각해야 하고, 바로 링크드 리스트가 떠올랐다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/152995 풀이 정렬 문제다. 두 개의 수를 가진 튜플(혹은 배열)이 있고, 두 수의 합이 아닌, 각 수를 개별적으로 두 값이 모두 작거나 큰지 판단해야 하는 경우에는 첫 번째 기준이 되는 값은 오름차순, 그리고 두 번째 기준이 되는 값은 내림차순으로 정렬하는 것이 일반적이다. 반대도 가능하고, 이 문제에서도 첫 번째 기준이 되는 값을 내림차순, 두 번째 기준이 되는 값을 오름차순으로 정렬하는 것이 더 편하다. 순위를 셀 때도 조금은 최적화할 수 있다. 제거해야할 원소들을 제거하고 새로운 배열을 만드는 것이 아닌, 그냥 배열을 순회하면서, 기준이 되는 원소보다 큰 수를 카운트 하면 된다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68646 풀이 문제의 조건은 쉬운데, 풀이 과정은 쉽지 않아보인다. 하지만 문제를 최대한 단순화해보자. 기본적으로, 인접한 두 풍선을 고를 수 있고 두 풍선중 번호가 더 큰 풍선을 터트려야 한다. 하지만 1회에 한정에서 번호가 더 작은 풍선을 터트릴 수 있다. 일단 기본적으로 마지막까지 남을 수 있는 풍선의 개수를 세야 하므로 모든 풍선에 대해 확인해봐야 한다. 그리고 마지막까지 남을 수 있는 풍선이라고 했으므로, 항상 마지막에 고르는 두 풍선들 중 하나는 현재 내가 확인하고 싶은 풍선일 것이다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49191 풀이 처음에 문제를 막 읽었을 때는 조금 어려워 보이지만, 문장을 살짝 다르게 해석해보자. ‘정확하게 순위를 매길 수 있는 선수의 수’를 알아야 하는데 정확하게 순위를 매긴다는 것은 어떨 때 성립할까? 특정 선수 A가 존재할 때, A와 서로 승패를 알 수 없는 선수 B가 존재하면 정확하게 순위를 매길 수 없는 것이다. 반대로 A가 다른 모든 선수들과 확실하게 승패의 결과를 알 수 있다면, 정확하게 순위를 매길 수 있다. 문제에서는 경기 결과를 제공해주므로, 선수들의 실력을 간접적으로 알 수 있다. 실력을 수치화 해서 관리할 수 있으면 좋지만, 그럴게 할 수 없는 조건이고 그럴 필요도 없다. 단순하게 선수들간의 ‘승’, ‘패’ 결과를 그래프로 관리해주면 된다. 승리 그래프와 패배 그래프를 따로 만들어서, 경기 결과를 그래프로 표현하고, 각 선수마다 이 선수가 승리할 선수, 패배할 선수의 수를 세어주면 된다. 특정 선수가 다른 모든 선수들과 확실하게 승패의 결과를 알 수 있다는 것은, 결국 승리할 선수와 패배할 선수의 합이 현재 선수를 제외한 나머지 선수의 수와 같은 것이기 때문이다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17678 풀이 단순 구현으로 풀 수 있는 문제다. 문제를 단순화하면 조건에 맞는 최대 값을 구하는 문제이므로 바이너리 서치도 쓸 수 있겠다. 우선 시간을 다루는 문제에서는 시간, 분을 분으로 통일하는 경우가 더 시간을 다루기 쉬워지는 경우가 많다. 예를 들어서 셔틀의 첫 도착 시간인 9:00을 540으로 바꾸는 것이다. 그리고 timetable 배열의 길이가 최대 2000이므로 모든 배열을 순회해도, 심지어 $O(n^2)$시간으로 순회해도 아무런 걱정이 없다. 따라서 앞 번호부터 순서대로 버스에 태우면 된다. 이제 마지막 버스인 경우에 콘이 탈 수 있는 여유가 있다면, 마지막 버스의 도착 시간을 리턴하면 되고, 만약 여유가 없다면, 마지막 버스에 마지막으로 타는 사람보다 ‘1분’ 일찍 나오면 된다. ...