[programmers] ๋ฐฉ๋ฌธ ๊ธธ์ด - Java

๊ฒŒ์ž„ ์บ๋ฆญํ„ฐ๊ฐ€ ์ฃผ์–ด์ง„ ๋ช…๋ น์–ด์— ๋”ฐ๋ผ ์ด๋™ํ•˜๋ฉฐ ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ธธ์˜ ๊ธธ์ด๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์บ๋ฆญํ„ฐ๋Š” ์ขŒํ‘œํ‰๋ฉด์˜ ๊ฒฝ๊ณ„ ๋‚ด์—์„œ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ด๋™ ๊ฒฝ๋กœ๋Š” Set์„ ์‚ฌ์šฉํ•˜์—ฌ ์ €์žฅํ•˜์—ฌ ์ค‘๋ณต ๊ณ„์‚ฐ์„ ๋ฐฉ์ง€ํ•ฉ๋‹ˆ๋‹ค. ์ตœ์ข…์ ์œผ๋กœ, ์ฒ˜์Œ ๋ฐฉ๋ฌธํ•œ ๊ฒฝ๋กœ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค.
DriedPollack's avatar
Sep 02, 2024
[programmers] ๋ฐฉ๋ฌธ ๊ธธ์ด - Java

๋ฐฉ๋ฌธ ๊ธธ์ด

๋ฌธ์ œ ์„ค๋ช…

๊ฒŒ์ž„ ์บ๋ฆญํ„ฐ๋ฅผ 4๊ฐ€์ง€ ๋ช…๋ น์–ด๋ฅผ ํ†ตํ•ด ์›€์ง์ด๋ ค ํ•ฉ๋‹ˆ๋‹ค. ๋ช…๋ น์–ด๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • U: ์œ„์ชฝ์œผ๋กœ ํ•œ ์นธ ๊ฐ€๊ธฐ
  • D: ์•„๋ž˜์ชฝ์œผ๋กœ ํ•œ ์นธ ๊ฐ€๊ธฐ
  • R: ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ•œ ์นธ ๊ฐ€๊ธฐ
  • L: ์™ผ์ชฝ์œผ๋กœ ํ•œ ์นธ ๊ฐ€๊ธฐ
์บ๋ฆญํ„ฐ๋Š” ์ขŒํ‘œํ‰๋ฉด์˜ (0, 0) ์œ„์น˜์—์„œ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. ์ขŒํ‘œํ‰๋ฉด์˜ ๊ฒฝ๊ณ„๋Š” ์™ผ์ชฝ ์œ„(-5, 5), ์™ผ์ชฝ ์•„๋ž˜(-5, -5), ์˜ค๋ฅธ์ชฝ ์œ„(5, 5), ์˜ค๋ฅธ์ชฝ ์•„๋ž˜(5, -5)๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
notion image
์˜ˆ๋ฅผ ๋“ค์–ด, "ULURRDLLU"๋กœ ๋ช…๋ นํ–ˆ๋‹ค๋ฉด
notion image
  • 1๋ฒˆ ๋ช…๋ น์–ด๋ถ€ํ„ฐ 7๋ฒˆ ๋ช…๋ น์–ด๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์›€์ง์ž…๋‹ˆ๋‹ค.
notion image
  • 8๋ฒˆ ๋ช…๋ น์–ด๋ถ€ํ„ฐ 9๋ฒˆ ๋ช…๋ น์–ด๊นŒ์ง€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์›€์ง์ž…๋‹ˆ๋‹ค.
