[python] 해시 오답정리 (1)

📌 이번에 푼 문제

#	문제	출처	링크
1	오픈채팅방	프로그래머스 (2019 카카오)	바로가기
2	주차 요금 계산	프로그래머스 (2022 카카오)	바로가기
3	롤케이크 자르기	프로그래머스	바로가기
4	신고 결과 받기	프로그래머스 (2022 카카오)	바로가기

다음에 풀 문제 : 보석 쇼핑, 순위 검색

---

1. 오픈채팅방

어떻게 풀었나 (잘못된 접근)

각 record를 split해서 저장해놓고 풀기 시작했는데, 처음부터 꼬였다.

def solution(record):
    answer = []
    result = [x.split(" ") for x in record]
    name_list = {}
    chat = []

    def savestack(result):
        if result[0] == "Enter":
            name_list[result[1]] = result[2]
            chat.append(result[2])      # ← 닉네임을 넣고 있음
        if result[0] == "Leave":
            chat.remove(result[2])      # ← Leave에는 닉네임이 아예 안 들어옴 (없는 인덱스 접근)
        if result[0] == "Change":
            name_list[result[1]] = result[2]

    for _ in range(len(result)):
        savestack(result[_])
    return answer

내가 몰랐던 점 / 틀린 이유

• Leave 명령은 닉네임 없이 들어오는데, 없는 인덱스(result[2])에 접근하려고 했다.
• 닉네임을 키처럼 저장하려고 했다. 닉네임은 Change로 계속 바뀌는 값이라 키가 될 수 없다. 변하지 않는 건 아이디(uid)다.
• 자료구조의 성격에 따라 저장해야 할 데이터를 명확히 분리하지 않았다.
  name_list(dict)와 chat(list)을 만들어 놓고는 chat에도 닉네임을 넣으려고 했다.
  • → name_list : key(아이디) : value(닉네임)
  • → chat : 닉네임이 아닌 아이디를 넣어야 함

개선한 풀이

핵심은 "이벤트는 아이디로 기록해두고, 닉네임은 마지막에 dict에서 꺼내 붙인다"이다.

def solution(record):
    name_list = {}          # uid → 최종 닉네임
    events = []             # (uid, "들어왔습니다."/"나갔습니다.") 순서대로

    for line in record:
        parts = line.split(" ")
        cmd, uid = parts[0], parts[1]

        if cmd == "Enter":
            name_list[uid] = parts[2]
            events.append((uid, "들어왔습니다."))
        elif cmd == "Leave":
            events.append((uid, "나갔습니다."))
        elif cmd == "Change":
            name_list[uid] = parts[2]

    return [f"{name_list[uid]}님이 {msg}" for uid, msg in events]

마지막 조합은 리스트 컴프리헨션 한 줄로 끝난다. 다음부터는 "변하는 값(닉네임)은 value, 변하지 않는 값(아이디)은 key" 원칙으로 dict를 설계해야겠다.

---

2. 주차 요금 계산

어떻게 풀었나 (잘못된 접근)

{차량번호: 입차시간}, {차량번호: 누적시간} 두 개의 dict로 분리한 것까지는 좋았는데, 누적 처리에서 막혔다.

def solution(fees, records):
    answer = []
    default_t, default_f, t, f = fees

    car_in = {}        # {차량번호: 입차시간}
    car_time = {}      # {차량번호: 누적시간}

    for i in records:
        time, car, io = i.split(" ")
        h, m = int(time[:2]), int(time[3:])

        if io == "IN":
            car_in[car] = [h - 1, m + 60]
        if io == "OUT":
            car_time[car] = (h - car_in[car][0]) * 60 + m - car_in[car][1]   # ← = 대입이라 누적이 안 됨
    return answer

내가 몰랐던 점 / 틀린 이유

• 같은 차가 여러 번 입·출차하는 경우를 고려하려면 car_time[car] = ...이 아니라 +=로 누적해야 한다.
• 그런데 일반 dict에서 +=로 바꾸면 KeyError가 난다. (없는 키에 더하려고 하니까)
  → from collections import defaultdict 후 car_time = defaultdict(int)로 선언해야 한다.
