๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 26์ผ์ฐจ TIL - ๋‹ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ

HOONSSACยท2024๋…„ 8์›” 16์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
26/41
post-thumbnail

โณ๋ฌธ์ œ

์–€์—์„œ๋Š” ๋งค๋…„ ๋‹ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ๊ฐ€ ์—ด๋ฆฝ๋‹ˆ๋‹ค. ํ•ด์„ค์ง„๋“ค์€ ์„ ์ˆ˜๋“ค์ด ์ž๊ธฐ ๋ฐ”๋กœ ์•ž์˜ ์„ ์ˆ˜๋ฅผ ์ถ”์›”ํ•  ๋•Œ ์ถ”์›”ํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ๋ถ€๋ฆ…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 1๋“ฑ๋ถ€ํ„ฐ 3๋“ฑ๊นŒ์ง€ "mumu", "soe", "poe" ์„ ์ˆ˜๋“ค์ด ์ˆœ์„œ๋Œ€๋กœ ๋‹ฌ๋ฆฌ๊ณ  ์žˆ์„ ๋•Œ, ํ•ด์„ค์ง„์ด "soe"์„ ์ˆ˜๋ฅผ ๋ถˆ๋ €๋‹ค๋ฉด 2๋“ฑ์ธ "soe" ์„ ์ˆ˜๊ฐ€ 1๋“ฑ์ธ "mumu" ์„ ์ˆ˜๋ฅผ ์ถ”์›”ํ–ˆ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ฆ‰ "soe" ์„ ์ˆ˜๊ฐ€ 1๋“ฑ, "mumu" ์„ ์ˆ˜๊ฐ€ 2๋“ฑ์œผ๋กœ ๋ฐ”๋€๋‹ˆ๋‹ค.

์„ ์ˆ˜๋“ค์˜ ์ด๋ฆ„์ด 1๋“ฑ๋ถ€ํ„ฐ ํ˜„์žฌ ๋“ฑ์ˆ˜ ์ˆœ์„œ๋Œ€๋กœ ๋‹ด๊ธด ๋ฌธ์ž์—ด ๋ฐฐ์—ด players์™€ ํ•ด์„ค์ง„์ด ๋ถ€๋ฅธ ์ด๋ฆ„์„ ๋‹ด์€ ๋ฌธ์ž์—ด ๋ฐฐ์—ด callings๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๊ฒฝ์ฃผ๊ฐ€ ๋๋‚ฌ์„ ๋•Œ ์„ ์ˆ˜๋“ค์˜ ์ด๋ฆ„์„ 1๋“ฑ๋ถ€ํ„ฐ ๋“ฑ์ˆ˜ ์ˆœ์„œ๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

๐Ÿšจ์ œํ•œ ์‚ฌํ•ญ

  • 5 โ‰ค players์˜ ๊ธธ์ด โ‰ค 50,000
  • players[i]๋Š” i๋ฒˆ์งธ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
  • players์˜ ์›์†Œ๋“ค์€ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • players์—๋Š” ์ค‘๋ณต๋œ ๊ฐ’์ด ๋“ค์–ด๊ฐ€ ์žˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • 3 โ‰ค players[i]์˜ ๊ธธ์ด โ‰ค 10
  • 2 โ‰ค callings์˜ ๊ธธ์ด โ‰ค 1,000,000
  • callings๋Š” players์˜ ์›์†Œ๋“ค๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฒฝ์ฃผ ์ง„ํ–‰์ค‘ 1๋“ฑ์ธ ์„ ์ˆ˜์˜ ์ด๋ฆ„์€ ๋ถˆ๋ฆฌ์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

๐Ÿ“ƒ์ž…์ถœ๋ ฅ ์˜ˆ

playerscallingsresult
["mumu", "soe", "poe", "kai", "mine"]["kai", "kai", "mine", "mine"]["mumu", "kai", "mine", "soe", "poe"]

๐Ÿ“ƒ์„ค๋ช…

4๋“ฑ์ธ "kai" ์„ ์ˆ˜๊ฐ€ 2๋ฒˆ ์ถ”์›”ํ•˜์—ฌ 2๋“ฑ์ด ๋˜๊ณ  ์•ž์„œ 3๋“ฑ, 2๋“ฑ์ธ "poe", "soe" ์„ ์ˆ˜๋Š” 4๋“ฑ, 3๋“ฑ์ด ๋ฉ๋‹ˆ๋‹ค. 5๋“ฑ์ธ "mine" ์„ ์ˆ˜๊ฐ€ 2๋ฒˆ ์ถ”์›”ํ•˜์—ฌ 4๋“ฑ, 3๋“ฑ์ธ "poe", "soe" ์„ ์ˆ˜๊ฐ€ 5๋“ฑ, 4๋“ฑ์ด ๋˜๊ณ  ๊ฒฝ์ฃผ๊ฐ€ ๋๋‚ฉ๋‹ˆ๋‹ค. 1๋“ฑ๋ถ€ํ„ฐ ๋ฐฐ์—ด์— ๋‹ด์œผ๋ฉด ["mumu", "kai", "mine", "soe", "poe"]์ด ๋ฉ๋‹ˆ๋‹ค.


