Algorithm๐Ÿงถ | ์‹คํŒจ์œจ

saneeeeeeee_Yaยท2021๋…„ 3์›” 25์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
9/11
post-thumbnail

https://programmers.co.kr/learn/courses/30/lessons/42889

๋ฌธ์ œ ์„ค๋ช…

์Šˆํผ ๊ฒŒ์ž„ ๊ฐœ๋ฐœ์ž ์˜ค๋ ๋ฆฌ๋Š” ํฐ ๊ณ ๋ฏผ์— ๋น ์กŒ๋‹ค. ๊ทธ๋…€๊ฐ€ ๋งŒ๋“  ํ”„๋žœ์ฆˆ ์˜ค์ฒœ์„ฑ์ด ๋Œ€์„ฑ๊ณต์„ ๊ฑฐ๋’€์ง€๋งŒ, ์š”์ฆ˜ ์‹ ๊ทœ ์‚ฌ์šฉ์ž์˜ ์ˆ˜๊ฐ€ ๊ธ‰๊ฐํ•œ ๊ฒƒ์ด๋‹ค. ์›์ธ์€ ์‹ ๊ทœ ์‚ฌ์šฉ์ž์™€ ๊ธฐ์กด ์‚ฌ์šฉ์ž ์‚ฌ์ด์— ์Šคํ…Œ์ด์ง€ ์ฐจ์ด๊ฐ€ ๋„ˆ๋ฌด ํฐ ๊ฒƒ์ด ๋ฌธ์ œ์˜€๋‹ค.

์ด ๋ฌธ์ œ๋ฅผ ์–ด๋–ป๊ฒŒ ํ• ๊นŒ ๊ณ ๋ฏผ ํ•œ ๊ทธ๋…€๋Š” ๋™์ ์œผ๋กœ ๊ฒŒ์ž„ ์‹œ๊ฐ„์„ ๋Š˜๋ ค์„œ ๋‚œ์ด๋„๋ฅผ ์กฐ์ ˆํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. ์—ญ์‹œ ์Šˆํผ ๊ฐœ๋ฐœ์ž๋ผ ๋Œ€๋ถ€๋ถ„์˜ ๋กœ์ง์€ ์‰ฝ๊ฒŒ ๊ตฌํ˜„ํ–ˆ์ง€๋งŒ, ์‹คํŒจ์œจ์„ ๊ตฌํ•˜๋Š” ๋ถ€๋ถ„์—์„œ ์œ„๊ธฐ์— ๋น ์ง€๊ณ  ๋ง์•˜๋‹ค. ์˜ค๋ ๋ฆฌ๋ฅผ ์œ„ํ•ด ์‹คํŒจ์œจ์„ ๊ตฌํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ์™„์„ฑํ•˜๋ผ.

  • ์‹คํŒจ์œจ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•œ๋‹ค.
    • ์Šคํ…Œ์ด์ง€์— ๋„๋‹ฌํ–ˆ์œผ๋‚˜ ์•„์ง ํด๋ฆฌ์–ดํ•˜์ง€ ๋ชปํ•œ ํ”Œ๋ ˆ์ด์–ด์˜ ์ˆ˜ / ์Šคํ…Œ์ด์ง€์— ๋„๋‹ฌํ•œ ํ”Œ๋ ˆ์ด์–ด ์ˆ˜

์ „์ฒด ์Šคํ…Œ์ด์ง€์˜ ๊ฐœ์ˆ˜ N, ๊ฒŒ์ž„์„ ์ด์šฉํ•˜๋Š” ์‚ฌ์šฉ์ž๊ฐ€ ํ˜„์žฌ ๋ฉˆ์ถฐ์žˆ๋Š” ์Šคํ…Œ์ด์ง€์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด stages๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์‹คํŒจ์œจ์ด ๋†’์€ ์Šคํ…Œ์ด์ง€๋ถ€ํ„ฐ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์Šคํ…Œ์ด์ง€์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ฒจ์žˆ๋Š” ๋ฐฐ์—ด์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜๋ผ.

์ œํ•œ์‚ฌํ•ญ

  • ์Šคํ…Œ์ด์ง€์˜ ๊ฐœ์ˆ˜ N์€ 1 ์ด์ƒ 500 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.
  • stages์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 200,000 ์ดํ•˜์ด๋‹ค.
  • stages์—๋Š” 1 ์ด์ƒ N + 1 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๊ฐ€ ๋‹ด๊ฒจ์žˆ๋‹ค.
    • ๊ฐ ์ž์—ฐ์ˆ˜๋Š” ์‚ฌ์šฉ์ž๊ฐ€ ํ˜„์žฌ ๋„์ „ ์ค‘์ธ ์Šคํ…Œ์ด์ง€์˜ ๋ฒˆํ˜ธ๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.
    • ๋‹จ, N + 1 ์€ ๋งˆ์ง€๋ง‰ ์Šคํ…Œ์ด์ง€(N ๋ฒˆ์งธ ์Šคํ…Œ์ด์ง€) ๊นŒ์ง€ ํด๋ฆฌ์–ด ํ•œ ์‚ฌ์šฉ์ž๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.
  • ๋งŒ์•ฝ ์‹คํŒจ์œจ์ด ๊ฐ™์€ ์Šคํ…Œ์ด์ง€๊ฐ€ ์žˆ๋‹ค๋ฉด ์ž‘์€ ๋ฒˆํ˜ธ์˜ ์Šคํ…Œ์ด์ง€๊ฐ€ ๋จผ์ € ์˜ค๋„๋ก ํ•˜๋ฉด ๋œ๋‹ค.
  • ์Šคํ…Œ์ด์ง€์— ๋„๋‹ฌํ•œ ์œ ์ €๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ ํ•ด๋‹น ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ 0 ์œผ๋กœ ์ •์˜ํ•œ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

