[ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] ๊ทค ๊ณ ๋ฅด๊ธฐ

๐Ÿง‘๐Ÿปโ€๐Ÿ’ป Coding Test/โŒจ๏ธ Programmers โ”ƒ 2024. 4. 12. 09:59
๋ชฉ์ฐจ
  1. ๋ฌธ์ œ ์„ค๋ช…
  2. ๋ฌธ์ œ ํ’€์ด
  3. ๋‚˜์˜ ํ’€์ด
  4. ๋‹ค๋ฅธ ์‚ฌ๋žŒ ํ’€์ด
  5. ์ค‘์š”ํ•œ ๊ฐœ๋…

 

 

๐Ÿ„ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ’€์ด

โœ๐Ÿป ๋ฌธ์ œ ํ’€์ด github ๋งํฌ

 

 

๋ฌธ์ œ ์„ค๋ช…

๊ฒฝํ™”๋Š” ๊ณผ์ˆ˜์›์—์„œ ๊ทค์„ ์ˆ˜ํ™•ํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ฒฝํ™”๋Š” ์ˆ˜ํ™•ํ•œ ๊ทค ์ค‘ 'k'๊ฐœ๋ฅผ ๊ณจ๋ผ ์ƒ์ž ํ•˜๋‚˜์— ๋‹ด์•„ ํŒ๋งคํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์ˆ˜ํ™•ํ•œ ๊ทค์˜ ํฌ๊ธฐ๊ฐ€ ์ผ์ •ํ•˜์ง€ ์•Š์•„ ๋ณด๊ธฐ์— ์ข‹์ง€ ์•Š๋‹ค๊ณ  ์ƒ๊ฐํ•œ ๊ฒฝํ™”๋Š” ๊ทค์„ ํฌ๊ธฐ๋ณ„๋กœ ๋ถ„๋ฅ˜ํ–ˆ์„ ๋•Œ ์„œ๋กœ ๋‹ค๋ฅธ ์ข…๋ฅ˜์˜ ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๊ฒฝํ™”๊ฐ€ ์ˆ˜ํ™•ํ•œ ๊ทค 8๊ฐœ์˜ ํฌ๊ธฐ๊ฐ€ [1, 3, 2, 5, 4, 5, 2, 3] ์ด๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค. ๊ฒฝํ™”๊ฐ€ ๊ทค 6๊ฐœ๋ฅผ ํŒ๋งคํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด, ํฌ๊ธฐ๊ฐ€ 1, 4์ธ ๊ทค์„ ์ œ์™ธํ•œ ์—ฌ์„ฏ ๊ฐœ์˜ ๊ทค์„ ์ƒ์ž์— ๋‹ด์œผ๋ฉด, ๊ทค์˜ ํฌ๊ธฐ์˜ ์ข…๋ฅ˜๊ฐ€ 2, 3, 5๋กœ ์ด 3๊ฐ€์ง€๊ฐ€ ๋˜๋ฉฐ ์ด๋•Œ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅธ ์ข…๋ฅ˜๊ฐ€ ์ตœ์†Œ์ผ ๋•Œ์ž…๋‹ˆ๋‹ค.

๊ฒฝํ™”๊ฐ€ ํ•œ ์ƒ์ž์— ๋‹ด์œผ๋ ค๋Š” ๊ทค์˜ ๊ฐœ์ˆ˜ k์™€ ๊ทค์˜ ํฌ๊ธฐ๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด tangerine์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฒฝํ™”๊ฐ€ ๊ทค k๊ฐœ๋ฅผ ๊ณ ๋ฅผ ๋•Œ ํฌ๊ธฐ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅธ ์ข…๋ฅ˜์˜ ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

 

 

์ œํ•œ์‚ฌํ•ญ

  • 1 โ‰ค k โ‰ค tangerine์˜ ๊ธธ์ด โ‰ค 100,000
  • 1 โ‰ค tangerine์˜ ์›์†Œ โ‰ค 10,000,000

 

 

์ž…์ถœ๋ ฅ ์˜ˆ

k tangerine result
6 [1, 3, 2, 5, 4, 5, 2, 3] 3
4 [1, 3, 2, 5, 4, 5, 2, 3] 2
2 [1, 1, 1, 1, 2, 2, 2, 3] 1

 

 

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

 

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

  • ๋ณธ๋ฌธ์—์„œ ์„ค๋ช…ํ•œ ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค.

 

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

  • ๊ฒฝํ™”๋Š” ํฌ๊ธฐ๊ฐ€ 2์ธ ๊ทค 2๊ฐœ์™€ 3์ธ ๊ทค 2๊ฐœ ๋˜๋Š” 2์ธ ๊ทค 2๊ฐœ์™€ 5์ธ ๊ทค 2๊ฐœ ๋˜๋Š” 3์ธ ๊ทค 2๊ฐœ์™€ 5์ธ ๊ทค 2๊ฐœ๋กœ ๊ทค์„ ํŒ๋งคํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ์˜ ํฌ๊ธฐ ์ข…๋ฅ˜๋Š” 2๊ฐ€์ง€๋กœ ์ด ๊ฐ’์ด ์ตœ์†Œ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

 

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

  • ๊ฒฝํ™”๋Š” ํฌ๊ธฐ๊ฐ€ 1์ธ ๊ทค 2๊ฐœ๋ฅผ ํŒ๋งคํ•˜๊ฑฐ๋‚˜ 2์ธ ๊ทค 2๊ฐœ๋ฅผ ํŒ๋งคํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ์˜ ํฌ๊ธฐ ์ข…๋ฅ˜๋Š” 1๊ฐ€์ง€๋กœ, ์ด ๊ฐ’์ด ์ตœ์†Œ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

 

 

 

 

