[programmers] ํŠœํ”Œ - Java

ํŠœํ”Œ์„ ํ‘œํ˜„ํ•˜๋Š” ๋ฌธ์ž์—ด s๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, s๋ฅผ ๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์—์„œ {{, }}๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  },{๋ฅผ ๊ตฌ๋ถ„์ž๋กœ ๋ถ„ํ• ํ•œ ํ›„, ๋ถ„ํ• ํ•œ ๋ฌธ์ž์—ด์„ ๊ธธ์ด๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ํ›„ ๊ฐ ๋ฌธ์ž์—ด์„ ,๋ฅผ ๊ตฌ๋ถ„์ž๋กœ ๋ถ„ํ• ํ•˜์—ฌ ์ •์ˆ˜๋ฅผ ์ถ”์ถœํ•˜๊ณ , ํ•œ ๋ฒˆ๋„ ๋“ฑ์žฅํ•˜์ง€ ์•Š์€ ์ˆ˜๋ฅผ ๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
DriedPollack's avatar
Mar 17, 2024
[programmers] ํŠœํ”Œ - Java

ํŠœํ”Œ

๋ฌธ์ œ ์„ค๋ช…

์…€์ˆ˜์žˆ๋Š” ์ˆ˜๋Ÿ‰์˜ ์ˆœ์„œ์žˆ๋Š” ์—ด๊ฑฐ ๋˜๋Š” ์–ด๋–ค ์ˆœ์„œ๋ฅผ ๋”ฐ๋ฅด๋Š” ์š”์†Œ๋“ค์˜ ๋ชจ์Œ์„ ํŠœํ”Œ(tuple)์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. n๊ฐœ์˜ ์š”์†Œ๋ฅผ ๊ฐ€์ง„ ํŠœํ”Œ์„ n-ํŠœํ”Œ(n-tuple)์ด๋ผ๊ณ  ํ•˜๋ฉฐ, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • (a1, a2, a3, ..., an)
ํŠœํ”Œ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ฑ์งˆ์„ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.
  1. ์ค‘๋ณต๋œ ์›์†Œ๊ฐ€ ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ex : (2, 3, 1, 2)
  1. ์›์†Œ์— ์ •ํ•ด์ง„ ์ˆœ์„œ๊ฐ€ ์žˆ์œผ๋ฉฐ, ์›์†Œ์˜ ์ˆœ์„œ๊ฐ€ ๋‹ค๋ฅด๋ฉด ์„œ๋กœ ๋‹ค๋ฅธ ํŠœํ”Œ์ž…๋‹ˆ๋‹ค. ex : (1, 2, 3) โ‰  (1, 3, 2)
  1. ํŠœํ”Œ์˜ ์›์†Œ ๊ฐœ์ˆ˜๋Š” ์œ ํ•œํ•ฉ๋‹ˆ๋‹ค.
์›์†Œ์˜ ๊ฐœ์ˆ˜๊ฐ€ n๊ฐœ์ด๊ณ , ์ค‘๋ณต๋˜๋Š” ์›์†Œ๊ฐ€ ์—†๋Š” ํŠœํ”Œ (a1, a2, a3, ..., an)์ด ์ฃผ์–ด์งˆ ๋•Œ(๋‹จ, a1, a2, ..., an์€ ์ž์—ฐ์ˆ˜), ์ด๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ง‘ํ•ฉ ๊ธฐํ˜ธ '{', '}'๋ฅผ ์ด์šฉํ•ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}
์˜ˆ๋ฅผ ๋“ค์–ด ํŠœํ”Œ์ด (2, 1, 3, 4)์ธ ๊ฒฝ์šฐ ์ด๋Š”
  • {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
์™€ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, ์ง‘ํ•ฉ์€ ์›์†Œ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€Œ์–ด๋„ ์ƒ๊ด€์—†์œผ๋ฏ€๋กœ
  • {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
  • {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
  • {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}
๋Š” ๋ชจ๋‘ ๊ฐ™์€ ํŠœํ”Œ (2, 1, 3, 4)๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
ํŠน์ • ํŠœํ”Œ์„ ํ‘œํ˜„ํ•˜๋Š” ์ง‘ํ•ฉ์ด ๋‹ด๊ธด ๋ฌธ์ž์—ด s๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, s๊ฐ€ ํ‘œํ˜„ํ•˜๋Š” ํŠœํ”Œ์„ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

[์ œํ•œ์‚ฌํ•ญ]

  • s์˜ ๊ธธ์ด๋Š” 5 ์ด์ƒ 1,000,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • s๋Š” ์ˆซ์ž์™€ '{', '}', ',' ๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ˆซ์ž๊ฐ€ 0์œผ๋กœ ์‹œ์ž‘ํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ์—†์Šต๋‹ˆ๋‹ค.
  • s๋Š” ํ•ญ์ƒ ์ค‘๋ณต๋˜๋Š” ์›์†Œ๊ฐ€ ์—†๋Š” ํŠœํ”Œ์„ ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ํ‘œํ˜„ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.
  • s๊ฐ€ ํ‘œํ˜„ํ•˜๋Š” ํŠœํ”Œ์˜ ์›์†Œ๋Š” 1 ์ด์ƒ 100,000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • return ํ•˜๋Š” ๋ฐฐ์—ด์˜ ๊ธธ์ด๊ฐ€ 1 ์ด์ƒ 500 ์ดํ•˜์ธ ๊ฒฝ์šฐ๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

[์ž…์ถœ๋ ฅ ์˜ˆ]

s
result
"{{2},{2,1},{2,1,3},{2,1,3,4}}"
[2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}"
[2, 1, 3, 4]
"{{20,111},{111}}"
[111, 20]
"{{123}}"
[123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}"
[3, 2, 4, 1]

์ž…์ถœ๋ ฅ ์˜ˆ์— ๋Œ€ํ•œ ์„ค๋ช…

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

๋ฌธ์ œ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

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

๋ฌธ์ œ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

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

(111, 20)์„ ์ง‘ํ•ฉ ๊ธฐํ˜ธ๋ฅผ ์ด์šฉํ•ด ํ‘œํ˜„ํ•˜๋ฉด {{111}, {111,20}}์ด ๋˜๋ฉฐ, ์ด๋Š” {{20,111},{111}}๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

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

(123)์„ ์ง‘ํ•ฉ ๊ธฐํ˜ธ๋ฅผ ์ด์šฉํ•ด ํ‘œํ˜„ํ•˜๋ฉด {{123}} ์ž…๋‹ˆ๋‹ค.

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

(3, 2, 4, 1)์„ ์ง‘ํ•ฉ ๊ธฐํ˜ธ๋ฅผ ์ด์šฉํ•ด ํ‘œํ˜„ํ•˜๋ฉด {{3},{3,2},{3,2,4},{3,2,4,1}}์ด ๋˜๋ฉฐ, ์ด๋Š” {{4,2,3},{3},{2,3,4,1},{2,3}}๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

solution.java

import java.util.*; class Solution { public ArrayList<Integer> solution(String s) { ArrayList<Integer> answer = new ArrayList<>(); s = s.substring(2, s.length() - 2); String[] sets = s.split("\\},\\{"); Arrays.sort(sets, Comparator.comparingInt(String::length)); for (String set : sets) { String[] elements = set.split(","); for (String element : elements) { int num = Integer.parseInt(element); if (!answer.contains(num)) answer.add(num); } } return answer; } }
 

ํ•ต์‹ฌ ํ‚ค์›Œ๋“œ

  • ๋ฌธ์ž์—ด์—์„œ {{, }}๋ฅผ ์ œ๊ฑฐํ•œ ํ›„, },{๋ฅผ ๊ตฌ๋ถ„์ž๋กœ ๋ฌธ์ž์—ด์„ ๋ถ„ํ• ํ•œ๋‹ค.
    • substring()๊ณผ split() ์„ ํ†ตํ•ด ๋ฌธ์ž์—ด์„ ์ œ๊ฑฐํ•˜๊ณ  ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ๋ถ„ํ• ํ•œ ๋ฌธ์ž์—ด์„ ๊ธธ์ด๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
    • Arrays.sort(), Comparator.comparingInt(String::length) ๋ฅผ ํ†ตํ•ด ์กฐ๊ฑด์ด ๋ถ™์€ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.
  • ๊ฐ๊ฐ์˜ ๋ฌธ์ž์—ด์„ ,๋ฅผ ๊ตฌ๋ถ„์ž๋กœ ๋ถ„ํ• ํ•ด์„œ ์ •์ˆ˜๋ฅผ ๊ตฌํ•œ๋‹ค.
  • ๋งŒ์•ฝ ํ•œ ๋ฒˆ๋„ ๋“ฑ์žฅํ•˜์ง€ ์•Š์€ ์ˆ˜๋ผ๋ฉด ๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€ํ•œ๋‹ค.
 

๊ฒฐ๋ก !

ํ•ด๋‹น ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ์–ด๋–ป๊ฒŒ ๋ฌธ์ž์—ด์„ ๋ถ„ํ• ํ•ด์„œ ๊ธธ์ด ์ˆœ์œผ๋กœ ์ •๋ ฌํ•  ์ˆ˜ ์žˆ์„์ง€์— ๋Œ€ํ•ด ๋งŽ์ด ๊ณ ๋ฏผํ–ˆ๋Š”๋ฐ, ์ด๋ฅผ substring()๊ณผ split(), Arrays.sort(), Comparator.comparingInt(String::length) ๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.
 
Share article

More articles

See more posts

[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 3์žฅ ์ •๋ฆฌ

DriedPollack's avatar
March 18, 2024
[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 3์žฅ ์ •๋ฆฌ

[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 2์žฅ ์ •๋ฆฌ

DriedPollack's avatar
March 13, 2024
[์ฝ”๋“œ๋กœ ๋ฐฐ์šฐ๋Š” ์Šคํ”„๋ง ์›น ํ”„๋กœ์ ํŠธ ๊ฐœ์ •ํŒ] 2์žฅ ์ •๋ฆฌ

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