notion image
์ด๋•Œ, ์šฐ๋ฆฌ๋Š” ๊ฒŒ์ž„ ์บ๋ฆญํ„ฐ๊ฐ€ ์ง€๋‚˜๊ฐ„ ๊ธธ ์ค‘ ์บ๋ฆญํ„ฐ๊ฐ€ ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ธธ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์œ„์˜ ์˜ˆ์‹œ์—์„œ ๊ฒŒ์ž„ ์บ๋ฆญํ„ฐ๊ฐ€ ์›€์ง์ธ ๊ธธ์ด๋Š” 9์ด์ง€๋งŒ, ์บ๋ฆญํ„ฐ๊ฐ€ ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ธธ์˜ ๊ธธ์ด๋Š” 7์ด ๋ฉ๋‹ˆ๋‹ค. (8, 9๋ฒˆ ๋ช…๋ น์–ด์—์„œ ์›€์ง์ธ ๊ธธ์€ 2, 3๋ฒˆ ๋ช…๋ น์–ด์—์„œ ์ด๋ฏธ ๊ฑฐ์ณ ๊ฐ„ ๊ธธ์ž…๋‹ˆ๋‹ค)
๋‹จ, ์ขŒํ‘œํ‰๋ฉด์˜ ๊ฒฝ๊ณ„๋ฅผ ๋„˜์–ด๊ฐ€๋Š” ๋ช…๋ น์–ด๋Š” ๋ฌด์‹œํ•ฉ๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, "LULLLLLLU"๋กœ ๋ช…๋ นํ–ˆ๋‹ค๋ฉด
notion image
  • 1๋ฒˆ ๋ช…๋ น์–ด๋ถ€ํ„ฐ 6๋ฒˆ ๋ช…๋ น์–ด๋Œ€๋กœ ์›€์ง์ธ ํ›„, 7, 8๋ฒˆ ๋ช…๋ น์–ด๋Š” ๋ฌด์‹œํ•ฉ๋‹ˆ๋‹ค. ๋‹ค์‹œ 9๋ฒˆ ๋ช…๋ น์–ด๋Œ€๋กœ ์›€์ง์ž…๋‹ˆ๋‹ค.
notion image
์ด๋•Œ ์บ๋ฆญํ„ฐ๊ฐ€ ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ธธ์˜ ๊ธธ์ด๋Š” 7์ด ๋ฉ๋‹ˆ๋‹ค.
๋ช…๋ น์–ด๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜ dirs๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๊ฒŒ์ž„ ์บ๋ฆญํ„ฐ๊ฐ€ ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ธธ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•˜์—ฌ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด ์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • dirs๋Š” stringํ˜•์œผ๋กœ ์ฃผ์–ด์ง€๋ฉฐ, 'U', 'D', 'R', 'L' ์ด์™ธ์— ๋ฌธ์ž๋Š” ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • dirs์˜ ๊ธธ์ด๋Š” 500 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

dirs
answer
"ULURRDLLU"
7
"LULLLLLLU"
7

solution.java