๋ฌธ์ œ ํ’€์ด

๋‚˜์˜ ํ’€์ด


      
import Foundation
func solution(_ k:Int, _ tangerine:[Int]) -> Int {
var dic = [Int:Int]()
var k = k, count = 0
for i in tangerine {
dic[i] = ( dic[i] ?? 0 ) + 1
}
for i in dic.values.sorted(by: >){
k -= i
count += 1
if k <= 0 {
return count
}
}
return 0
}

tangerine ๊ธธ์ด์˜ ์ตœ๋Œ“๊ฐ’์ด 100,000 ์ด์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ˜๋ณต๋ฌธ์„ ํ•œ ๋ฒˆ๋งŒ ๋Œ์•„์„œ ํ’€ ์ˆ˜ ์žˆ๋„๋ก ํ•ด์•ผํ–ˆ๋‹ค. ๊ฒฐ๊ตญ ํ•œ ๋ฒˆ์€ ๊ฐ ์ˆซ์ž๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์•„์„œ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ฆฌ๋ฅผ ํ•ด์•ผํ•˜๋Š”๋ฐ, ์ด๋•Œ, ๋น„๊ต๊ฐ€ ์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์งง์„ ๋”•์…”๋„ˆ๋ฆฌ๋กœ ํƒํ–ˆ๋‹ค. ํ•œ๋ฒˆ์˜ for๋ฌธ์„ ๋Œ๋ฉฐ ๋”•์…”๋„ˆ๋ฆฌ์— ํ•ด๋‹น ํฌ๊ธฐ๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ์–ป๊ณ , ํ•ด๋‹น ํฌ๊ธฐ๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ํ•˜์—ฌ ๊ทธ ๊ฐ’๋“ค์„ k์—์„œ ํ•˜๋‚˜์”ฉ ๋นผ์„œ k๊ฐ€ 0๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์„ ๊ฒฝ์šฐ์— for๋ฌธ์„ ๋น ์ ธ๋‚˜์˜ด๊ณผ ๋™์‹œ์— ๋‹ต์„ ์ถœ๋ ฅํ•˜๋„๋ก ํ•˜์˜€๋‹ค.

 

 

๋‹ค๋ฅธ ์‚ฌ๋žŒ ํ’€์ด


      
func solution(_ k: Int, _ tangerine: [Int]) -> Int {
return Dictionary(grouping: tangerine) { $0 }.values
.sorted { $0.count > $1.count }
.reduce((0, 0)) { acc, array in acc.1 >= k ? acc : (acc.0 + 1, acc.1 + array.count) }
.0
}

 

 

๋‚˜๋„ ์ฒ˜์Œ์—” reduce๋กœ ํ’€๋ ค๊ณ  ํ–ˆ๋Š”๋ฐ, ์ค‘๊ฐ„์— if๋ฌธ์„ ๋น ์ ธ๋‚˜์˜ฌ ์ˆ˜ ์—†์–ด์„œ ์“ฐ์ง€ ๋ชปํ–ˆ๋‹ค.

ํ•˜์ง€๋งŒ, ํด๋กœ์ € ์•ˆ์— return์„ ์ฃผ๋Š” ๊ฒƒ์ด ์•„๋‹Œ return ๊ฐ’ ๋’ค์— reduce๋ผ๋Š” ๋ฌธ์žฅ์„ ํ•œ๋ฒˆ์— ์จ์„œ ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ํ•˜๋‚˜์”ฉ ๊ฐ’์„ ๋”ํ•  ๋•Œ ์ด ๊ฐ’์ด k๋ณด๋‹ค ํฌ๋‹ค๋ฉด ์•„๋ฌด๊ฒƒ๋„ ๋”ํ•˜์ง€ ์•Š๊ณ , k๋ณด๋‹ค ์ž‘๋‹ค๋ฉด ๊ฐฏ์ˆ˜๋ฅผ ํ•˜๋‚˜ ์˜ฌ๋ฆฌ๊ณ , ๊ฐ’์„ ๊ณ„์† ๋”ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

 

๊ทธ๋ ‡๋‹ค๋ฉด ๊ถ๊ธˆํ•œ ๊ฑด acc.1์ด k๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์„ ๊ฒฝ์šฐ์—” ๋’ค์˜ acc ๋”์ด์ƒ์˜ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ์ง€ ์•Š๊ณ  ๊ทธ๋Œ€๋กœ ๋น ์ ธ๋‚˜์˜ค๋Š” ๊ฒƒ์ธ๊ฐ€ ์•„๋‹˜ ๋ฐ˜๋ณต๋ฌธ์„ ๊ณ„์† ๋Œ์ง€๋งŒ, ๊ณ„์‚ฐ์„ ์•ˆํ•˜๋Š” ๊ฒƒ์ธ๊ฐ€? 

