DevYoon

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] 혼자 λ†€κΈ°μ˜ 달인 (Python) λ³Έλ¬Έ

PS/Programmers

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€] 혼자 λ†€κΈ°μ˜ 달인 (Python)

gimewn 2023. 2. 19. 00:53

link πŸ”— https://school.programmers.co.kr/learn/courses/30/lessons/131130

 

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€

μ½”λ“œ μ€‘μ‹¬μ˜ 개발자 μ±„μš©. μŠ€νƒ 기반의 ν¬μ§€μ…˜ 맀칭. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€μ˜ 개발자 λ§žμΆ€ν˜• ν”„λ‘œν•„μ„ λ“±λ‘ν•˜κ³ , λ‚˜μ™€ 기술 ꢁ합이 잘 λ§žλŠ” 기업듀을 맀칭 λ°›μœΌμ„Έμš”.

programmers.co.kr

 

문제 μ„€λͺ…

ν˜Όμžμ„œλ„ 잘 λ…ΈλŠ” λ²”ν¬λŠ” μ–΄λŠ λ‚  방ꡬ석에 μžˆλŠ” 숫자 μΉ΄λ“œ 더미λ₯Ό λ³΄λ”λ‹ˆ 혼자 ν•  수 μžˆλŠ” μž¬λ―ΈμžˆλŠ” κ²Œμž„μ„ μƒκ°ν•΄λƒˆμŠ΅λ‹ˆλ‹€.

숫자 μΉ΄λ“œ λ”λ―Έμ—λŠ” μΉ΄λ“œκ°€ 총 100μž₯ 있으며, 각 μΉ΄λ“œμ—λŠ” 1λΆ€ν„° 100κΉŒμ§€ μˆ«μžκ°€ ν•˜λ‚˜μ”© μ ν˜€μžˆμŠ΅λ‹ˆλ‹€. 2 이상 100 μ΄ν•˜μ˜ μžμ—°μˆ˜λ₯Ό ν•˜λ‚˜ μ •ν•΄ κ·Έ μˆ˜λ³΄λ‹€ μž‘κ±°λ‚˜ 같은 숫자 μΉ΄λ“œλ“€μ„ μ€€λΉ„ν•˜κ³ , μ€€λΉ„ν•œ μΉ΄λ“œμ˜ 수만큼 μž‘μ€ μƒμžλ₯Ό μ€€λΉ„ν•˜λ©΄ κ²Œμž„μ„ μ‹œμž‘ν•  수 있으며 κ²Œμž„ 방법은 λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€.

μ€€λΉ„λœ μƒμžμ— μΉ΄λ“œλ₯Ό ν•œ μž₯μ”© λ„£κ³ , μƒμžλ₯Ό λ¬΄μž‘μœ„λ‘œ μ„žμ–΄ 일렬둜 λ‚˜μ—΄ν•©λ‹ˆλ‹€. μƒμžκ°€ 일렬둜 λ‚˜μ—΄λ˜λ©΄ μƒμžκ°€ λ‚˜μ—΄λœ μˆœμ„œμ— 따라 1λ²ˆλΆ€ν„° 순차적으둜 μ¦κ°€ν•˜λŠ” 번호λ₯Ό λΆ™μž…λ‹ˆλ‹€.

κ·Έ λ‹€μŒ μž„μ˜μ˜ μƒμžλ₯Ό ν•˜λ‚˜ μ„ νƒν•˜μ—¬ μ„ νƒν•œ μƒμž μ•ˆμ˜ 숫자 μΉ΄λ“œλ₯Ό ν™•μΈν•©λ‹ˆλ‹€. λ‹€μŒμœΌλ‘œ ν™•μΈν•œ μΉ΄λ“œμ— 적힌 λ²ˆν˜Έμ— ν•΄λ‹Ήν•˜λŠ” μƒμžλ₯Ό μ—΄μ–΄ μ•ˆμ— λ‹΄κΈ΄ μΉ΄λ“œμ— 적힌 숫자λ₯Ό ν™•μΈν•©λ‹ˆλ‹€. λ§ˆμ°¬κ°€μ§€λ‘œ μˆ«μžμ— ν•΄λ‹Ήν•˜λŠ” 번호λ₯Ό 가진 μƒμžλ₯Ό κ³„μ†ν•΄μ„œ μ—΄μ–΄κ°€λ©°, μ—΄μ–΄μ•Ό ν•˜λŠ” μƒμžκ°€ 이미 μ—΄λ €μžˆμ„ λ•ŒκΉŒμ§€ λ°˜λ³΅ν•©λ‹ˆλ‹€.

μ΄λ ‡κ²Œ μ—° μƒμžλ“€μ€ 1번 μƒμž κ·Έλ£Ήμž…λ‹ˆλ‹€. 이제 1번 μƒμž 그룹을 λ‹€λ₯Έ μƒμžλ“€κ³Ό μ„žμ΄μ§€ μ•Šλ„λ‘ λ”°λ‘œ λ‘‘λ‹ˆλ‹€. λ§Œμ•½ 1번 μƒμž 그룹을 μ œμ™Έν•˜κ³  λ‚¨λŠ” μƒμžκ°€ μ—†μœΌλ©΄ κ·ΈλŒ€λ‘œ κ²Œμž„μ΄ μ’…λ£Œλ˜λ©°, μ΄λ•Œ νšλ“ν•˜λŠ” μ μˆ˜λŠ” 0μ μž…λ‹ˆλ‹€.

그렇지 μ•Šλ‹€λ©΄ 남은 μƒμž 쀑 λ‹€μ‹œ μž„μ˜μ˜ μƒμž ν•˜λ‚˜λ₯Ό 골라 같은 λ°©μ‹μœΌλ‘œ 이미 μ—΄λ €μžˆλŠ” μƒμžλ₯Ό λ§Œλ‚  λ•ŒκΉŒμ§€ μƒμžλ₯Ό μ—½λ‹ˆλ‹€. μ΄λ ‡κ²Œ μ—° μƒμžλ“€μ€ 2번 μƒμž κ·Έλ£Ήμž…λ‹ˆλ‹€.

1번 μƒμž 그룹에 μ†ν•œ μƒμžμ˜ μˆ˜μ™€ 2번 μƒμž 그룹에 μ†ν•œ μƒμžμ˜ 수λ₯Ό κ³±ν•œ 값이 κ²Œμž„μ˜ μ μˆ˜μž…λ‹ˆλ‹€.

μƒμž μ•ˆμ— λ“€μ–΄μžˆλŠ” μΉ΄λ“œ λ²ˆν˜Έκ°€ μˆœμ„œλŒ€λ‘œ λ‹΄κΈ΄ λ°°μ—΄ cardsκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 범희가 이 κ²Œμž„μ—μ„œ 얻을 수 μžˆλŠ” 졜고 점수λ₯Ό κ΅¬ν•΄μ„œ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.


μ œν•œμ‚¬ν•­
  • 2  cards의 길이 ≤ 100
  • cards의 μ›μ†ŒλŠ” cards의 길이 μ΄ν•˜μΈ μž„μ˜μ˜ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • cardsμ—λŠ” μ€‘λ³΅λ˜λŠ” μ›μ†Œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.
  • cards[i]λŠ” i + 1번 μƒμžμ— λ‹΄κΈ΄ μΉ΄λ“œμ— 적힌 숫자λ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€.

 


 

def solution(cards):
    answer = 0
    length = len(cards)

    for first in range(length):
        # 1번 그룹 visit 체크
        visited01 = [0] * length
        pick = cards[first]
        # λ°©λ¬Έν–ˆλ˜ μƒμžλ₯Ό λ‹€μ‹œ λ°©λ¬Έν•œλ‹€λ©΄ break
        while visited01[pick - 1] == 0:
            # 방문 체크
            visited01[pick - 1] = 1
            # λ‹€μŒ λ°©λ¬Έν•  μƒμž 번호
            pick = cards[pick - 1]
            
        for second in range(first + 1, length):
            # 2번 그룹 visit 체크
            visited02 = visited01[:]
            pick = cards[second]
            # λ°©λ¬Έν–ˆλ˜ μƒμžλ₯Ό λ‹€μ‹œ λ°©λ¬Έν•œλ‹€λ©΄ break
            while visited02[pick - 1] == 0:
                # 방문 체크
                visited02[pick - 1] = 2
                # λ‹€μŒ λ°©λ¬Έν•  μƒμž 번호
                pick = cards[pick - 1]
            
            # 1번 그룹의 개수 * 2번 그룹의 개수
            score = visited01.count(1) * visited02.count(2)
            # max κ°±μ‹ 
            answer = max(answer, score)
            
    return answer

- 1번 κ·Έλ£Ήκ³Ό 2번 그룹을 λ‚˜λˆ„μ–΄ 문제 μ„€λͺ…λŒ€λ‘œ μƒμžλ₯Ό 열어보고, 각 그룹의 개수λ₯Ό κ³±ν•΄ maxλ₯Ό κ°±μ‹ ν•œλ‹€.