A → B 성공
저는 이 문제를 완전 탐색 문제로 이해하고 해결 했습니다. 경우의 수를 계산해보니 10^9 의 최대 값 이내에서 나뉘어지는 경우의 수가 N / 2 라고 판단하여 제한 시간 이내에 문제를 해결할 수 있을 것이라 생각 했습니다. 하지만 이 문제를 한 번에 해결하지 못했는데 이유는 제가 종료 조건을 제대로 작성하지 않았기 때문입니다.
if (numStr.length >= targetNumStr.length) {
if (targetNumStr === numStr) {
answer = Math.min(answer, score);
}
}
처음에는 위와 같이 생각 했습니다. 문자열의 길이가 정답과 같거나 이상인 경우라 판단하고 문제를 해결하려고 했지만 이는 모든 경우를 고려하지 못한 종료 조건이었습니다. 예를 들어 입력 값이 2 8 일 경우에는 정답이 계산이 되는 정상적인 경우이지만 저의 조건대로 계산하면 이를 오답으로 계산하기 때문에 잘못된 계산 방식이었습니다.
if(targetNumStr === numStr) {
answer = Math.min(answer, score);
}
if(numStr.length > targetNumStr.length) {
return;
}
그래서 이를 위와 같이 같은 경우에만 정답을 업데이트하고 초과하는 경우에는 조기 반환을 하는 식으로 했어야 제가 원래 의도했던 방식대로 문제를 해결할 수 있었습니다.
괄호 제거
이 문제는 흔히 볼 수 있는 스택을 활용하여 올바른 괄호를 찾는 문제였습니다. 하지만 이 문제 또한 조건을 제대로 따르지 않아 문제를 해결하지 못했습니다. 이 문제의 마지막 조건은 정답이 "서로 다른 식을 사전 순으로 출력한다." 라는 조건을 갖고 있었습니다.
이에 저는 습관적으로 정답이 문자열, ( 를 포함하기 때문에 문자열에 따른 사전 순을 따라야 한다고 판단하여 localeCompare 을 사용하여 문자열을 정렬하여 문제를 해결하고자 했습니다. 하지만 이 경우 제대로 정렬이 이루어지지 않았습니다.
const answer = [
'(0/0)',
'0/(0)'
];
위와 같이 두 문자열을 비교할 경우 ( 의 경우 아스키 코드의 값이 40이고 0 은 48 이므로 정렬을 하게 되면 (0/0) 이 먼저 정렬되어야 합니다.
하지만 localeCompare의 경우 실행환경에 따라 특수문자나 괄호를 다르게 처리할 수 있습니다. 특히 localeCompare는 종종 특수문자를 무시하거나(ignore punctuation), 숫자와 특수문자의 순서를 ASCII와 다르게 정렬하는 경우가 있습니다.
그렇기 때문에 문자열을 정렬하더라도 문자열 내부에 특수문자와 숫자가 혼합되어 있을 경우에는 localeCompare 보다 sort(0 를 사용한 UTF-18 코드 유닛 순서대로 정렬하는 방식이 더 정확하다는 것을 반드시 기억해야 합니다.
색종이 붙이기
이 문제의 경우 설계는 제대로 했지만 세부적인 구현사항들을 제대로 작성하지 못해서 해결하지 못했습니다. AI의 평가는 다음과 같았습니다.
알고리즘 선택 : 2차원 배열, 부분 집합 채우기, 최적해 찾기라는 특성을 보고 **DFS(백트래킹) + 완전 탐색**을 선택한 것은 완벽했습니다.
가지치기(Pruning) 시도: 색종이 개수 제한(`TOTAL_CARD_COUNTS`)을 두고, 1을 모두 덮으면 종료하는 조건 등은 적절한 접근이었습니다.
하지만 세부적인 조건을 제대로 고려하지 못한 것이 패착이었습니다. 예를 들어
function solution(sx, sy) {
for(let i = sx; i < MAX_LENGTH; i++) {
for(let j = sy; j < MAX_LENGTH; j++) {
...
}
}
}
위와 같이 sx, sy 를 인자로 전달받아 Loop를 돌 경우 sy 가 모두 돌았을때 시작점이 어떻게 되는가?를 전혀 고려하지 않았다는 점입니다. sy 의 경우 최대 길이에 해당하면 다시 sy = 0 에서 부터 탐색을 수행해야 하는데 이를 고려하지 않아 전체 배열 탐색이 아닌 부분 탐색을 했다는 부분에서 문제를 해결하지 못하게 되는 부분이었습니다.
또한 이 문제에서는 부분이 실패하면 전체가 실패해야 한다라는 조건이 명시적으로 작성이 되어 있었습니다. 하지만 저는 이 조건을 제대로 고려하지 않아 문제를 제대로 해결하지 못했습니다.
이렇듯 문제를 어떻게 해결할지 구상하는 것 또한 중요하지만 세부적인 조건을 제대로 지키지 못하고 있다는 것이 현재 저의 단점이라는 것을 이번 하루 문제 해결을 통해서 알 수 있었습니다.