reduce๋Š” ์ค‘๊ฐ„์— ๋ฐฐ์—ด ๊ฐ’์„ ๋น ์ ธ๋‚˜์˜ค์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— 100,000๊ฐœ์˜ ๋ฐฐ์—ด์—์„œ 2๋ฒˆ์งธ ์›์†Œ์—์„œ ํ•ด๋‹น ์กฐ๊ฑด์„ ๋งŒ์กฑํ–ˆ๋‹ค๊ณ  ํ•˜๋”๋ผ๋„ ์•„๋ฌด ์—ฐ์‚ฐ์ด ์ผ์–ด๋‚˜์ง€ ์•Š์ง€๋งŒ ๋‚˜๋จธ์ง€ 99,998๊ฐœ์˜ ๋ฐฐ์—ด์„ ๋‹ค ๋ˆ๋‹ค๊ณ  ํ•˜์˜€๋‹ค. ๊ทธ๋Ÿผ ๋” ๋น„ํšจ์œจ์ ์ธ๊ฒŒ ์•„๋‹Œ๊ฐ€!!!!

 

 

์ค‘์š”ํ•œ ๊ฐœ๋…

Dictionary(grouping: ๊ทธ๋ฃนํ™”ํ•  ๋ฐฐ์—ด, by: ๊ทธ๋ฃนํ™”ํ•  ๊ธฐ์ค€)


      
let students = ["Kofi", "Abena", "Efua", "Kweku", "Akosua"]
let studentsByLetter = Dictionary(grouping: students, by: { $0.first! })
// ["E": ["Efua"], "K": ["Kofi", "Kweku"], "A": ["Abena", "Akosua"]]

 

Dictionary์—์„œ ํ•ด๋‹น ๊ฐ’์„ ๊ทธ๋ฃนํ™”ํ•˜๋ฉด ๊ทธ๋ฃนํ™”๋œ ๊ฐ’๋“ค์ด ๋ฐฐ์—ด๋กœ ๋”•์…”๋„ˆ๋ฆฌ์— ์ €์žฅ์ด ๋œ๋‹ค!

์•ž์œผ๋กœ ์ž์ฃผ ์“ธ ๋“ฏ!ใ…Ž

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)
  1. ๋ฌธ์ œ ์„ค๋ช…
  2. ๋ฌธ์ œ ํ’€์ด
  3. ๋‚˜์˜ ํ’€์ด
  4. ๋‹ค๋ฅธ ์‚ฌ๋žŒ ํ’€์ด
  5. ์ค‘์š”ํ•œ ๊ฐœ๋…
'๐Ÿง‘๐Ÿปโ€๐Ÿ’ป Coding Test/โŒจ๏ธ Programmers' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] ์—ฐ์† ๋ถ€๋ถ„ ์ˆ˜์—ด ํ•ฉ์˜ ๊ฐœ์ˆ˜
  • [ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] ๊ด„ํ˜ธ ํšŒ์ „ํ•˜๊ธฐ
  • [ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] ๋ฉ€๋ฆฌ ๋›ฐ๊ธฐ / ๋™์  ๊ณ„ํš๋ฒ• ( Dynamic Programming )
  • [ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] N๊ฐœ์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜
EarthSea
EarthSea
์ฃผ๋‹ˆ์–ด ๊ฐœ๋ฐœ์ž ์งธ์ž…๋‹ˆ๋‹ค ๐ŸŒฑ

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ๊ธ€์“ฐ๊ธฐ
EarthSea
EarthSea's Log๐ŸŒ
EarthSea

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

  • EarthSea's Introduce
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • โœ๏ธ TIL
    • ๐Ÿ“‘ Project
    • ๐Ÿ“’ Study
      • ๐ŸŒ React
      • ๐Ÿšฉ Swift
      • ๐Ÿ“ UIKit
      • ๐Ÿ–ค Git
      • ๐Ÿฉต Python
    • ๐Ÿง‘๐Ÿปโ€๐Ÿ’ป Coding Test
      • โŒจ๏ธ Programmers
      • ๐Ÿ–Œ๏ธ BAEKJOON
    • ๐ŸŽ† SSAFY
    • ๐ŸŽ Apple
    • ๐Ÿท๏ธ Tistory
    • ์˜ค๋กฏ์ด ๋‚˜์˜ ์‹œ๊ฐ„
Total
Today
Yesterday
hELLO ยท Designed By ์ •์ƒ์šฐ.v4.2.2
EarthSea
[ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ] ๊ทค ๊ณ ๋ฅด๊ธฐ
์ƒ๋‹จ์œผ๋กœ

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

๋‹จ์ถ•ํ‚ค

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

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

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

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

๋ชจ๋“  ์˜์—ญ

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

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