Baekjoon 2696번 중앙값 구하기

💭 문제가 궁금하다면?

내가 시도한 방법

T = int(input())                                # T: 테스트 케이스 갯수

for _ in range(T):

    N = int(input())                            # N: 수열의 크기

    cnt = N//2+1                                # cnt: 출력하는 중앙값 갯수

    lst = []                                    # lst: 전체 수열이 담긴 배열
    answer = []                                 # answer: 출력하는 중앙값이 담긴 배열

    for n in range(N//10+1):
        # ex) 원소가 9개 -> 1줄 입력 받아야 함 
        # 원소가 23개 -> 3줄 입력 받아야 함
        # 즉, N//10+1번 순회해야 함

        line = list(map(int, input().split()))  # line: 10개씩 나눈 부분 수열

        for th in range(len(line)):

            lst.append(line[th])

            if not th % 2:
                lst.sort()
                answer.append(lst[(th+n*10)//2])

    # 출력
    print(cnt)

    for i in range(cnt//10+1):
        print(*answer[10*i:10*i+10])

느낀 점

• 입출력으로도 어려운 문제를 만들 수 있다...ㅎ.
  • 해당 문제는 그동안 풀었던 문제와 다르게 입출력에서 분명한 차별화된 포인트가 있었다. 수열을 입출력할 때, 10개 단위로 맞춰야했다.
  • 출력은 예전에 비슷한 문제를 접한 적이 있어서 큰 어려움은 없었는데,
  • 입력 부분은 프린트를 사용해서 어떤 식으로 들어오는 지(10개 단위를 자르는 방식, 홀수번째 골라내기 등) 눈으로 확인하면서 코드 설계를 했다.
  • 다양한 문제를 풀어보는 게 중요하다는 생각을 했는데 거기에 입출력 형태도 추가...해야겠다..ㅎ
    
    
• 어떤 행위가 필요한 부분과 상황을 명확히 그려보기
  • 처음에 패스한 코드에는 lst.sort()를 lst.append(line[th])아래에 적었었다.
  • 그런데 사실 정렬이 필요한 순간은 중앙값을 출력할 때!
    즉, 홀수번째 값이 입력되고 중앙값이 출력되기 전에만 정렬이 필요했던 것이다! 원소가 추가될 때 마다 정렬을 할 필요가 없었다!!
  • 생각못한 부분이었는데 스터디원의 코드에서...리팩토링 요소를 얻었다....
    
    
• 힙으로 구현 다시 해보기
  • 처음에는 힙을 이용해보려고 했다.
  • 중앙값으로 힙의 크기 // 2 + 1 번째 값을 뽑아내면 될 거라고 생각했는데 예시 출력과 답이 틀렸었다...(엄청 예전이라 정확히 뭐가 틀렸는지 기억이 가물가물....) 그래서 포기하고 그냥 정렬을 사용했는데 힙으로 풀이한 코드가 있었다...
  • 그래서 추가 과제가 생겼다..ㅎ
    📌 힙으로 설계했을 때 막힌 부분 떠올려보기
    📌 힙으로 구현하기