N은 4자리로 고정되어 있다.
query 함수를 호출해 보면 스트라이크와 볼의 갯수를 알 수 있다.
예시인 플레이어1은 '1234' 플레이어2는 '4139'면
첫번째 경우 1 스트라이크, 2 볼일 수 있다. 그러면 음 뭘 해야 될까.
1. 스트라이크를 찾는다.
-> '1234'중 한 자리씩 아예 새로운 숫자로 바꿔 본다. (2,5,6,7,8,) 중에 가능하다.
4139 -> 2139 : 1스트라이크 2볼 여전하다.
4139 -> 4239 : 2스트라이크 0볼, 스트라이크가 하나 늘었다. 확실한거는 꼭 저장하자. 어떻게??
(1,5,6,7,8)
//즉 스트라이크 + 볼 < 4일때 까지랑 이후랑 다르다.
4239 -> 4231 : 1 스트라이크 3볼 // 스트라이크와 볼의 갯수가 4개니까 여기서 부터는 숫자 자체를
바꿀 필요는 없다.
3은 고정..
일단 순열 순서로 바꿔보자.
4231
4132 : 1스트라이크 3볼
2431 : 1스트라이크 3볼
2134 : 2스트라이크 2볼 -> 2,4번째 자리각각 중에 하나만 스트라이크이다.
2번째 자리를 다른 숫자인 5로 바꿔 보아서 2534를 만들고 여전히 2 스트라이크면 4가 답이고,
스트라이크 갯수가 줄으면 2번째가 스트라이크 자리다.
2134
// 순열 과정에서 스트라이크 갯수가 증가하면 어느 위치가 스트라이크 인지 확인해야 한다.
그리고 순열 과정을 거치는 수를 2개로 바꾼다. 근데 2개면 나머지 2개만 위치 바꾸면 되니까 답
1234가 된다.
다른 예시
'1234'에 '2567'
2567 : 0스트라이크 1볼
3567 : 0스트라이크 1볼
어떡하지?
첫번째 경우 : 같은 위치에서 수를 두번만 더 바꿔보자
4567 : 0스트라이크 1볼
8567 : 0스트라이크 0볼
두번째 경우 : 다음 자리로 넘어간다.
3567
3467 : 0스트라이크 2볼 , 볼 갯수 전에 안바뀌고 1개 증가한거면 두자리 모두 볼인 숫자이다.
다른 방법으로 접근할 수 도 있다.
'1234' '4139'면
4139 : 1스트라이크 2볼 -> 아웃인게 1개인 상황이니까 하나만 찾으면 된다.
그렇다고 한개만 찾자니 바꾸다 보면 정보가 나온다....
볼의 갯수 감소,증가, 스트라이크의 증가,감소는 명확한 정보가 주어진다.
그러나 증감이 없는 경우는 정보가 애매하다.
같은 위치에 숫자를 바꿨을때 볼의 갯수가 여전히 변화가 없으면 다시 확인이 원점으로 돌아오는 상황이다.
4139 : 1스트라이크 2볼
2139 : 1스트라이크 2볼
5139 : 1스트라이크 1볼 // 2는 볼이고 5는 볼이 아니다. 거슬러 올라가면 4는 볼임을 알 수 있다.
볼 2,4
2139 : 1스트라이크 2볼 // 4가 볼이므로 2439로 한다.
2439 : 1스트라이크 2볼 // 5는 볼이 아니므로
2639 : 1스트라이크 1볼 // 4는 볼이고 6은 볼이 아니다. 거슬러올라가면 1도 볼이다.
볼 1
2439 : 1스트라이크 2볼 // 1이 볼이 므로
2419 : 0스트라이크 3볼 // 3이 스트라이크다. 4번째를 1로 하면 된다.
2431 : 1스트라이크 3볼 //이제 3볼 끼리 바꾸면 된다.
근데 볼 갯수 안변하는 문제 경우가
'9876'인데
'1876'이면
2876 : 3스트라이크 0볼 : 첫자리를 바꿨는데 3스트라이크면 이 위치만 스트라이크면 되는 거다.
3876 : 3스트라이크 0볼
4876 : 3스트라이크 0볼
5876 : 3스트라이크 0볼
9876 : 4스트라이크
9876
1276 이면 2스트라이크 0볼
3276 : 2스트라이크 0볼 // 3은 0볼이라서 아웃, 게다가 이전에 스트라이크가 감소 안해서 1도 아웃인걸로 판단.
4276 : 2스트라이크 0볼 // 4도 0볼이라서 아웃.
5276 : 2스트라이크 0볼 // 5도 아웃
8276 : 2스트라이크 1볼 // 8은 볼, 현재 아웃 아니고 배치 안된 숫자는 9밖에 없다.
8976 : 2스트라이크 2볼 // 9는 볼이다.
// 지금 8이랑 9가 볼이라서 서로 자기 자리가 아닌 것을 아니까 -> 볼이 2개 스트라이크가 2개인 상황이니까.
9876 으로 하면 된다.
//결국 던진 결과 0볼이면 상황 판단이 명확하다.
0볼에서 0볼이면 던진 공이 아웃인게 확실 하다.
9876
1723 : 0스트라이크 1볼
4723 : 0스트라이크 1볼 //
5723 : 0스트라이크 1볼 //
//1볼에서 1볼이면
던진 공과 원래 있던 공이 모두 볼인지
던진 공과 원래 있던 공이 모두 아웃인지 알 수 없다.
남은 숫자를 쭉 거기에 넣을때 볼의 갯수에 변화가 있으면 모두 볼인 거고.
갯수에 변화가 없으면 모두 아웃인 것이다.
6723 : 0스트라이크 2볼 // 6은 볼 // 1볼에서 2볼 되서.
6823 : 1스트라이크 1볼 // 8은 스트라이크 // 7은 원래 볼이네.
6873 : 1스트라이크 2볼 // 2는 아웃.
6879 : 1스트라이크 3볼.
어떻게 던지지?
스트라이크 + 볼 == 4일때 까지는 공을 던지는 과정이 필요하다.
앞쪽에서 부터 아직 던져져 있지 않고, 아웃이 아닌 공중에 차례로 던지면 된다.
1234를 찾을때 3592 면 어떻게 새로 던지는 걸 구현하자.
3592 : 0스트라이크 2볼
4592 : 0스트라이크 2볼
즉 4를 어디서 가져오지. 정보 저장의 문제.
일단 전부 unknown에서 하나씩 가져온다.
3,4는 보류(delay)에 넣는다.
6592 : 0스트라이크 1볼, 6은 언노운에서 지우고 아웃으로 넣는다.
3,4는 언노운에서 지우고 볼에 넣는다.
그리고 다음 자릿수로 넘어간다.
이 구조를 배열로 해보자 일단. 그러면
언노운 - 0,1,2,5,7,8,9
아웃 - 6
볼 - 3,4
스트라이크 -
공 클래스를 생성한다. 그리고 속성들은
nums[0~9]
배열의 자료형은 구조체로
struct{
bool valid;
}
메소드들은 추가, 제거를 넣는다. 그리고 get_next(int from)?
볼의 갯수 감소,증가, 스트라이크의 증가,감소는 명확한 정보가 주어진다.
이것을 설계해 보자. 이거 if문이 어렵다......
1. 볼이나 스트라이크의 증가는 새로 던진게 볼이나 스트라이크라는 것이다.
그리고 감소가 있으면 그건 감소한 것이라는 것이다.
2. 볼이나 스트라이크의 감소는 이전 것이 볼이나 스트라이크라는 것이다.
그리고 감소가 있으면 그건 감소한 것이라는 것이다.
3. 증가는 있는데 감소는 없으면 prev는 아웃이라는 것이다.
4. 감소는 있는데 증가는 없으면 throwing이 아웃이라는 것이다.
5. 증가,감소 모두 없으면 prev랑 throwing 모두 볼/스트라이크거나
모두 아웃일 수 도 있다.
-> 이거 다하면 if else가 10개는 나오는데 하.... 이게 맞는건가.
근데 out,ball,strike인 공들의 저장은 할 수 있는데 관리가 안된다.
->하나의 balls라는 클래스에 0~9까지의 공들을 10개를 그냥 타입을 부여해서 구분했다.
위의 if문을 간결하게 해보자 최대한.
어떤 타입이 증가하면 증가하면 throwing은 그 타입인거다.
다른 타입이 그대로다 prev는 아웃이였다. ,아니면 prev는 다른 타입이였다.
어떤 타입이 감소하면 prev는 그 타입이였던 거다.
다른 타입이 그대로다 prev는 아웃이였다. ,아니면 prev는 다른 타입이였다.
증감이 없다. -> 특수 케이스~
continue; 하면 안되나?
0123456789
1234
2356 : 0스트라이크 2볼
4356 : 0스트라이크 2볼
7356 : 0스트라이크 1볼 //4는 볼
7156 : 0스트라이크 1볼
7256 : 0스트라이크 1볼
7356 : 0스트라이크 1볼
7856 : 0스트라이크 0볼 //3은 아웃.
7956 : 0스트라이크 0볼 // 같다고 다 컨텐뉴가 아니네, !! 9는아웃
7916 : 0스트라이크 1볼 //1은 볼
7912 : 0스트라이크 2볼 //2는 볼.
이럼 내가 구현 한건 끝나버리는데 ....아 여기서 볼은 3개긴 한데 아직 갯수 안되니까 다시 앞에서 부터 찾도록 해볼까?
너무 복잡하다 간단하게 다시 해보자.
1234이면
5972 : 0,1
1972 : 1,1 -> 첫째자리 스트라이크
1372 : 1,2 -> 새로 던진거 볼. 볼인 것을 다른 자리로 옮겨 봐야지.
1732 : 2,1 -> 세번째 자리가 스트라이크, 2가 볼인지 7이 볼인지 모른다. 그러니까 7 2 바꾼다
1237 : 3,0 -> 2,7중 한개가 스트라이크 2에 아웃인거 3,7 바꿔본다. 그러면
1273 : 2,1 -> 7이 아웃이다. 1237에서 네번째 자리만 바꿔본다.
1234 : 끝.
1234
만약 1972였음?
1972 : 1,1 - 스트라이크 어떻게 찾지? 자리에 새로운걸 넣으면 바뀌어서 다시 그것도 확인하느라 복잡해진다.
두개씩 교환하는 방식이 좋을 수도?
9172 : 0,2 - 첫,둘째 자리 중 한개가 스트라이크다.
7912 : 0,2 - 첫째자리가 스트라이크다.
위 과정에서 2,7,9는 자기 위치가 아닌 곳이 확인됬다.
1972 : 1,1 -볼을 찾자.
1927 :1,1
1792 : 1,1
5972 : 0,1 - 볼인거 한개 어떻게 찾지.
순열?로 스트라이크 되도록?.
1972 : 1,1
1372 : 1,2 - 3은 볼
1472 : 1,2 - 4도 볼
1234
스트라이크 확인은
1567 -> 1,0
51 67 -> 0,1
6157 -> 0,1 : 첫번째 자리가 스트라이크 3번 쿼리
1279 ->2,0
2179 ->0,2 : 첫,둘째자리가 스트라이크
1729 -> 1,1
api화 하면 n번째 자리가 스트라이크인지 확인해보자.
1279 : 2,0 , 첫째 자리가 스트라이크인가?
2179 : 2,0 ,둘다 스트라이크다. 아니면 둘다 아닐 수도
7219 : 1,1
9271 : 1,1 그렇다.
자리를 3번 바꿨을때 스트라이크 갯수 감소가 4-(스트라이크갯수)여야 한다.
1234
7934 :2,0
9734 :2,0 -> 세네번째가 스트라이크다.
1234
7294 : 2,0
2794 : 1,1
9274 : 2,0, 둘다 아웃인 경우.
4297 : 1,1
1234
9234 : 3,0
2934 : 2,1 둘중 한개는 아웃이다. 한개만 줄었으므로.
3294 : 2,1 두번동안 9가 공통이므로 9가 아웃임을 알 수 있다.
1234
5678 - 0,0이면 그냥 다바꾸면 되네
이 숫자들은 싸그리 제외. 그리고 그냥 새로 숫자 만들면 될듯
0123 뭐 이런식으로 순차적으로 찾아야지 물론.(순열로?)
5178 - 0,1이면 3개만 바꾸면 된다.
0649 - 0,0 이 숫자들은 제외
3156 - 0,2면 두개만 새로운 숫자 찾으면 된다.
1234
2879 :0,1 볼인것의 제 위치를 찾아주자니 6번 해야한다.
2879 숫자들은 확률이 낮으니 나중에 확인하도록 밀어 넣고
1345 부터 해보면 어떨까?
1345 :1,2 여기서 근데 누가 스트라이크인지 찾으면 노답인게 3번걸리는데 3*4 이건 안됨.
그러면 그냥 순열로 돌리면 12가지라 노답임.
1354
1435
1453
답은 이번에 6789
일단 그냥 스트라이크 하나 찾는게 제일 빨라 보인다.
2493 : 0,1 그냥 첫자리에 넣본다. 0~9를
0493 : 0,1 : 0은 아웃이다.
1493 : 0,1 : 1은 아웃이다.
2493 : 0,1 : 2는 아웃이다. 다시하는게 마음 편할듯. 복잡해짐 이걸로 경우 나누면????
5493 : 0,1 : 5는 아웃이다.
6493 : 1,1 :6은 스트라이크다.
그럼 이상태에서
6은 무조건 고정
6493 : 1,1 : 2번째 자리도 아웃인거 뺴고 하면 금방 할듯?
6793 : 2,1 : 7은 스트라이크이다.
6783 : 3,0 : 9는 볼이다 그리고 8은 스트라이크다.. 셋째 자리 확인중이니까 9는 넷째 자리가 스트라이크 자리다.
6789
이정도 횟수면 양호한듯하다.
6789가 답.
6237 :1,1
0237 :0,1 -> 6이 스트라이크,0은 아웃.
6437 :1,1 -> 4는 아웃.
6537 :1,1 -> 5는 아웃.
6837 :1,2 -> 8은 볼.
6897 :1,3 -> 3볼일때 어떻게 찾지?
6 879 : 1,3
6 789 : 4,0
아 이렇게 해야겠다.
아웃인 공은 확인하지 말고
1.스트라이크 감소 -> 이전꺼 스트라이크, 새로운건 아웃
원래 위치에 스트라이크 다시 넣고, 다음 인덱스에서 확인
2.스트라이크 증가 -> 새로운거 스트라이크
다음 인덱스에서 확인.
3.볼 감소 -> 이전거 볼, 새로운건 아웃.
이전꺼가 볼이라 표시만, 스트라이크 찾는다.
4.볼 증가 -> 새로운건 볼.
새로운거 볼이라 표시 스트라이크 찾는다.
아 근데 문제가 현재 1860을 찾는데 0123으로 하면 1이 첫번째 자리에 절대 안온다. ㅋㅋ 아 ball+strike 4개면 순열로 돌리자.
ㅠㅠ못풀었다.
#define N 4
typedef struct {
int strike;
int ball;
} Result;
enum type {
Boll,
Strike,
Unknown,
Guess,
Out
};
typedef struct {
int type = Unknown;
int indexOfGuess = -1;
}ball;
class Balls {
private:
int next = 0;
int strikes = 0;
int bolls = 0;
ball nums[10];
public:
void push(int x,int type,int index);
int getFrontFrom(int from);
int size();
bool checkIfUnknown(int x);
int getType(int x);
int getStrikeZone(int x);
};
int Balls::getStrikeZone(int x) {
return nums[x].indexOfGuess;
}
int Balls::getType(int x) {
return nums[x].type;
}
bool Balls::checkIfUnknown(int x) {
if (nums[x].type == Unknown) {
return true;
}
else {
return false;
}
}
int Balls::size() {
return strikes+bolls;
}
void Balls ::push(int x,int type,int index) {
nums[x].type = type;
if (type == Strike) {
strikes++;
nums[x].indexOfGuess = index;
}
else if (type == Boll) {
bolls++;
}
}
//from is a num 0~9
int Balls::getFrontFrom(int from) {
for (int i = from; i < 10; i++) {
if (nums[i].type == Unknown) {
return i;
}
}
//means empty;
return -1;
}
//
Balls balls;
// API
extern Result query(int guess[]);
int visit[4][10] = { 0 };
//throw until ball + strike == 4
void getResultByChanging(int guess[]) {
int On[10] = { 0 };
for (int i = 0; i < 4; i++) {
On[guess[i]] = 1;
}
Result prev_result = query(guess);
Result cur_result = prev_result;
for (int index = 0; index < 4; index++) {
int throwing;
for (int i = 0; i < 10; i++) {
if (balls.size() == 4) {
int onStrike[4] = { 0 };
//strike 처리
for (int j = 0; j < 10; j++) {
if (balls.getType(j) == Strike ) {
guess[balls.getStrikeZone(j)] = j;
onStrike[balls.getStrikeZone(j)] = 1;
}
}
int inuse[10] = { 0 };
for (int in1 = 0; in1 < 10; in1++) {
if (onStrike[0] == 0 && balls.getType(in1)== Boll && inuse[in1]==0) {
inuse[in1] = 1;
guess[0] = in1;
}
for (int in2 = 0; in2 < 10; in2++) {
if (onStrike[1] == 0 && balls.getType(in2) == Boll && inuse[in2] == 0) {
inuse[in2] = 1;
guess[1] = in2;
}
for (int in3 = 0; in3 < 10; in3++) {
if (onStrike[2] == 0 && balls.getType(in3) == Boll && inuse[in3] == 0) {
inuse[in3] = 1;
guess[2] = in3;
}
for (int in4 = 0; in4 < 10; in4++) {
if (onStrike[3] == 0 && balls.getType(in4) == Boll && inuse[in4] == 0) {
inuse[in4] = 1;
guess[3] = in4;
}
Result ans = query(guess);
if (ans.strike == 4)
return;
}
}
}
}
}//if
if (balls.getType(i) == Out || On[i] == 1) {
continue;
}
int prev, cur;
prev = guess[index];
cur = i;
guess[index] = i;
On[prev] = 0;
On[cur] = 1;
prev_result = cur_result;
cur_result = query(guess);
if (cur_result.strike < prev_result.strike)
{
balls.push(prev, Strike, index);
balls.push(cur, Out, -1);
guess[index] = prev;
On[prev] = 1;
On[cur] = 0;
break;
}
if (cur_result.strike > prev_result.strike) {
balls.push(cur, Strike, index);
break;
}
if (cur_result.ball < prev_result.ball) {
balls.push(prev, Boll, -1);
balls.push(cur, Out, -1);
}
if (cur_result.ball > prev_result.ball) {
balls.push(cur, Boll, -1);
}
}
}
}
void doUserImplementation(int guess[]) {
// Implement a user's implementation function
//init unknown
for (int i = 0; i < 10; i++) {
balls.push(i,Unknown,-1);
}
guess[0] = 0;
guess[1] = 1;
guess[2] = 2;
guess[3] = 3;
// The array of guess[] is a return array that
getResultByChanging(guess);
// is your guess for what digits[] would be.
}
아 그냥 4자리면 1자리만 볼을 넣고 나머지 자리에는 아웃을 넣어서 확인했다. 그런데 쿼리를 너무 많이 물어본거 같다. 50개중에 40개만 맞았다. ㅠㅠ
#define N 4
typedef struct {
int strike;
int ball;
} Result;
enum type {
Boll,
Strike,
Unknown,
Guess,
Out
};
typedef struct {
int type = Unknown;
int indexOfGuess = -1;
}ball;
class Balls {
private:
int next = 0;
int strikes = 0;
int bolls = 0;
ball nums[10];
public:
void push(int x,int type,int index);
int getFrontFrom(int from);
int size();
bool checkIfUnknown(int x);
int getType(int x);
int getStrikeZone(int x);
int strikeSize();
};
int Balls::strikeSize()
{
return strikes;
}
int Balls::getStrikeZone(int x) {
return nums[x].indexOfGuess;
}
int Balls::getType(int x) {
return nums[x].type;
}
bool Balls::checkIfUnknown(int x) {
if (nums[x].type == Unknown) {
return true;
}
else {
return false;
}
}
int Balls::size() {
return strikes+bolls;
}
void Balls ::push(int x,int type,int index) {
if (nums[x].type!=Strike && type == Strike) {
strikes++;
nums[x].indexOfGuess = index;
if (nums[x].type == Boll)
bolls--;
}
else if (nums[x].type != Boll &&type == Boll) {
bolls++;
}
nums[x].type = type;
}
//from is a num 0~9
int Balls::getFrontFrom(int from) {
for (int i = from; i < 10; i++) {
if (nums[i].type == Unknown) {
return i;
}
}
//means empty;
return -1;
}
//
void swap(int *a, int *b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void copyAB(int A[], int B[]) {
A[0] = B[0];
A[1] = B[1];
A[2] = B[2];
A[3] = B[3];
}
// API
extern Result query(int guess[]);
//throw until ball + strike == 4
void getResultByChanging(int guess[],Balls balls) {
int On[10] = { 0 };
for (int i = 0; i < 4; i++) {
On[guess[i]] = 1;
}
Result prev_result = query(guess);
Result cur_result = prev_result;
for (int index = 0; index < 4; index++) {
int throwing;
for (int i = 0; i < 10; i++) {
if (balls.size() == 4) {
int onStrike[4] = { 0 };
int outs[10] = { -1 };
int bolls[10] = { -1 };
int outs_cnt=0;
int bolls_cnt = 0;
//strike 처리
for (int j = 0; j < 10; j++) {
if (balls.getType(j) == Strike ) {
guess[balls.getStrikeZone(j)] = j;
onStrike[balls.getStrikeZone(j)] = 1;
}
else if (balls.getType(j) == Out || balls.getType(j) == Unknown) {
outs[outs_cnt] = j;
outs_cnt++;
}
else if (balls.getType(j) == Boll) {
bolls[bolls_cnt] = j;
bolls_cnt++;
}
}
for (int i = 0; i < 4; i++) {
if (onStrike[i] == 0) {
for (int j = 0; j < 4; j++) {
if (i != j)
guess[j] = outs[j];
}
for (int k = 0; k < bolls_cnt; k++) {
if(balls.getType(bolls[k]) == Boll){
guess[i] = bolls[k];
Result ans = query(guess);
if (ans.strike == 1) {
balls.push(bolls[k], Strike, i);
break;
}
}
}
}
if (balls.strikeSize() == 4) {
for (int i = 0; i < 10; i++) {
if (balls.getType(i) == Strike) {
guess[balls.getStrikeZone(i)] = i;
}
}
return;
}
}
}//if
if (balls.getType(i) == Out || On[i] == 1) {
continue;
}
int prev, cur;
prev = guess[index];
cur = i;
guess[index] = i;
On[prev] = 0;
On[cur] = 1;
prev_result = cur_result;
cur_result = query(guess);
if (cur_result.strike == 4) {
return;
}
if (cur_result.strike < prev_result.strike)
{
balls.push(prev, Strike, index);
balls.push(cur, Out, -1);
guess[index] = prev;
On[prev] = 1;
On[cur] = 0;
break;
}
if (cur_result.strike > prev_result.strike) {
balls.push(cur, Strike, index);
break;
}
if (cur_result.ball < prev_result.ball) {
balls.push(prev, Boll, -1);
balls.push(cur, Out, -1);
}
if (cur_result.ball > prev_result.ball) {
balls.push(cur, Boll, -1);
}
}
}
}
void doUserImplementation(int guess[]) {
Balls balls;
// Implement a user's implementation function
//init unknown
for (int i = 0; i < 10; i++) {
balls.push(i,Unknown,-1);
}
guess[0] = 0;
guess[1] = 1;
guess[2] = 2;
guess[3] = 3;
// The array of guess[] is a return array that
getResultByChanging(guess,balls);
// is your guess for what digits[] would be.
}
------------------------------------------------
음 다시해본다~
음 고정된 한자리를 한개씩 바꿔가면서 모든 숫자에 대해서 확인하면 -> 문제점이
답이 2467이고
시작이 1234면 2볼
5234 2볼 5는 아웃.
6234 3볼 6은 볼
7234
8234
9234
이래서 음 156789에 대해서만 확인이 가능하다.
그럼 이렇게 해서 볼,스트라이크를 찾고 아웃도 알게 된다. 뒤에 세자리는 아웃으로 넣고 순열로 돌려서 확인하면 오래걸린다.
2467
0123 1볼
4567 1볼2스트라이크
8901 아웃들.
1,2번째 숫자열에 아웃을 하나씩 자리를 옮기며 넣어보면 각 숫자가 뭔지 알 수 있다.
9047
일단 아웃을 찾자.
0123 1볼
찾은게 1개밖에 없으니까 싹 갈아업자?
4567 1스트라이크 1볼
음 두개는 있다.
8901 2볼
그럼 4567, 8901 합치면 올바른 공이 4개 있는거!
8P4 는 아니고 ㅋㅋ
음 012389 도 맞는데
음 이렇게 찾긴 힘들다.
0-9 10개니까
9047
0123 1볼
4123 1볼
5123 5아웃 0,4가 볼이 였음이 밝혀짐... 이거 반대인 경우가.
6123 6아웃
7123 1볼
8123 8아웃
9123 1스트라이크
9057
0123 1볼
4123 4아웃
5123 1볼
6123 6아웃
7123 1볼
8123 8아웃
9123 9스트라이크
1570
a 0123 : 2볼
b 4567 : 1스트라이크 1볼
c 8901 : 2볼
ab 또는 bc가 스트라이크 볼 합쳐서 4개이다. 즉 ab에 의하면 89는 아웃. bc에 의하면 23은 아웃
즉 a는 01이볼 b는 몰라 c는 01이 볼.
4567 ->
1스트1볼
8567 ->
1스트 1볼
4867 ->
1볼 5가 스트라이크~
4587 ->
4568
0123456789
0126
0123 3스
4567 1볼
8901 2볼
8923 1스
0126
0123 3스
2345 1볼
4567 1볼
6789 1볼
8910 2볼
아 이런식으로 하는게 아닌거 같다. 도저히 모르겠다.
7401
0123 : 2볼 , 2개 공은 위치가 틀린 공이고,2개 공은 여기 있으면 안되는 공이다.
4567 : 2볼
89 는 아웃이네
8123 -> 0812 -> 3081 -> 2308
뭔가 쿼리한번 했을때 얻는 정보를 최대로 사용해야 되는거 같은데. 그러려면 일단 다 저장해야 될듯?
답이 6371
0123 2볼 -> 0,1,2,3 모두 확률이 0.5이다.
4567 2볼 -> 4,5,6,7 모두 확률이 0.5이다.
89는 아웃 -> 이런식으로 하면 일단 4개 숫자중 볼이 2개인거 까지는 금방 찾는다.
2345 1스트라이크
0167 3볼 -> 이런식으로 3개까지 모을 수 있다.
0347 1스1볼
1256 2볼
------------------------------------------
안되는 경우는
답이 2406
2345 1스1볼
0167 2볼
0347 2볼
1256 1스1볼
2167 3볼
0367 1스2볼
1367 1스3볼
7316 1스3볼
6371 정답
89는 아웃.
다시 해본다.!!~~ 프로그래머스에서 완전탐색으로 풀고 왔는데 위에서 처럼 조건을 따져보려니 너무 많아서 나도 완탐으로 해보자...
프로그래머스에서 한 코드 기반으로 했는데 프로그래머스에서 조건을 잘 못 걸었던거 같다. 그리고 헤더파일 사용했었어서 다시 수정해야 한다.....ㅋㅋ
#define N 4
#include <string>
#include <vector>
#include<queue>
using namespace std;
int arr[10];
queue<vector<int>> q;
queue<vector<int>> q2;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void perm(int arr[], int n, int r, int depth) {
if (r == depth) {
vector<int> tmp;
tmp.push_back(arr[0]);
tmp.push_back(arr[1]);
tmp.push_back(arr[2]);
tmp.push_back(arr[3]);
if (arr[0] == 8 && arr[1] == 9 && arr[2] == 7 && arr[3] == 5) {
int a = 1;
}
q.push(tmp);
return;
}
for (int i = depth; i < n; i++) {
swap(&arr[i], &arr[depth]);
perm(arr, n, r, depth + 1);
swap(&arr[i], &arr[depth]);
}
}
void init() {
while (!q.empty()) q.pop();
while (!q2.empty()) q2.pop();
for (int i = 0; i < 10; i++) {
arr[i] = i;
}
perm(arr, 10, 4, 0);
}
struct SB {
int strike = 0;
int ball = 0;
};
SB compare(vector<int>a, vector<int>b) {
SB tmp;
if (b[0] == 8 && b[1] == 9 && b[2] == 7 && b[3] == 5) {
int a= 1;
}
for (int i = 0; i < 3; i++) {
if (a[i] == b[i]) {
tmp.strike += 1;
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i != j && a[i] == b[j]) {
tmp.ball++;
}
}
}
return tmp;
}
void getRidof(vector<int> baseball, int strike, int ball) {
SB result;
while (!q.empty()) {
vector<int> frontVec = q.front();
result = compare(baseball, frontVec);
if (result.strike <= strike && result.ball <= ball) {
q2.push(frontVec);;
}
else {
;
}
q.pop();
}
while (!q2.empty()) {
q.push(q2.front());
q2.pop();
}
}
vector<int> getVec(int x) {
vector<int> tmp;
string str = to_string(x);
tmp.push_back(str[0] - '0');
tmp.push_back(str[1] - '0');
tmp.push_back(str[2] - '0');
return tmp;
}
typedef struct {
int strike;
int ball;
} Result;
extern Result query(int guess[]);
vector<int> createNewVec() {
vector<int> tmp;
return q.front();
}
void doUserImplementation(int guess[]) {
init();
vector<int> throwBall;
while (q.size() != 1) {
throwBall = createNewVec();
int throwBallArr[4];
for (int i = 0; i < 4; i++) {
throwBallArr[i] = throwBall[i];
}
Result res = query(throwBallArr);
if (res.strike == 4) {
for (int i = 0; i < 4; i++) {
guess[i] = throwBall[i];
}
return;
}
else {
q.pop();
}
getRidof(throwBall, res.strike, res.ball);
}
}
'알고리즘 문제 풀기' 카테고리의 다른 글
| swexpertacademy - 1770. 블록 부품 맞추기 (0) | 2020.01.14 |
|---|---|
| 프로그래머스 - 정렬 : K번째 수, 가장 큰 수, H index (0) | 2020.01.13 |
| swexpertacademy - 9088. 다이아몬드,8998. 세운이는 내일 할거야, 8993. 하지 추측 (0) | 2020.01.06 |
| 프로그래머스 - 힙 : 더 맵게,라면 공장, 디스크 컨트롤러 (0) | 2020.01.05 |
| 프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽) (0) | 2020.01.04 |