[Programmers] Level 2. 혼자 놀기의 달인

2025. 1. 28. 20:32·코딩테스트/Python
728x90
반응형

🔗 Problem Link

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr


❔Thinking

  • 상자를 열어서 해당 상자 안에 있는 숫자에 해당하는 상자를 연속적으로 열어나간다.
  • 한번에 열 수 있는 상자의 수를 기록하고, 더이상 열 수 있는 상자가 없을 때까지 상자를 선택하여 연다.
  • 한번에 연 상자들을 그룹화할때, 두 개의 그룹의 상자 수를 최대로 한 경우를 반환한다. 그룹이 하나라면 0이다.

💻Solution

def solution(cards):
    answer = []
    visited = [False] * len(cards)
    
    def dfs(num:int):
        cnt = 0
        cur = num
        while visited[cur] is False:
            visited[cur] = True
            cnt += 1
            cur = cards[cur] - 1
        return cnt
    
    for i in range(len(cards)):
        if visited[i] is False:
            answer.append(dfs(i))
    answer.sort()
    return answer[-1]*answer[-2] if len(answer) > 1 else 0

🗝️keypoint

  1. DFS로 상자의 숫자를 확인하여 해당 번호의 상자를 열어나가고, 이미 연 상자라면 멈춘다.
  2. 그룹이 하나라면 답은 0이고, 하나 이상이라면 가장 큰 두 수를 곱하여 반환한다.
  3. 상자의 개수가 100개 이기 때문에, DFS로도 충분히 해결할 수 있다.
저작자표시 (새창열림)

'코딩테스트 > Python' 카테고리의 다른 글

[Programmers] Level 2. 양궁대회  (1) 2025.01.31
[Baekjoon] 1025. 제곱수 찾기  (0) 2025.01.30
[Baekjoon] 1202. 보석 도둑  (0) 2025.01.28
[Programmers] Level 2. 혼자서 하는 틱택토  (0) 2025.01.24
[Baekjoon] 2493. 탑  (0) 2025.01.20
'코딩테스트/Python' 카테고리의 다른 글
  • [Programmers] Level 2. 양궁대회
  • [Baekjoon] 1025. 제곱수 찾기
  • [Baekjoon] 1202. 보석 도둑
  • [Programmers] Level 2. 혼자서 하는 틱택토
swwho
swwho
일상을 데이터화하다
  • swwho
    하루한장
    swwho
  • 전체
    오늘
    어제
    • 분류 전체보기 (188)
      • ML_DL (39)
        • MUJAKJUNG (무작정 시리즈) (18)
        • 딥러닝 공부하기 (21)
      • 데이터사이언스 (1)
        • EDA (1)
        • 데이터과학을 위한 통계 (0)
      • 데이터엔지니어링 (2)
      • 논문리뷰 (2)
        • Computer Vision (2)
      • Python 활용하기 (12)
      • 코딩테스트 (127)
        • Python (109)
        • MySQL (14)
      • Git (3)
      • MySQL 활용하기 (0)
      • 일상 이야기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
swwho
[Programmers] Level 2. 혼자 놀기의 달인
상단으로

티스토리툴바