[programmers] ์Šคํ‚ฌํŠธ๋ฆฌ - Java

์ฃผ์–ด์ง„ ์„ ํ–‰ ์Šคํ‚ฌ ์ˆœ์„œ์— ๋”ฐ๋ผ ๊ฐ€๋Šฅํ•œ ์Šคํ‚ฌํŠธ๋ฆฌ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ, ์Šคํ‚ฌํŠธ๋ฆฌ์˜ ๊ฐ ์Šคํ‚ฌ์ด ์˜ฌ๋ฐ”๋ฅธ ์ˆœ์„œ๋กœ ๋ฐฐ์›Œ์กŒ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ๋‹ค. ์˜ˆ์‹œ๋กœ๋Š” "BACDE", "CBADF", "AECB", "BDA"๊ฐ€ ์ฃผ์–ด์กŒ์œผ๋ฉฐ, ์œ ํšจํ•œ ์Šคํ‚ฌํŠธ๋ฆฌ๋Š” 2๊ฐœ์ด๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์€ ์Šคํ‚ฌํŠธ๋ฆฌ์˜ ๊ฐ ๋ฌธ์ž๋ฅผ ํ™•์ธํ•˜์—ฌ ์„ ํ–‰ ์Šคํ‚ฌ ์ˆœ์„œ์™€ ๋น„๊ตํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
DriedPollack's avatar
Sep 30, 2024
[programmers] ์Šคํ‚ฌํŠธ๋ฆฌ - Java

์Šคํ‚ฌํŠธ๋ฆฌ

๋ฌธ์ œ ์„ค๋ช…

์„ ํ–‰ ์Šคํ‚ฌ์ด๋ž€ ์–ด๋–ค ์Šคํ‚ฌ์„ ๋ฐฐ์šฐ๊ธฐ ์ „์— ๋จผ์ € ๋ฐฐ์›Œ์•ผ ํ•˜๋Š” ์Šคํ‚ฌ์„ ๋œปํ•ฉ๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด ์„ ํ–‰ ์Šคํ‚ฌ ์ˆœ์„œ๊ฐ€ ์ŠคํŒŒํฌ โ†’ ๋ผ์ดํŠธ๋‹ ๋ณผํŠธ โ†’ ์ฌ๋”์ผ๋•Œ, ์ฌ๋”๋ฅผ ๋ฐฐ์šฐ๋ ค๋ฉด ๋จผ์ € ๋ผ์ดํŠธ๋‹ ๋ณผํŠธ๋ฅผ ๋ฐฐ์›Œ์•ผ ํ•˜๊ณ , ๋ผ์ดํŠธ๋‹ ๋ณผํŠธ๋ฅผ ๋ฐฐ์šฐ๋ ค๋ฉด ๋จผ์ € ์ŠคํŒŒํฌ๋ฅผ ๋ฐฐ์›Œ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์œ„ ์ˆœ์„œ์— ์—†๋Š” ๋‹ค๋ฅธ ์Šคํ‚ฌ(ํž๋ง ๋“ฑ)์€ ์ˆœ์„œ์— ์ƒ๊ด€์—†์ด ๋ฐฐ์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ŠคํŒŒํฌ โ†’ ํž๋ง โ†’ ๋ผ์ดํŠธ๋‹ ๋ณผํŠธ โ†’ ์ฌ๋”์™€ ๊ฐ™์€ ์Šคํ‚ฌํŠธ๋ฆฌ๋Š” ๊ฐ€๋Šฅํ•˜์ง€๋งŒ, ์ฌ๋” โ†’ ์ŠคํŒŒํฌ๋‚˜ ๋ผ์ดํŠธ๋‹ ๋ณผํŠธ โ†’ ์ŠคํŒŒํฌ โ†’ ํž๋ง โ†’ ์ฌ๋”์™€ ๊ฐ™์€ ์Šคํ‚ฌํŠธ๋ฆฌ๋Š” ๋ถˆ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
์„ ํ–‰ ์Šคํ‚ฌ ์ˆœ์„œ 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

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog