๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 11์ผ์ฐจ TIL - ์นด๋“œ ๋ญ‰์น˜

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

99Club Coding Test Study

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

โณ๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

์ฝ”๋‹ˆ๋Š” ์˜์–ด ๋‹จ์–ด๊ฐ€ ์ ํžŒ ์นด๋“œ ๋ญ‰์น˜ ๋‘ ๊ฐœ๋ฅผ ์„ ๋ฌผ๋กœ ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. ์ฝ”๋‹ˆ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์œผ๋กœ ์นด๋“œ์— ์ ํžŒ ๋‹จ์–ด๋“ค์„ ์‚ฌ์šฉํ•ด ์›ํ•˜๋Š” ์ˆœ์„œ์˜ ๋‹จ์–ด ๋ฐฐ์—ด์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š”์ง€ ์•Œ๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.

  • ์›ํ•˜๋Š” ์นด๋“œ ๋ญ‰์น˜์—์„œ ์นด๋“œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ํ•œ ์žฅ์”ฉ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
  • ํ•œ ๋ฒˆ ์‚ฌ์šฉํ•œ ์นด๋“œ๋Š” ๋‹ค์‹œ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ์นด๋“œ๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๋‹ค์Œ ์นด๋“œ๋กœ ๋„˜์–ด๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ๊ธฐ์กด์— ์ฃผ์–ด์ง„ ์นด๋“œ ๋ญ‰์น˜์˜ ๋‹จ์–ด ์ˆœ์„œ๋Š” ๋ฐ”๊ฟ€ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ์ฒซ ๋ฒˆ์งธ ์นด๋“œ ๋ญ‰์น˜์— ์ˆœ์„œ๋Œ€๋กœ ["i", "drink", "water"], ๋‘ ๋ฒˆ์งธ ์นด๋“œ ๋ญ‰์น˜์— ์ˆœ์„œ๋Œ€๋กœ ["want", "to"]๊ฐ€ ์ ํ˜€์žˆ์„ ๋•Œ ["i", "want", "to", "drink", "water"] ์ˆœ์„œ์˜ ๋‹จ์–ด ๋ฐฐ์—ด์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค๋ฉด ์ฒซ ๋ฒˆ์งธ ์นด๋“œ ๋ญ‰์น˜์—์„œ "i"๋ฅผ ์‚ฌ์šฉํ•œ ํ›„ ๋‘ ๋ฒˆ์งธ ์นด๋“œ ๋ญ‰์น˜์—์„œ "want"์™€ "to"๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ์ฒซ ๋ฒˆ์งธ ์นด๋“œ๋ญ‰์น˜์— "drink"์™€ "water"๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ์‚ฌ์šฉํ•˜๋ฉด ์›ํ•˜๋Š” ์ˆœ์„œ์˜ ๋‹จ์–ด ๋ฐฐ์—ด์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฌธ์ž์—ด๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฐฐ์—ด cards1, cards2์™€ ์›ํ•˜๋Š” ๋‹จ์–ด ๋ฐฐ์—ด goal์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, cards1๊ณผ cards2์— ์ ํžŒ ๋‹จ์–ด๋“ค๋กœ goal๋ฅผ ๋งŒ๋“ค ์žˆ๋‹ค๋ฉด "Yes"๋ฅผ, ๋งŒ๋“ค ์ˆ˜ ์—†๋‹ค๋ฉด "No"๋ฅผ returnํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • 1 โ‰ค cards1์˜ ๊ธธ์ด, cards2์˜ ๊ธธ์ด โ‰ค 10
  • 1 โ‰ค cards1[i]์˜ ๊ธธ์ด, cards2[i]์˜ ๊ธธ์ด โ‰ค 10
  • cards1๊ณผ cards2์—๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ๋‹จ์–ด๋งŒ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.
  • 2 โ‰ค goal์˜ ๊ธธ์ด โ‰ค cards1์˜ ๊ธธ์ด + cards2์˜ ๊ธธ์ด
  • 1 โ‰ค goal[i]์˜ ๊ธธ์ด โ‰ค 10
  • goal์˜ ์›์†Œ๋Š” cards1๊ณผ cards2์˜ ์›์†Œ๋“ค๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • cards1, cards2, goal์˜ ๋ฌธ์ž์—ด๋“ค์€ ๋ชจ๋‘ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

cards1cards2goalresult
["i", "drink", "water"]["want", "to"]["i", "want", "to", "drink", "water"]"Yes"
["i", "water", "drink"]["want", "to"]["i", "want", "to", "drink", "water"]"No"

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

๋ณธ๋ฌธ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

cards1์—์„œ "i"๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  cards2์—์„œ "want"์™€ "to"๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ "i want to"๊นŒ์ง€๋Š” ๋งŒ๋“ค ์ˆ˜ ์žˆ์ง€๋งŒ "water"๊ฐ€ "drink"๋ณด๋‹ค ๋จผ์ € ์‚ฌ์šฉ๋˜์–ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ•ด๋‹น ๋ฌธ์žฅ์„ ์™„์„ฑ์‹œํ‚ฌ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ "No"๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.


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

