[Programmers] ๋ฉ€์ฉกํ•œ ์‚ฌ๊ฐํ˜•

2022. 6. 11. 16:25ยท๐Ÿ’ฏ CodingTest/Programmers

โ–ถ ๋ฌธ์ œ : https://programmers.co.kr/learn/courses/30/lessons/62048

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋ฉ€์ฉกํ•œ ์‚ฌ๊ฐํ˜•

๊ฐ€๋กœ ๊ธธ์ด๊ฐ€ Wcm, ์„ธ๋กœ ๊ธธ์ด๊ฐ€ Hcm์ธ ์ง์‚ฌ๊ฐํ˜• ์ข…์ด๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ข…์ด์—๋Š” ๊ฐ€๋กœ, ์„ธ๋กœ ๋ฐฉํ–ฅ๊ณผ ํ‰ํ–‰ํ•˜๊ฒŒ ๊ฒฉ์ž ํ˜•ํƒœ๋กœ ์„ ์ด ๊ทธ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๋ชจ๋“  ๊ฒฉ์ž์นธ์€ 1cm x 1cm ํฌ๊ธฐ์ž…๋‹ˆ๋‹ค. ์ด ์ข…์ด๋ฅผ ๊ฒฉ์ž ์„ ์„

programmers.co.kr

 

โ–ถ ์ฝ”๋“œ : 

function solution(w, h) {
    const total = w * h;
    const g = gcd(w, h); // g ์ฆ‰, ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋Š” ๋Œ€๊ฐ์„ ์œผ๋กœ ๋‚˜๋ˆ„์—ˆ์„๋•Œ ๋ฐ˜๋ณต๋˜๋Š” ์‚ฌ๊ฐํ˜•ํ˜•ํƒœ๊ฐ€ ๋“ฑ์žฅํ•˜๋Š” ํšŸ์ˆ˜์ด๋‹ค.
    const miniSquare = w/g + h/g - 1; // ๊ฐ๊ฐ์˜ ์ž‘์€ ์‚ฌ๊ฐํ˜•์€ ๊ฐ€๋กœ๋ฅผ g๋กœ ๋‚˜๋ˆˆ๊ฐ’๊ณผ ์„ธ๋กœ๋ฅผ g๋กœ ๋‚˜๋ˆˆ๊ฐ’์—์„œ 1(์ค‘๋ณตํ•ด์„œ ์ž๋ฅด๋Š” ์‚ฌ๊ฐํ˜•)์„ ๋บ€ ๊ฐ’๋งŒํผ ์‚ฌ๊ฐํ˜•์„ ์ง€์šด๋‹ค.
    
    return total - (g * miniSquare);
}

function gcd(a,b){
    if(b === 0){
        return a;
    }else{
        return gcd(b, a % b);
    }   
}

 

 

โ–ถ ๋ฌธ์ œ ํ’€์ด : 

- ํ•ด๋‹น ๋ฌธ์ œ๋Š” '๋ฉ€์ฉกํ•œ ์‚ฌ๊ฐํ˜• ํ’€์ด' ๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ํ’€์ดํ•˜์˜€๋‹ค.

1. ์ „์ฒด ์‚ฌ๊ฐํ˜•์—์„œ ์ž˜๋ฆฌ๋Š” ์‚ฌ๊ฐํ˜•์˜ ์ˆ˜๋ฅผ ์„ธ์–ด์•ผ ํ•œ๋‹ค. (์ด๋•Œ, ์ „์ฒด์‚ฌ๊ฐํ˜•์€ ์ง์‚ฌ๊ฐํ˜•์ด๋ผ๋Š” ์ „์ œ์กฐ๊ฑด์ด ๋ฌธ์ œ์— ์žˆ๋‹ค.)

2. ์ „์ฒด ์‚ฌ๊ฐํ˜•์—์„œ ์ž˜๋ฆฌ๋Š” ์‚ฌ๊ฐํ˜•(์ž˜๋ฆฌ๋Š” ์˜์—ญ)์€ ๋ฐ˜๋ณต๋˜๋Š” ํ˜•ํƒœ๋ฅผ ๊ฐ€์ง€๋Š”๋ฐ, ์ด๋•Œ ๋ฐ˜๋ณต๋˜๋Š” ํšŸ์ˆ˜๋Š” GCD(์ตœ๋Œ€๊ณต์•ฝ์ˆ˜) ๋ฒˆ ๋“ฑ์žฅํ•œ๋‹ค. 

