You have to fight many times! There is no one able to tell you when you will be encounter the legendary amazon... You have to prove yourself before she comes!
There is a little possibility to encounter her, this means you have to spend some APs to find her (if you are lucky she will appear at first 10 if you are not you can spend even 24 APs and still nothing).
One suggestion for this step! If you are not sure that you will be able to take her down when you will meet her, keep your mercs with full health and spirit and combined attribute potions. This way you will have the most possibilities to win the battle and not have to search for her again.
For me one time spend more than 40 APs to get her (I was really unlucky) and the other I was lucky since I got her at 5th fight!