3๊ฐœ์˜ ๋ฐฐ์—ด์ด ์ฃผ์–ด์ ธ ์žˆ๊ณ , goal๋ฐฐ์—ด๊ณผ ๋‚˜๋จธ์ง€ ๋‘ ๋ฐฐ์—ด์˜ ์š”์†Œ๋ฅผ ๋น„๊ตํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ๋ผ, ๊ฐ๊ฐ์˜ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋ฅผ ์ž˜ ํ™œ์šฉํ•˜๊ธฐ๋งŒ ํ•˜๋ฉด ๋ฌธ์ œ๋ฅผ ํ’€ ์ˆ˜ ์žˆ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes";
        int cards1Index = 0;
        int cards2Index = 0;
        int goalIndex = 0;
        
        for (goalIndex = 0; goalIndex < goal.length; goalIndex++) {
            
            // ์นด๋“œ1์— ๋“ค์–ด ์žˆ๋‹ค๋ฉด
            if (cards1Index < cards1.length && goal[goalIndex].equals(cards1[cards1Index])) {
                cards1Index++;
            }
            
            // ์นด๋“œ2์— ๋“ค์–ด ์žˆ๋‹ค๋ฉด
            else if (cards2Index < cards2.length && goal[goalIndex].equals(cards2[cards2Index])) {
                cards2Index++;
            }
            else {
                answer = "No";
            }
        }
        
        return answer;
    }
}

๊ทธ๋ž˜์„œ ๊ฐ๊ฐ์˜ ์ธ๋ฑ์Šค cards1Index, cards2Index, goalIndex๋ฅผ ๋งŒ๋“ค์–ด ์ฃผ์—ˆ๋‹ค.

์ด์ œ, ๋‘ ๊ฐœ์˜ ์นด๋“œ ๋ญ‰์น˜์—์„œ ์ˆœ์„œ๋Œ€๋กœ ํ•œ ์žฅ์”ฉ ํ™•์ธํ•ด goal์˜ ๋ฌธ์žฅ์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ์ง€ ํ™•์ธ์„ ํ•ด์•ผ ํ•œ๋‹ค.

์ด๋ฅผ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด, goalIndex๋ฅผ 0๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์˜ฎ๊ฒจ๊ฐ€๋ฉฐ, ๋‘ ์นด๋“œ ๋ญ‰์น˜์—์„œ ๊บผ๋‚ธ ์นด๋“œ ์ค‘ ์ผ์น˜ํ•˜๋Š” ์ง€ ํ™•์ธ์‹œ์ผœ ๋ณด๋„๋ก ํ•˜์˜€๋‹ค.

if (cards1Index < cards1.length && goal[goalIndex].equals(cards1[cards1Index])) {
	cards1Index++;
}

else if (cards2Index < cards2.length && goal[goalIndex].equals(cards2[cards2Index])) {
	cards2Index++;
}

๋งŒ์•ฝ cards1 ๋ญ‰์น˜์—์„œ ๊ฐ™์€ ๋ฌธ์ž์—ด์„ ๋ฐœ๊ฒฌํ•œ๋‹ค๋ฉด, cards1์˜ ์ธ๋ฑ์Šค๋ฅผ 1 ์ฆ๊ฐ€์‹œ์ผœ ํ•ด๋‹น ์นด๋“œ๋Š” ์ด๋ฏธ ํ™•์ธํ–ˆ์Œ์„ ๊ตฌํ˜„ํ•ด ์ฃผ์—ˆ๊ณ , card2์˜ ๊ฒฝ์šฐ๋„ ๋™์ผํ•˜๊ฒŒ ๊ตฌํ˜„ํ•ด ์ฃผ์—ˆ๋‹ค.

๋งˆ์ง€๋ง‰์œผ๋กœ ๋‘˜ ์ค‘ ์–ด๋Š ์กฐ๊ฑด๋ฌธ์—๋„ ํ•ด๋‹นํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด, goal์˜ ๋ฌธ์žฅ์„ ๋งŒ๋“ค ์ˆ˜ ์—†๋‹ค๋Š” ์˜๋ฏธ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ด ๊ฒฝ์šฐ์—๋Š” answer์— No๋ฅผ ์ €์žฅํ•˜๋„๋ก ํ•ด์คŒ์œผ๋กœ์จ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค๐Ÿ˜€


๋‹ค๋ฅธ ํ’€์ด

๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ๋Š”, ArrayList๋ฅผ ํ™œ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค.

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes";
        ArrayList cards1List = new ArrayList(Arrays.asList(cards1));
        ArrayList cards2List = new ArrayList(Arrays.asList(cards2));

        for(int i=0; i < goal.length; i++) {
            if( cards1List.size() > 0 && goal[i].equals(cards1List.get(0))){
                cards1List.remove(0);
            } else if (cards2List.size() > 0 && goal[i].equals(cards2List.get(0))){
                cards2List.remove(0);
            } else {
                answer = "No";
            }
        }
        return answer;
    }
}

๋‘ ์นด๋“œ ๋ญ‰์น˜๋ฅผ ๊ฐ๊ฐ์˜ ArrayList์— ๋‹ด์€ ๋‹ค์Œ, get()ํ•จ์ˆ˜๋กœ ๋งจ ์•ž ์นด๋“œ๋ฅผ ํ™•์ธํ•ด, goal์˜ ๋ฌธ์ž์—ด๊ณผ ๊ฐ™๋‹ค๋ฉด, ํ•ด๋‹น ์นด๋“œ๋ฅผ ArrayList์—์„œ ์ œ๊ฑฐํ•ด ์ฃผ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

๋ฌผ๋ก , ์ด ๋ฐฉ๋ฒ•์€ ์ƒˆ๋กœ์šด ArrayList๊ฐ์ฒด๋ฅผ ์ƒ์„ฑํ•ด์•ผ ํ•ด์„œ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ์ด ๋” ๋งŽ๊ณ , remove()๋ฉ”์„œ๋“œ๋ฅผ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ ์‹œ๊ฐ„ ๋ณต์žก๋„๋„ O(n)O(n)์œผ๋กœ ๋ฐฐ์—ด์„ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ–ˆ์„ ๋•Œ๋ณด๋‹ค ํšจ์œจ์„ฑ์ด ์กฐ๊ธˆ ๋–จ์–ด์ง„๋‹ค.


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

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

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

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

Awesome ๐Ÿ˜š

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