import java.util.HashSet; import java.util.Set; class Solution { public int solution(String dirs) { // ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•˜๋Š” set Set<String> visitedPaths = new HashSet<>(); // ์‹œ์ž‘ ์œ„์น˜ int x = 0, y = 0; // ๊ฐ๊ฐ์˜ ์ด๋™์— ๋Œ€ํ•œ ๋ฐฉํ–ฅ ๋งคํ•‘ for (char dir : dirs.toCharArray()) { int nx = x, ny = y; switch (dir) { case 'U': ny = y + 1; break; case 'D': ny = y - 1; break; case 'L': nx = x - 1; break; case 'R': nx = x + 1; break; } // ์ด๋™ํ•œ ์œ„์น˜๊ฐ€ ๊ฒฝ๊ณ„ ๋‚ด์— ์žˆ๋Š”์ง€ ํ™•์ธ if (nx < -5 || nx > 5 || ny < -5 || ny > 5) { continue; // ๊ฒฝ๊ณ„๋ฅผ ๋ฒ—์–ด๋‚˜๋Š” ๊ฐ’์ด๋ผ๋ฉด ๋ฌด์‹œ } // ์–‘์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฒฝ๋กœ ์‹๋ณ„์ž ๋งŒ๋“ค๊ธฐ String path1 = x + "," + y + "->" + nx + "," + ny; String path2 = nx + "," + ny + "->" + x + "," + y; // ์ƒˆ ๊ฒฝ๋กœ์ธ ๊ฒฝ์šฐ ๊ฒฝ๋กœ ์ถ”๊ฐ€ if (!visitedPaths.contains(path1) && !visitedPaths.contains(path2)) { visitedPaths.add(path1); visitedPaths.add(path2); } // ์ƒˆ ์œ„์น˜๋กœ ์ด๋™ x = nx; y = ny; } // ์ฒ˜์Œ ๊ฑธ์–ด๋ณธ ๊ฒฝ๋กœ์˜ ์ˆ˜ return visitedPaths.size() / 2; } }
 

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

  • ์บ๋ฆญํ„ฐ์˜ ์œ„์น˜๋Š” (-5, -5)์—์„œ (5, 5) ๊ฒฝ๊ณ„ ๋‚ด์— ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์ด ๊ฒฝ๊ณ„๋ฅผ ๋„˜์–ด์„œ๋Š” ๋ชจ๋“  ์›€์ง์ž„์€ ๋ฌด์‹œ๋˜์–ด์•ผ ํ•œ๋‹ค.
  • ๋‘ ์ขŒํ‘œ ์‚ฌ์ด์˜ ๊ฒฝ๋กœ๋ฅผ ์ถ”์ ํ•ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด (x1, y1)์—์„œ (x2, y2)๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด ์ฒ˜์Œ์ด๋ผ๋ฉด ์ƒˆ ๊ฒฝ๋กœ๋กœ ๊ฐ„์ฃผ๋˜์–ด์•ผ ํ•œ๋‹ค.
  • ๋™์ผํ•œ ๊ฒฝ๋กœ๋ฅผ ๋‘ ๋ฒˆ ๊ณ„์‚ฐํ•ด์„œ๋Š” ์•ˆ ๋˜๋ฏ€๋กœ ์ฒ˜์Œ ๋ฐฉ๋ฌธํ•œ ๊ฒฝ๋กœ ์ง‘ํ•ฉ์„ ์ €์žฅํ•ด์•ผ ํ•œ๋‹ค.
    • Set์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฐ ์ด๋™์˜ ์‹œ์ž‘๊ณผ ๋์„ ๋‚˜ํƒ€๋‚ด๋Š” ์  ์Œ์œผ๋กœ ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•œ๋‹ค. ์ฒ˜์Œ ๋ฐฉ๋ฌธํ•œ ๊ฒฝ๋กœ๋ฅผ ์ถ”์ ํ•˜๊ธฐ ์œ„ํ•ด ๊ฐ ๊ฒฝ๋กœ๋ฅผ x1,y1->x2,y2์™€ ๊ฐ™์€ ๋ฌธ์ž์—ด๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค.
 

๊ฒฐ๋ก !

ํ•ด๋‹น ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ Set์„ ํ™œ์šฉํ•ด์„œ ์ง€๋‚˜๊ฐ„ ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์€ ์•Œ์•˜์ง€๋งŒ, ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ €์žฅ์„ ํ• ์ง€์— ๋Œ€ํ•ด์„  ๊ณ ๋ฏผ์ด ํ•„์š”ํ–ˆ๋‹ค. ๊ทธ ๊ฒฐ๊ณผ, String์œผ๋กœ ํ˜„์žฌ ์œ„์น˜์™€ ๋ชฉ์ ์ง€๋ฅผ ๋งŒ๋“ค์–ด์„œ ์ €์žฅ์„ ํ•˜๋ฉด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ์•˜๋‹ค.
 
Share article

More articles

See more posts

[Do it! ๊นก์ƒ˜์˜ ์•ˆ๋“œ๋กœ์ด๋“œ ์•ฑ ํ”„๋กœ๊ทธ๋ž˜๋ฐ with ์ฝ”ํ‹€๋ฆฐ] ๋ธŒ๋กœ๋“œ์บ์ŠคํŠธ ๋ฆฌ์‹œ๋ฒ„ ์ปดํฌ๋„ŒํŠธ

DriedPollack's avatar
August 19, 2024
[Do it! ๊นก์ƒ˜์˜ ์•ˆ๋“œ๋กœ์ด๋“œ ์•ฑ ํ”„๋กœ๊ทธ๋ž˜๋ฐ with ์ฝ”ํ‹€๋ฆฐ] ๋ธŒ๋กœ๋“œ์บ์ŠคํŠธ ๋ฆฌ์‹œ๋ฒ„ ์ปดํฌ๋„ŒํŠธ

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