Nstagesresult
5[2, 1, 2, 6, 2, 4, 3, 3][3,4,2,1,5]
4[4,4,4,4,4][4,1,2,3]

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

์ž…์ถœ๋ ฅ ์˜ˆ #1
1๋ฒˆ ์Šคํ…Œ์ด์ง€์—๋Š” ์ด 8๋ช…์˜ ์‚ฌ์šฉ์ž๊ฐ€ ๋„์ „ํ–ˆ์œผ๋ฉฐ, ์ด ์ค‘ 1๋ช…์˜ ์‚ฌ์šฉ์ž๊ฐ€ ์•„์ง ํด๋ฆฌ์–ดํ•˜์ง€ ๋ชปํ–ˆ๋‹ค. ๋”ฐ๋ผ์„œ 1๋ฒˆ ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • 1 ๋ฒˆ ์Šคํ…Œ์ด์ง€ ์‹คํŒจ์œจ : 1/8

2๋ฒˆ ์Šคํ…Œ์ด์ง€์—๋Š” ์ด 7๋ช…์˜ ์‚ฌ์šฉ์ž๊ฐ€ ๋„์ „ํ–ˆ์œผ๋ฉฐ, ์ด ์ค‘ 3๋ช…์˜ ์‚ฌ์šฉ์ž๊ฐ€ ์•„์ง ํด๋ฆฌ์–ดํ•˜์ง€ ๋ชปํ–ˆ๋‹ค. ๋”ฐ๋ผ์„œ 2๋ฒˆ ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • 2 ๋ฒˆ ์Šคํ…Œ์ด์ง€ ์‹คํŒจ์œจ : 3/7

๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋‚˜๋จธ์ง€ ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • 3 ๋ฒˆ ์Šคํ…Œ์ด์ง€ ์‹คํŒจ์œจ : 2/4
  • 4๋ฒˆ ์Šคํ…Œ์ด์ง€ ์‹คํŒจ์œจ : 1/2
  • 5๋ฒˆ ์Šคํ…Œ์ด์ง€ ์‹คํŒจ์œจ : 0/1

๊ฐ ์Šคํ…Œ์ด์ง€์˜ ๋ฒˆํ˜ธ๋ฅผ ์‹คํŒจ์œจ์˜ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  • [3,4,2,1,5]

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

๋ชจ๋“  ์‚ฌ์šฉ์ž๊ฐ€ ๋งˆ์ง€๋ง‰ ์Šคํ…Œ์ด์ง€์— ์žˆ์œผ๋ฏ€๋กœ 4๋ฒˆ ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ 1์ด๋ฉฐ ๋‚˜๋จธ์ง€ ์Šคํ…Œ์ด์ง€์˜ ์‹คํŒจ์œจ์€ 0์ด๋‹ค.

  • [4,1,2,3]

๋ฌธ์ œ ํ’€์ด

def solution(N, stages):
    c = {}
    user = len(stages)
    for i in range(1,N+1):
        c[i] = 0
        if i in stages: #์Šคํ…Œ์ด์ง€์— ํ•ด๋‹น๋ฒˆ์งธ ์Šคํ…Œ์ด์ง€๊ฐ€ ์žˆ๋‹ค๋ฉด
            cnt = stages.count(i) #์Šคํ…Œ์ด์ง€๋งˆ๋‹ค ์‚ฌ๋žŒ๋“ค ์ˆ˜
            faile = cnt/user #์Šคํ…Œ์ด์ง€๋งˆ๋‹ค ์‹คํŒจ์œจ
            user -= cnt
            if cnt != None: #c dictionary์— ์‹คํŒจ์œจ๊ณผ ์ธ๋ฑ์Šค ์ถ”๊ฐ€
                c[i] = faile
        
    c = sorted(c.items(), key=lambda x: x[1], reverse=True)
    answer = []
    for i in c:
        answer.append(i[0])
    return answer

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

def solution(N, stages):
    result = {}
    denominator = len(stages)
    for stage in range(1, N+1):
        if denominator != 0:
            count = stages.count(stage)
            result[stage] = count / denominator
            denominator -= count
        else:
            result[stage] = 0
    return sorted(result, key=lambda x : result[x], reverse=True)
profile
๐Ÿœhttps://action2thefuture.github.io/๐Ÿœ

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