9017. 크로스 컨트리

9017 문제 보기

접근 방식

예전엔 백준 문제 티어를 항상 켜뒀었는데,
요즘 랜덤 기출 문제를 풀면서 정답처리가 되기 전에는 티어를 노출시키지 않은 채 문제를 풀다 보니까
쉽게 접근해도 되는 문제를 어렵게 접근하고.. 훨씬 준비에 효과적인 것 같다.
더불어 스스로 코테 풀이에 있어 내가 가장 우선적으로 보완해야하는 부분은
1. 쉽게 생각하는 능력 기르기(꼬아서 생각하지 말자!)

• 삽질부터 할 생각을 하면 디버깅 할 때도 삽질을 하게 된다...

2. 파이썬으로 코딩테스트를 볼 것이기에 파이썬에서 제공하는 툴 중 활용할 것이 있는지 꼭 먼저 생각해보기
   인 것 같다 😂

🥄 이것은 삽입니다. 삽질이라는 이야기죠. 삽질의 연속인 제 코드입니다. 게다가 틀렸습니다.

정말 돌고 돌아서 문제를 풀이했고,
삽질의 삽질을 거듭해 테스트케이스가 맞았을 때 엄청나게 신났지만!
채점 1%에서 틀렸습니다를 맛보고 30초정도 좌절^^ 하지만

내 접근 방식은 이랬다.

1. 6명이 되지 않는 팀 추리기 (카운터로 팀 개수 추리기: .count())
2. 팀 번호 배열 순회하며 1 조건에 만족하지 못하는 팀 제외 추가 점수 배열에 저장하기
3. 2번 결과에서 각 팀 별 상위 4개 점수 합 구하기(인덱스 별로 점수 정렬되어있기에 추가 정렬 필요 X)
[[1, 4, 6, 7, 9, 12, 18], [], [2, 3, 5, 8, 10, 11, 18], []]
-> 팀원이 6명 되는 배열마다 배열 가장 마지막 원소에 1~4 더한 값 넣어줌 
-> ex) score[i][-1]으로 접근

# 자랑스런 나의 삽질 코드 ^ㅁ^
import sys
input = sys.stdin.readline

T = int(input().rstrip())
for _ in range(T):
  N = int(input().rstrip())
  arr = list(map(int, input().rstrip().split()))
  
  unique_team = list(set(arr)) # 팀이 몇 개 있는지 추리기 위한 작업
  six_check = [[i+1, arr.count(unique_team[i])] for i in range(len(unique_team))] # 팀 당 여섯명이 되는지 체크하기 위한 배열
  score = [[] for _ in range(len(unique_team))]

  cnt = 1
  for i in range(len(arr)):
    if six_check[arr[i]-1][1] >= 6: # 6명이 넘는 팀의 경우
      score[six_check[arr[i]-1][0] - 1].append(cnt) # 점수 부여
      cnt += 1

  candi = []
  for i in range(len(score)):
    if len(score[i]) >= 4:
      score[i].append(sum(score[i][:4])) # score의 가장 마지막 인덱스에 상위 4개 점수 합 저장
      candi.append((i+1, score[i][-1]))
  
  if len(candi) == 1: # 후보군이 하나일 경우
    print(candi[0][0])
    break
  else: # 후보군이 여러개일 경우
    idx = 999
    for i in range(len(candi)): # candi[i][0]에 저장된 팀번호를 바탕으로 5번째 원소를 비교
      for j in range(1, len(candi)):
        if score[candi[i][0] - 1][4] < score[candi[j][0] - 1][4]:
          idx = i+1 # 더 높은 점수를 가진 팀 번호를 idx에 저장
    print(idx)

처참히 틀려버렸고...
끼워맞추기 식으로 코드를 짰더니 디버깅하기도 너무 어려웠다...
분명 이렇게 풀지 않아도 충분히 쉽게 접근 가능할텐데!! 하면서 다른 풀이를 찾아봤다.
다음 문제부터 찾아보지마!!!!

최종 코드

import sys
from collections import Counter
input = sys.stdin.readline

T = int(input().rstrip())
for _ in range(T):
  N = int(input().rstrip())
  arr = list(map(int, input().rstrip().split()))
  
  counter = Counter(arr)
  score = {}
  cnt = 0

  for i in range(N):
    if counter[arr[i]] < 6:
      cnt += 1
      continue

    if arr[i] in score:
      score[arr[i]].append(i - cnt + 1)
    
    else:
      score[arr[i]] = [i - cnt + 1]

  print(score)

  print(sorted(score, key=lambda x:(sum(score[x][:4]), score[x][4]))[0])

내 머리를 때린 풀이 방법.
(놀랍게도 제 도파민공유자 겸 취준메이트의 코드였다죠... 카톡으로 잠시 경의를 표함)

1. 팀 번호가 몇개 있는지 set으로 추리고, 또 count()로 저장했던 과정(메모리 낭비)
2. lambda를 통해 정렬 조건을 순차적으로 적용해줄 수 있음을 생각하지 않음(추가적인 메모리와 반복으로 인한 시간 소요)

이 두 부분에서 코드의 간결함과 가독성이 훨씬 향상됨을 발견했다.

1️⃣ Counter를 사용해 {팀번호: 팀원수, 팀번호: 팀원수, ...}로 한번에 정리 가능

• 이 때 Counter로부터 생성된 counter는 Counter({1: 6, 3: 6, 2: 2, 4: 1})와 같이 빈도수가 높은 것부터 정렬되어 리턴된다.

2️⃣ 정렬의 key로 첫번째 조건은 1~4등의 점수 합을 기준으로, 첫번째 조건에서 동일한 점수 합이 나올 경우 두번째 조건으로 5등의 점수를 기준으로 정렬을 해준다.

• 2번 과정을 거칠 경우 sorted()를 사용했기에 해당 조건으로 정렬된 새로운 리스트가 반환된다.
• 위 15개의 입력값 예제에 대해서는 {1: [1, 4, 6, 7, 9, 12], 3: [2, 3, 5, 8, 10, 11]}가 반환된다.
• 여기서 [0]를 출력하므로 위 두개의 조건으로 정렬된 리스트 중 가장 첫번째에 위치하는 팀 번호가 출력된다.

배운점

▶️ Counter 활용을 잘 하자
▶️ 파이썬의 정렬 방법을 꼭 잘 알아두자
▶️ lambda와 filter는 정말 유용하다