[programmers] ์คํฌํธ๋ฆฌ - Java
์ฃผ์ด์ง ์ ํ ์คํฌ ์์์ ๋ฐ๋ผ ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ก, ์คํฌํธ๋ฆฌ์ ๊ฐ ์คํฌ์ด ์ฌ๋ฐ๋ฅธ ์์๋ก ๋ฐฐ์์ก๋์ง๋ฅผ ํ์ธํ๋ ๋ฐฉ๋ฒ์ ์ค๋ช
ํ๋ค. ์์๋ก๋ "BACDE", "CBADF", "AECB", "BDA"๊ฐ ์ฃผ์ด์ก์ผ๋ฉฐ, ์ ํจํ ์คํฌํธ๋ฆฌ๋ 2๊ฐ์ด๋ค. ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์คํฌํธ๋ฆฌ์ ๊ฐ ๋ฌธ์๋ฅผ ํ์ธํ์ฌ ์ ํ ์คํฌ ์์์ ๋น๊ตํ๋ ๊ฒ์ด๋ค.
Sep 30, 2024
์คํฌํธ๋ฆฌ
๋ฌธ์ ์ค๋ช
์ ํ ์คํฌ์ด๋ ์ด๋ค ์คํฌ์ ๋ฐฐ์ฐ๊ธฐ ์ ์ ๋จผ์ ๋ฐฐ์์ผ ํ๋ ์คํฌ์ ๋ปํฉ๋๋ค.
์๋ฅผ ๋ค์ด ์ ํ ์คํฌ ์์๊ฐ
์คํํฌ โ ๋ผ์ดํธ๋ ๋ณผํธ โ ์ฌ๋
์ผ๋, ์ฌ๋๋ฅผ ๋ฐฐ์ฐ๋ ค๋ฉด ๋จผ์ ๋ผ์ดํธ๋ ๋ณผํธ๋ฅผ ๋ฐฐ์์ผ ํ๊ณ , ๋ผ์ดํธ๋ ๋ณผํธ๋ฅผ ๋ฐฐ์ฐ๋ ค๋ฉด ๋จผ์ ์คํํฌ๋ฅผ ๋ฐฐ์์ผ ํฉ๋๋ค.์ ์์์ ์๋ ๋ค๋ฅธ ์คํฌ(ํ๋ง ๋ฑ)์ ์์์ ์๊ด์์ด ๋ฐฐ์ธ ์ ์์ต๋๋ค. ๋ฐ๋ผ์
์คํํฌ โ ํ๋ง โ ๋ผ์ดํธ๋ ๋ณผํธ โ ์ฌ๋
์ ๊ฐ์ ์คํฌํธ๋ฆฌ๋ ๊ฐ๋ฅํ์ง๋ง, ์ฌ๋ โ ์คํํฌ
๋ ๋ผ์ดํธ๋ ๋ณผํธ โ ์คํํฌ โ ํ๋ง โ ์ฌ๋
์ ๊ฐ์ ์คํฌํธ๋ฆฌ๋ ๋ถ๊ฐ๋ฅํฉ๋๋ค.์ ํ ์คํฌ ์์ skill๊ณผ ์ ์ ๋ค์ด ๋ง๋ ์คํฌํธ๋ฆฌ1๋ฅผ ๋ด์ ๋ฐฐ์ด skill_trees๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ ๊ฐ์๋ฅผ return ํ๋ solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ ์กฐ๊ฑด
- ์คํฌ์ ์ํ๋ฒณ ๋๋ฌธ์๋ก ํ๊ธฐํ๋ฉฐ, ๋ชจ๋ ๋ฌธ์์ด์ ์ํ๋ฒณ ๋๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ์คํฌ ์์์ ์คํฌํธ๋ฆฌ๋ ๋ฌธ์์ด๋ก ํ๊ธฐํฉ๋๋ค.
- ์๋ฅผ ๋ค์ด,
C โ B โ D
๋ผ๋ฉด "CBD"๋ก ํ๊ธฐํฉ๋๋ค
- ์ ํ ์คํฌ ์์ skill์ ๊ธธ์ด๋ 1 ์ด์ 26 ์ดํ์ด๋ฉฐ, ์คํฌ์ ์ค๋ณตํด ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- skill_trees๋ ๊ธธ์ด 1 ์ด์ 20 ์ดํ์ธ ๋ฐฐ์ด์ ๋๋ค.
- skill_trees์ ์์๋ ์คํฌ์ ๋ํ๋ด๋ ๋ฌธ์์ด์ ๋๋ค.
- skill_trees์ ์์๋ ๊ธธ์ด๊ฐ 2 ์ด์ 26 ์ดํ์ธ ๋ฌธ์์ด์ด๋ฉฐ, ์คํฌ์ด ์ค๋ณตํด ์ฃผ์ด์ง์ง ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
skill | skill_trees | return |
"CBD" | ["BACDE", "CBADF", "AECB", "BDA"] | 2 |
์ ์ถ๋ ฅ ์ ์ค๋ช
- "BACDE": B ์คํฌ์ ๋ฐฐ์ฐ๊ธฐ ์ ์ C ์คํฌ์ ๋จผ์ ๋ฐฐ์์ผ ํฉ๋๋ค. ๋ถ๊ฐ๋ฅํ ์คํฌํธ๋ฆฝ๋๋ค.
- "CBADF": ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ์ ๋๋ค.
- "AECB": ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ์ ๋๋ค.
- "BDA": B ์คํฌ์ ๋ฐฐ์ฐ๊ธฐ ์ ์ C ์คํฌ์ ๋จผ์ ๋ฐฐ์์ผ ํฉ๋๋ค. ๋ถ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ์ ๋๋ค.
solution.java
import java.util.*; class Solution { public int solution(String skill, String[] skill_trees) { int validCount = 0; // ๋ฐฐ์ด์ ๊ฐ ์คํฌ ํธ๋ฆฌ๋ฅผ ๋ฃจํ for (String skillTree : skill_trees) { if (isValidSkillTree(skill, skillTree)) { validCount++; } } return validCount; } private boolean isValidSkillTree(String skill, String skillTree) { int skillIndex = 0; // ์คํฌํธ๋ฆฌ์ ์ฒซ ๋ฒ์งธ ์คํฌ๋ถํฐ ํ์ธ ์์ // ์คํฌ ํธ๋ฆฌ์ ๊ฐ ๋ฌธ์๋ฅผ ๋ฐ๋ณต for (char c : skillTree.toCharArray()) { int currentSkillPos = skill.indexOf(c); // ํ์ฌ ์คํฌ์ด ์คํฌ ํธ๋ฆฌ์ ์๋ ๊ฒฝ์ฐ if (currentSkillPos != -1) { // ๋ฐฐ์ฐ์ง ์์ ์คํฌ์ด ์๋ค๋ฉด ๋ถ๊ฐ๋ฅํ ์คํฌํธ๋ฆฌ๋ค if (currentSkillPos != skillIndex) { return false; } // ๋ค์ ๋ฐฐ์ธ ์คํฌ๋ก ์ธ๋ฑ์ค๋ฅผ ์ด๋ skillIndex++; } } // ํ์ฌ ์คํฌ์ด ์คํฌ ํธ๋ฆฌ์ ์๋ ๊ฒฝ์ฐ return true; } }
ํต์ฌ ํค์๋
- ์คํฌํธ๋ฆฌ์ ๊ฐ ์บ๋ฆญํฐ๋ฅผ ํ์ธํ์ฌ ์คํฌ์์์ ํด๋น ์์น์ ๋น๊ตํ ์ ์๋ค.
- ์คํฌ์ด ์์๋๋ก ๋์ค์ง ์์ ๊ฒฝ์ฐ ํด๋น ํธ๋ฆฌ๋ ๋ถ๊ฐ๋ฅํ๋ค.
๊ฒฐ๋ก !
ํ์ฌ ์คํฌ์ด ํ์ ์์์ ์ผ๋ถ์ธ์ง ์ฒดํฌํ๊ณ , ๋ค๋ฅธ ์คํฌ๊ณผ ๋น๊ตํ์ฌ ์ฌ๋ฐ๋ฅธ ์์น์ ์๋์ง ํ์ธํ๋ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํ ์ ์์๋ค.
Share article