โœ๏ธํ’€์ด

์ฒซ ๋ฒˆ์งธ ์‹œ๋„

class Solution {
    public String[] solution(String[] players, String[] callings) {
        for (String called : callings) {
            for (int i = 1; i < players.length; i++) {
                if (players[i].equals(called)) {
                    String temp = players[i - 1];
                    players[i - 1] = players[i];
                    players[i] = temp;
                }
            }
        }

        return players;
    }
}

์ด์ค‘ for๋ฌธ์„ ์‚ฌ์šฉํ•˜๋‹ˆ ์—ญ์‹œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜์˜€๋‹ค.
ํƒ์ƒ‰ ์‹œ๊ฐ„์„ ๋‹จ์ถ•์‹œํ‚ค๊ธฐ ์œ„ํ•ด HashMap์„ ์‚ฌ์šฉํ•ด๋ณด๊ธฐ๋กœ ํ–ˆ๋‹ค.

๐Ÿ‘พ์ตœ์ข… ์ฝ”๋“œ

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> ranking = new HashMap<>();

        // ์ดˆ๊ธฐ ์ˆœ์œ„ ๋ฐ์ดํ„ฐ ์ €์žฅ
        for (int i = 0; i < players.length; i++) {
            ranking.put(players[i], i);
        }

        for (String called : callings) {
            // ์ด๋ฆ„์ด ๋ถˆ๋ฆฐ ์„ ์ˆ˜ ์ธ๋ฑ์Šค ์ถ”์ถœ
            int calledRank = ranking.get(called);

            // players ๋ฐฐ์—ด์—์„œ ์ˆœ์œ„ ๋ณ€๊ฒฝ
            String catched = players[calledRank - 1];
            players[calledRank - 1] = players[calledRank];
            players[calledRank] = catched;

            // HashMap ์ˆœ์œ„ ์—…๋ฐ์ดํŠธ
            ranking.put(catched, ranking.get(catched) + 1);
            ranking.put(called, ranking.get(called) - 1);


        }

        return players;
    }
}

์„ ์ˆ˜ ์ด๋ฆ„๊ณผ ๋“ฑ์ˆ˜๋ฅผ key-value๋กœ ๊ฐ€์ง€๋Š” HashMap์„ ํ•˜๋‚˜ ์ƒ์„ฑํ•ด์ค€ ํ›„, ์ดˆ๊ธฐ ์ˆœ์œ„ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•ด ์ฃผ์—ˆ๋‹ค.

callings ๋ฐฐ์—ด์„ ํ•˜๋‚˜์”ฉ ์ˆœํšŒํ•˜๋ฉด์„œ, ์ด๋ฆ„์ด ๋ถˆ๋ฆฐ ์„ ์ˆ˜์˜ ์ธ๋ฑ์Šค๋ฅผ HashMap์œผ๋กœ๋ถ€ํ„ฐ ๊ฐ€์ ธ์™€ players ๋ฐฐ์—ด์˜ ์ˆœ์œ„๋ฅผ ๋จผ์ € ๋ฐ”๊พธ์–ด ์ฃผ์—ˆ๋‹ค.

๋งˆ์ง€๋ง‰์œผ๋กœ HashMap์—์„œ ๋”ฐ๋ผ ์žกํžŒ ์‚ฌ๋žŒ์˜ value(๋“ฑ์ˆ˜)์— 1์„ ๋”ํ•ด์ฃผ๊ณ ,
๋”ฐ๋ผ ์žก์€ ์‚ฌ๋žŒ์˜ value(๋“ฑ์ˆ˜)์— 1์„ ๋นผ์ฃผ๋ฉด,
ํ˜„์žฌ ์ˆœ์œ„๊ฐ€ ์—…๋ฐ์ดํŠธ ๋จ์œผ๋กœ์จ, ์ˆœ์œ„ ๊ต์ฒด ์ž‘์—…์ด ๋๋‚˜๊ฒŒ ๋œ๋‹ค.

HashMap์„ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ, key(์„ ์ˆ˜ ์ด๋ฆ„)๊ฐ’์— ๋Œ€ํ•œ value(๋“ฑ์ˆ˜)๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์‹œ๊ฐ„์„ ํ‰๊ท  O(1)O(1)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ์ค„์ผ ์ˆ˜ ์žˆ์–ด์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.๐Ÿ˜Ž


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 16์ผ

๐Ÿ‡๐Ÿ‡๐Ÿ‡๋‹ฌ๋ ค๋ผ ๋‹ฌ๋ ท...!

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