연산자 끼워넣기, 스타트와 링크

삼성 기출문제들을 풀면서 이전에 풀었던 실버I 두문제를 풀어보았다. 이전에는 풀지 못하고 답을 참고했던 기억이 나는데, 이번엔 상대적으로 쉽게 풀어서 나름 성장한것을(?) 느꼈다.

연산자 끼워넣기

프로그래머스

SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

해당 문제와 유사한데, 프로그래머스 방식은 굉장히 복잡했던 기억이 있어 다시 풀어봐야겠다.

백준 문제는 수열을 앞에서 부터 순회하며, 4가지 연산에 따라서 모든 경우의 수를 구해서 계산해주면 되는 문제였다.

N=11일 때 연산자의 개수는 10개 이므로, 백트래킹으로 계산했을 때 시간복잡도는 10! = 360만이 되어 충분히 1초안에 통과 가능하다.

앞에서부터 순회하며 연산자의 수가 1이상일 때 해당 연산자에 맞는 계산을 해주고, 횟수 -1을 해준다. 탐색이 끝난 뒤에는 +1을 해줘서 원복을 시켜줘야 한다.

이렇게 해서 쉽게 최소, 최대값을 구할 수 있는데, 로직이 맞는데 자꾸 틀려서 봤더니 최소값의 초기값 설정을 0으로 둬서 생긴 문제였다. 음수가 생길수도 있으니 이 부분을 빠르게 캐치하지 못했다.

N=20이고, 각 스타트와 링크는 n=10이기 때문에 해당 문제 역시 백트래킹으로 탐색이 가능하다.

백트래킹을 돌며 depth가 n/2일 때 return하며 팀이 될수 있는 모든 경우의 수를 찾는다. 이 때, 방문처리 되었다면 스타트 팀 아니라면 링크 팀으로 구분해주었다.

팀을 나누었다고 해서 끝이 아닌데, 예를 들어 (0,1,2)가 같은 팀의 경우 계산을 어떻게 해줘야하나 처음에 헷갈렸다. 다시한번 천천히 살펴보니 (0,1,2)에서 나올 수 있는 모든 조합을 더해주면 간단했다. 해당 연산은 이중포문을 통해 더해주었다.

개인적으로 아쉬웠던 점은, dfs(0, 0) 이렇게 시작값을 정해주었을 때 중복이 발생했다.

스타트 (0,1)

링크 (2,3)

스타트 (2,3)

링크 (0,1)

해당 두 케이스는 문제를 보면 알겠지만 중복이다. 문제에서 시간에 걸리진 않았지만, 개선의 여지가 있었다.

gpt의 도움을 빌려보니,

visited[0] = true;
dfs(1, 1);

이런식으로 0번 인덱스를 무조건 스타트에 포함시키면, 중복 조합이 제거가 가능했다.

실제로 메모리와 시간복잡도가 개선된 것을 확인할 수 있었다.