Per TIMATIC, the database used by airlines;
TWOV (Transit Without Visa):
Visa required, except for Passengers transiting through Seoul
(ICN) with a confirmed onward ticket for a flight to a third
country within 24 hours. They must stay in the international
transit area of the airport and have documents required for
the next destination.
However, with separate tickets, the check-in staff will likely treat Seoul as your final destination, and thus deny you boarding without a visa.
On what airline is your Naha-Seoul flight? You need to contact the handling agent in Naha for that airline.