• 출차 안 한 차량(23:59 처리)을 계산하려면, 출차한 차량은 car_in에서 del 해줘야 한다!! 이걸 안 해서 한참 헤맸다.
• dict 정렬도 헷갈렸다:
  • sorted(dict) → key 기준 오름차순의 key 리스트가 나온다.

    print(car_time)              # defaultdict(<class 'int'>, {'3961': 121, '0202': 120})
    car_time = sorted(car_time)
    print(car_time)              # ['0202', '3961']

  • 내림차순 → reverse=True 옵션 추가
  • 값(value) 기준 → sorted(dict.items(), key=lambda x: x[1])

💡 저장해야 하는 데이터의 특성을 파악하고, 적절한 자료구조를 택해서 어떤 데이터는 남기고 어떤 데이터는 버려야 하는지 꼭 고려해야 한다.

개선한 풀이

from collections import defaultdict
import math

def solution(fees, records):
    answer = []
    default_t, default_f, t, f = fees

    car_in = {}                   # {차량번호: 입차시간 [h, m]}
    car_time = defaultdict(int)   # {차량번호: 누적시간} — +=로 누적 가능

    for i in records:
        time, car, io = i.split(" ")
        h, m = int(time[:2]), int(time[3:])

        if io == "IN":
            car_in[car] = [h - 1, m + 60]
        if io == "OUT":
            car_time[car] += (h - car_in[car][0]) * 60 + m - car_in[car][1]
            del car_in[car]       # 출차했으면 입차 기록에서 제거!

    # 출차 안 한 차량은 23:59 출차 처리
    for car in car_in:
        h, m = 23, 59
        car_time[car] += (h - car_in[car][0]) * 60 + m - car_in[car][1]

    # 차량번호 오름차순으로 주차요금 계산
    for car in sorted(car_time):
        if car_time[car] > default_t:
            real_time = math.ceil((car_time[car] - default_t) / t)
        else:
            real_time = 0
        answer.append(default_f + real_time * f)

    return answer

누적이 필요한 dict는 처음부터 defaultdict(int)로 선언하고, 처리 끝난 데이터는 del로 지워서 "남은 데이터" 자체가 의미를 갖게 만드는 패턴을 기억하자.

---

3. 롤케이크 자르기

어떻게 풀었나 (잘못된 접근 → 시간초과 ㅠㅠ)

자르는 지점마다 슬라이싱해서 양쪽의 Counter를 매번 새로 구했다.

from collections import Counter

def solution(topping):
    answer = 0
    for i in range(1, len(topping)):
        chulsu = topping[:i]
        dongsang = topping[i:]
        if len(Counter(chulsu).keys()) == len(Counter(dongsang).keys()):
            answer += 1
    return answer

로직은 맞는데 시간초과가 났다. 매 반복마다 슬라이싱 O(n) + Counter 생성 O(n)이라 전체 O(n²)이 되기 때문이다.

내가 몰랐던 점 / 틀린 이유

• 매번 Counter를 구하지 마라. 한쪽으로 몰빵해놓고 하나씩 넘겨주는 방식이 웬만하면 빠르다.
• Counter도 어차피 dict이기 때문에 chulsu[t] += 1 같은 식으로 직접 접근/수정이 가능하다.
• 단, 개수만 0이 되면 key는 남아있으므로 dongsang[t] == 0이면 del dongsang[t]로 지워야 len()(가짓수)이 제대로 줄어든다.

개선한 풀이

처음에 동생이 전부 갖고 시작 → 철수에게 하나씩 넘기면서 가짓수만 비교한다. O(n)으로 끝난다.

from collections import Counter

def solution(topping):
    answer = 0
    chulsu = Counter()
    dongsang = Counter(topping)   # 동생이 전부 갖고 시작

    for t in topping:
        chulsu[t] += 1            # 하나씩 철수에게 넘기기
        dongsang[t] -= 1
        if dongsang[t] == 0:
            del dongsang[t]       # 0이 된 key는 지워야 가짓수(len)가 줄어든다

        if len(chulsu) == len(dongsang):
            answer += 1
    return answer