3. ์ถ”๊ฐ€์ ์œผ๋กœ ์ž˜๋ฆฌ๋Š” ์˜์—ญ์˜ ์ž‘์€ ์‚ฌ๊ฐํ˜•์ด ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ ๋ฒˆ ๋“ฑ์žฅํ•œ๋‹ค๋ฉด ํ•˜๋‚˜์˜ ์ž‘์€ ์˜์—ญ ์‚ฌ๊ฐํ˜• ๋‚ด๋ถ€์—์„œ ์ž˜๋ฆฌ๋Š” ์‚ฌ๊ฐํ˜•์˜ ๊ฐœ์ˆ˜๋Š” ์–ด๋–ป๊ฒŒ ๊ตฌํ• ๊นŒ? 

  - ์ž‘์€ ์‚ฌ๊ฐํ˜•์˜ ํฌ๊ธฐ๋Š” (w // g) * (h // g) ์ด๋‹ค. ์ด๋•Œ ๊ฐ๊ฐ์˜ ์‚ฌ๊ฐํ˜•์— ๋Œ€ํ•ด ๋Œ€๊ฐ์„ ์„ ๊ทธ์—ˆ์„๋•Œ (์ž‘์€ ์‚ฌ๊ฐํ˜•์˜ ๊ฐ€๋กœ) ๊ฐœ, (์ž‘์€ ์‚ฌ๊ฐํ˜•์˜ ์„ธ๋กœ) ๊ฐœ ์”ฉ ๋‚˜๋ˆˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋•Œ ๊ฐ€๋กœ์™€ ์„ธ๋กœ์— ๋Œ€ํ•ด ์ค‘๋ณต์œผ๋กœ ์นด์šดํŒ…ํ•˜๋Š” ์นธ(์ฒ˜์Œ ์‹œ์ž‘์นธ) ์— ๋Œ€ํ•œ 1์„ ๋นผ์ฃผ์–ด์•ผํ•œ๋‹ค. 

4. ์ง€๊ธˆ ๊นŒ์ง€์˜ ๋ง์„ ์ •๋ฆฌํ•ด๋ณด๋ฉด ์ „์ฒด ์‚ฌ๊ฐํ˜•์˜ ํฌ๊ธฐ (w * h) ์—์„œ gcd(์ž‘์€ ์‚ฌ๊ฐํ˜•์˜ ๋“ฑ์žฅ ํšŸ์ˆ˜) * miniSquare(์ž‘์€ ์‚ฌ๊ฐํ˜•์—์„œ ๋Œ€๊ฐ์„ ์— ์˜ํ•ด ์ œ์™ธ๋˜๋Š” ์‚ฌ๊ฐํ˜•์˜ ์ˆ˜)๋ฅผ ๋นผ์ฃผ์–ด์•ผ ํ•˜๊ณ  miniSquare์˜ ์ˆ˜๋Š” "(w / g) + (h /g) - 1" ์ด ๋œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. 

5. ๋”ฐ๋ผ์„œ ์ „์ฒด ์‹์€ `(w * h) - gcd * (w/g + h/g - 1)` ์ด ๋˜์–ด์•ผ ํ•œ๋‹ค๋Š” ์˜๋ฏธ์ด๋‹ค. 

6. gcd() ํ•จ์ˆ˜๋Š” '์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ' ๋ฅผ ์ฐธ๊ณ ํ•ด ๊ตฌํ˜„ํ•˜์˜€์œผ๋ฉฐ ๊ฐ๊ฐ์„ ์กฐํ•ฉํ•˜์—ฌ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•ด์ฃผ๋ฉด ๋˜๋Š” ๋ฌธ์ œ์˜€๋‹ค.

'๐Ÿ’ฏ CodingTest > Programmers' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Programmers] 124 ๋‚˜๋ผ์˜ ์ˆซ์ž  (0) 2022.06.11
[Programmers] (Javascript) ์ˆœ์œ„ ๊ฒ€์ƒ‰  (2) 2022.05.02
[Programmers] (Javascript) ๋ฉ”๋‰ด ๋ฆฌ๋‰ด์–ผ  (0) 2022.04.28
[Programmers] (Javascript) ์ถ”์„ ํŠธ๋ž˜ํ”ฝ  (0) 2022.04.26
[Programmers] (Javascript) ํŠœํ”Œ  (0) 2022.04.25
'๐Ÿ’ฏ CodingTest/Programmers' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [Programmers] 124 ๋‚˜๋ผ์˜ ์ˆซ์ž
  • [Programmers] (Javascript) ์ˆœ์œ„ ๊ฒ€์ƒ‰
  • [Programmers] (Javascript) ๋ฉ”๋‰ด ๋ฆฌ๋‰ด์–ผ
  • [Programmers] (Javascript) ์ถ”์„ ํŠธ๋ž˜ํ”ฝ
