๐Ÿค”[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ˆซ์ž ๊ฒŒ์ž„

Chobbyยท2022๋…„ 4์›” 26์ผ
1

Programmers

๋ชฉ๋ก ๋ณด๊ธฐ
30/344
post-thumbnail

๋ฌธ์ œ ์„ค๋ช…

xx ํšŒ์‚ฌ์˜ 2xN๋ช…์˜ ์‚ฌ์›๋“ค์€ N๋ช…์”ฉ ๋‘ ํŒ€์œผ๋กœ ๋‚˜๋ˆ  ์ˆซ์ž ๊ฒŒ์ž„์„ ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋‘ ๊ฐœ์˜ ํŒ€์„ ๊ฐ๊ฐ AํŒ€๊ณผ BํŒ€์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ˆซ์ž ๊ฒŒ์ž„์˜ ๊ทœ์น™์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • ๋จผ์ € ๋ชจ๋“  ์‚ฌ์›์ด ๋ฌด์ž‘์œ„๋กœ ์ž์—ฐ์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ๋ถ€์—ฌ๋ฐ›์Šต๋‹ˆ๋‹ค.
  • ๊ฐ ์‚ฌ์›์€ ๋”ฑ ํ•œ ๋ฒˆ์”ฉ ๊ฒฝ๊ธฐ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฐ ๊ฒฝ๊ธฐ๋‹น AํŒ€์—์„œ ํ•œ ์‚ฌ์›์ด, BํŒ€์—์„œ ํ•œ ์‚ฌ์›์ด ๋‚˜์™€ ์„œ๋กœ์˜ ์ˆ˜๋ฅผ ๊ณต๊ฐœํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋•Œ ์ˆซ์ž๊ฐ€ ํฐ ์ชฝ์ด ์Šน๋ฆฌํ•˜๊ฒŒ ๋˜๊ณ , ์Šน๋ฆฌํ•œ ์‚ฌ์›์ด ์†ํ•œ ํŒ€์€ ์Šน์ ์„ 1์  ์–ป๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
  • ๋งŒ์•ฝ ์ˆซ์ž๊ฐ€ ๊ฐ™๋‹ค๋ฉด ๋ˆ„๊ตฌ๋„ ์Šน์ ์„ ์–ป์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์ „์ฒด ์‚ฌ์›๋“ค์€ ์šฐ์„  ๋ฌด์ž‘์œ„๋กœ ์ž์—ฐ์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ๋ถ€์—ฌ๋ฐ›์•˜์Šต๋‹ˆ๋‹ค. ๊ทธ๋‹ค์Œ AํŒ€์€ ๋น ๋ฅด๊ฒŒ ์ถœ์ „์ˆœ์„œ๋ฅผ ์ •ํ–ˆ๊ณ  ์ž์‹ ๋“ค์˜ ์ถœ์ „ ์ˆœ์„œ๋ฅผ BํŒ€์—๊ฒŒ ๊ณต๊ฐœํ•ด๋ฒ„๋ ธ์Šต๋‹ˆ๋‹ค. BํŒ€์€ ๊ทธ๊ฒƒ์„ ๋ณด๊ณ  ์ž์‹ ๋“ค์˜ ์ตœ์ข… ์Šน์ ์„ ๊ฐ€์žฅ ๋†’์ด๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ํŒ€์›๋“ค์˜ ์ถœ์ „ ์ˆœ์„œ๋ฅผ ์ •ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ์˜ BํŒ€์ด ์–ป๋Š” ์Šน์ ์„ ๊ตฌํ•ด์ฃผ์„ธ์š”.
A ํŒ€์›๋“ค์ด ๋ถ€์—ฌ๋ฐ›์€ ์ˆ˜๊ฐ€ ์ถœ์ „ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ด๋˜์–ด์žˆ๋Š” ๋ฐฐ์—ด A์™€ i๋ฒˆ์งธ ์›์†Œ๊ฐ€ BํŒ€์˜ i๋ฒˆ ํŒ€์›์ด ๋ถ€์—ฌ๋ฐ›์€ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ๋ฐฐ์—ด B๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, B ํŒ€์›๋“ค์ด ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์Šน์ ์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • A์™€ B์˜ ๊ธธ์ด๋Š” ๊ฐ™์Šต๋‹ˆ๋‹ค.
  • A์™€ B์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 100,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • A์™€ B์˜ ๊ฐ ์›์†Œ๋Š” 1 ์ด์ƒ 1,000,000,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

ABresult
[5,1,3,7][2,2,6,8]3
[2,2,2,2][1,1,1,1]0

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

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

A ํŒ€์€ ์ˆซ์ž 5๋ฅผ ๋ถ€์—ฌ๋ฐ›์€ ํŒ€์›์ด ์ฒซ๋ฒˆ์งธ๋กœ ์ถœ์ „ํ•˜๊ณ , ์ด์–ด์„œ 1,3,7์„ ๋ถ€์—ฌ๋ฐ›์€ ํŒ€์›๋“ค์ด ์ฐจ๋ก€๋Œ€๋กœ ์ถœ์ „ํ•ฉ๋‹ˆ๋‹ค.
B ํŒ€์›๋“ค์„ 4๋ฒˆ, 2๋ฒˆ, 3๋ฒˆ, 1๋ฒˆ์˜ ์ˆœ์„œ๋Œ€๋กœ ์ถœ์ „์‹œํ‚ฌ ๊ฒฝ์šฐ ํŒ€์›๋“ค์ด ๋ถ€์—ฌ๋ฐ›์€ ์ˆซ์ž๋“ค์€ ์ฐจ๋ก€๋Œ€๋กœ 8,2,6,2๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฉด, ์ฒซ ๋ฒˆ์งธ, ๋‘ ๋ฒˆ์งธ, ์„ธ ๋ฒˆ์งธ ๊ฒฝ๊ธฐ์—์„œ ์Šน๋ฆฌํ•˜์—ฌ 3์ ์„ ์–ป๊ฒŒ ๋˜๊ณ , ์ด๋•Œ๊ฐ€ ์ตœ๋Œ€์˜ ์Šน์ ์ž…๋‹ˆ๋‹ค.

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

B ํŒ€์›๋“ค์„ ์–ด๋–ค ์ˆœ์„œ๋กœ ์ถœ์ „์‹œ์ผœ๋„ BํŒ€์˜ ์Šน์ ์€ 0์ ์ž…๋‹ˆ๋‹ค.

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

3๋‹จ๊ณ„ ์น˜๊ณ  ๊ต‰์žฅํžˆ ๊ฐ„๋‹จํ•œ ๋ฌธ์ œ์ด๋ฉฐ Greedyํ˜• ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

์šฐ์„  ๋‘ ๋ฐฐ์—ด์„ ์ •๋ ฌํ•œ ํ›„ ๊ฐ ์š”์†Œ๋ฅผ ๋น„๊ตํ•˜๋ฉฐ A๋ฐฐ์—ด์ด B๋ฐฐ์—ด์˜ ์š”์†Œ๋ณด๋‹ค ์ž‘๋‹ค๋ฉด ๋‹ค์Œ ์š”์†Œ๋ฅผ ๋น„๊ตํ•˜๋ฉฐ ๊ฐ™๊ฑฐ๋‚˜ ํฌ๋‹ค๋ฉด B์š”์†Œ์˜ ๋‹ค์Œ์š”์†Œ์™€ ํ˜„์žฌ์˜ A๋ฐฐ์—ด ์š”์†Œ๋ฅผ ๋น„๊ต ๋ฐ˜๋ณตํ•จ.

function solution(A, B) {
    let count = 0
    A = A.sort((a,b) => a-b)
    B = B.sort((a,b) => a-b)
    A.forEach((el,idx) => {
        if(A[count] < B[idx]) count++
    })
    
    return count
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€