2503 숫자 야구

2503 숫자 야구 / c++ / Silver3 / 35분

문제 및 코드

접근 방식

백트래킹 / 브루트 포스

1. 처음엔 주어진 숫자들을 순회하며 규칙을 찾아 판별해내려고 했다.
2. 사람인 내가 생각하기에는 충분한 규칙이었지만 코딩하기엔 애매한 규칙들이었다.
3. 다른 방법을 생각하던 중 시간 복잡도를 계산해봤다.
4. 1 부터 9 까지의 숫자 중 중복되지 않도록 3개를 뽑는다고 하면 9 * 8 * 7 총 504 가지의 경우의 수가 나왔고, 이 숫자들 마다 주어지는 질문의 최대 개수인 100개를 순회한다고 하더라도 50400 번의 계산으로 전부 확인(브루트 포스)이 가능했다.
5. 제한 시간은 1초였고, 1초는 약 1억번의 계산이 가능하므로 충분히 시간 내에 풀 수 있었다.
6. 백트래킹을 사용하여 1부터 9까지 들어있는 벡터로 3자리 숫자를 만들어냈고, 각 숫자마다 질문을 순회하여 아래 로직을 수행했다.
   1. 현재 3자리 숫자를 string A, 현재 순회중인 질문의 3자리 숫자를 string B 로 변환
   2. A 에 B[0], B[1], B[2] 각 자리 숫자가 존재할 경우 Ball++
   3. 그 후 A의 각 자리를 순회하면서 A[i] == B[i] 인 경우, Strike++, Ball–
   4. 계산된 Strike와 Ball 값이 현재 질문의 Strike와 Ball 갯수와 같지 않다면 break 후 return;
   5. 같다면 전역변수인 Answer++;
7. 백트래킹 종료 후 Answer 출력

다시 생각해 볼 점

1. 규칙을 찾기보다 시간 복잡도 계산 후 브루트 포스를 먼저 생각해야하는데, 그게 참 쉽지 않다. 이번에도 규칙을 찾는다고 초반에 시간을 많이 잡아먹었다. 주의해야겠다.