"구간을 나눠서 양쪽을 비교"하는 문제는 매번 다시 계산하지 말고, 경계를 옮기며 차분만 갱신하는 게 정석이라는 걸 배웠다.

---

4. 신고 결과 받기

어떻게 풀었나

오!!! 처음으로 AI 도움 안 받고 풀었다!! 신고 관계를 dict 두 개로 나눠 저장하는 설계가 바로 떠올랐다.

from collections import Counter
from collections import defaultdict

def solution(id_list, report, k):
    answer = []

    report_p = defaultdict(list)   # {신고자: [신고한 사람들]}
    reported_n = defaultdict(int)  # {신고당한 사람: 신고당한 횟수}

    # 중복 신고 제거
    real_report = list(Counter(report).keys())

    for i in real_report:
        user, reported = i.split(" ")
        report_p[user].append(reported)
        reported_n[reported] += 1

    # 정지된 사람
    sus_user = []
    for n, v in reported_n.items():
        if v >= k:
            sus_user.append(n)

    for name in id_list:
        singo = 0
        for _ in range(len(report_p[name])):
            if report_p[name][_] in sus_user:   # ← list에서 찾기 = O(n)
                singo += 1
        answer.append(singo)

    return answer

내가 몰랐던 점 / 보완할 점

맞긴 했는데, sus_user를 list로 만든 게 비효율이었다.
if r in sus_user 검사가 list에서는 O(n), set에서는 O(1)이다.

# 개선: sus_user를 set으로
sus_user = {n for n, v in reported_n.items() if v >= k}

for name in id_list:
    singo = 0
    for r in report_p[name]:
        if r in sus_user:        # ← set에서 찾기 = O(1)
            singo += 1
    answer.append(singo)

⇒ in list보다 in set이 훨씬 빠르다. 멤버십 검사용 모음은 무조건 set으로 만들자.

덤으로 tuple과 set의 차이도 정리했다. (set은 값만 있는 dict라고 생각하면 됨)

구분	tuple ()	set {}
순서	있음 (인덱스 O)	없음 (인덱스 X)
중복	허용	자동 제거
인덱싱	t[0] 가능	불가능
변경	불가 (immutable)	가능 (add/remove)
in 검사	O(n) 느림	O(1) 빠름
용도	묶어서 고정 전달	멤버십 검사, 중복 제거

---

✅ 마무리 — 해시 문제에서 꼭 알아야 할 것

키워드	내용	관련 문제
key 설계	변하지 않는 값(아이디)을 key로, 변하는 값(닉네임)을 value로	오픈채팅방
데이터 분리	자료구조 성격에 맞게 저장할 데이터를 명확히 분리 (dict에는 매핑, list에는 이벤트 순서)	오픈채팅방
defaultdict(int)	없는 키에 += 누적하면 일반 dict는 KeyError → defaultdict로 선언	주차 요금 계산, 신고 결과 받기
del dict[key]	처리 끝난 데이터는 지워서 "남은 것"이 의미를 갖게 (출차 안 한 차량, 가짓수 계산)	주차 요금 계산, 롤케이크 자르기
dict 정렬	sorted(dict) = key 기준 오름차순 key 리스트 / 내림차순 reverse=True / 값 기준 sorted(dict.items(), key=lambda x: x[1])	주차 요금 계산
Counter	dict처럼 c[t] += 1 직접 접근 가능, 단 0이 되면 del로 지워야 len()이 줄어듦	롤케이크 자르기
누적 갱신 패턴	매번 전체를 다시 세지 말고(O(n²)), 한쪽에 몰빵 후 하나씩 넘기며 차분만 갱신(O(n))	롤케이크 자르기
in set = O(1)	멤버십 검사는 list(O(n))가 아니라 set(O(1))으로	신고 결과 받기
set vs tuple	set: 순서X·중복제거·in 빠름 / tuple: 순서O·불변·in 느림	신고 결과 받기
중복 제거	set() 또는 Counter().keys()로 중복 신고/입력 제거	신고 결과 받기