S.Honey
S.Honey
  • S.Honey
    Algo ์“ฐ์ž
    S.Honey
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (123)
      • ํšŒ๊ณ  (0)
        • ์ทจ์—… ํ›„ ํšŒ๊ณ  (0)
      • ๐Ÿƒ Frontend Road-Map (2)
        • ๐Ÿšฉ Summary (1)
        • ๐Ÿ“š Road-Map Contents (1)
        • ๐ŸŸง HTML (0)
        • ๐ŸŸฆ CSS (0)
        • ๐ŸŸจ Javascript (0)
        • โฌœ React (0)
        • ๐ŸŸช Redux (0)
      • Backend (0)
        • QueryDSL (0)
      • ๐Ÿ’ป Programming Language (54)
        • C# (51)
        • Flutter-Dart (3)
        • Java (0)
      • ๐Ÿ“š Computer Science (4)
        • Algorithms (4)
        • Database (0)
        • Network (0)
        • Operating System(OS) (0)
      • ๐Ÿ’ฏ CodingTest (60)
        • BaekJoon (22)
        • Programmers (34)
        • CodeTree (4)
      • โœ’๏ธ Design Pattern (1)
      • ๐Ÿฑ Etc (2)
        • Jenkins Plugin ์ œ์ž‘๊ธฐ (1)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ๋งํฌ

    • ๊ณต์ง€์‚ฌํ•ญ

      • ๐Ÿ“– ๊ณต๋ถ€ ์ฐธ๊ณ  ๊ต์žฌ ๋ฐ ์ž๋ฃŒ
    • ์ธ๊ธฐ ๊ธ€

    • ํƒœ๊ทธ

      Java
      ์‹œ๋ฎฌ๋ ˆ์ด์…˜
      JavaScript
      ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
      ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ
      ์ฝ”๋“œํŠธ๋ฆฌ
      ๋ฐฑ์ค€
      ๊ตฌํ˜„
      programmers
      ๋ฌธ์ž์—ด ํŒŒ์‹ฑ
      ์‚ผ์„ฑsw์—ญํ…Œ
      sort
      ์•Œ๊ณ ๋ฆฌ์ฆ˜
      BFS
      ํŒŒ์ด์ฌ
      ์ด์ง„ํƒ์ƒ‰
      ์ž๋ฃŒ๊ตฌ์กฐ
      ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰
      ์นด์นด์˜ค
      ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      ์“ฐ์…จ์ž–์•„
      JS
      BAEKJOON
      ์Šคํ„ฐ๋””
      Algorithm
      Flutter
      ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
      c#
      DART
      DP
    • ์ตœ๊ทผ ๋Œ“๊ธ€

    • ์ตœ๊ทผ ๊ธ€

    • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.1
    S.Honey
    [Programmers] ๋ฉ€์ฉกํ•œ ์‚ฌ๊ฐํ˜•
    ์ƒ๋‹จ์œผ๋กœ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

    ๋‹จ์ถ•ํ‚ค

    ๋‚ด ๋ธ”๋กœ๊ทธ

    ๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
    Q
    Q
    ์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
    W
    W

    ๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

    ๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
    E
    E
    ๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
    C
    C

    ๋ชจ๋“  ์˜์—ญ

    ์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
    S
    S
    ๋งจ ์œ„๋กœ ์ด๋™
    T
    T
    ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
    H
    H
    ๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
    Shift + /
    โ‡ง + /

    * ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.