코딩 테스트 벼락치기(?) - Day3

Day 3 (백준):

1. 1157번 (문자열)
2. 2750번 (정렬)
3. 10989번 (정렬)
4. 1620번 (해시맵)
5. 7568번 (브루트포스)

오늘거 레전드로 재미없다 백준 진짜 UI구림

---

백준 1157(문자열)

import sys

def solution():
    #전부 대문자로 바꿔버리기
    s = sys.stdin.readline().strip().upper()
    #set으로 중복 피하기
    unique_s = list(set(s))
    
    counts = []
   
    for char in unique_s:
        cnt = s.count(char)
        counts.append(cnt) #알파벳 빈도수 저장
        
    max_cnt = max(counts) #빈도수 가장 많은 것중에 최대가 뭐야?
    
    #2이상이면 ? 출력(빈도수 같은 게 2개 이상이면)
    if counts.count(max_cnt) > 1:
        print("?")
    else:
        #최댓값 자리 있는 인덱스 자리 찾아야지?
        max_index = counts.index(max_cnt)
        #인덱스에 해당하는 알파벳 출력
        print(unique_s[max_index])
        
solution()

---

백준 2750(정렬)

import sys

# 1. 숫자의 개수 입력 받기
n = int(sys.stdin.readline())

# 2. n개의 숫자를 입력받아 리스트에 저장 (정수로 변환 필수!)
numbers = []
for _ in range(n):
    numbers.append(int(sys.stdin.readline()))

# 3. 오름차순 정렬
numbers.sort()

# 4. 하나씩 출력
for num in numbers:
    print(num)

---

백준 10989 정렬

import sys

# 1. 숫자의 개수 입력 받기
n = int(sys.stdin.readline())

# 2. 숫자의 범위(1~10,000)만큼 빈 리스트 생성 (메모리 아끼기)
count_list = [0] * 10001

# 3. 숫자를 리스트에 담지 않고, 개수만 세기
for _ in range(n):
    num = int(sys.stdin.readline())
    count_list[num] += 1

# 4. 리스트를 돌며 개수만큼 출력하기
for i in range(10001):
    if count_list[i] != 0:
        # 해당 숫자가 나온 횟수만큼 반복 출력
        for _ in range(count_list[i]):
            print(i)

---

백준 1620(해시맵)

import sys

n,m = map(int, sys.stdin.readline().split()) 

# 2. 도감 만들기 (두 가지 버전)
name_to_id = {}
id_to_name = {}

for i in range(1, n+1):
    name = sys.stdin.readline().strip()
    name_to_id[name] = i
    id_to_name[i] = name

for _ in range(m):
    query = sys.stdin.readline().strip()
    if query.isdigit():
        print(id_to_name[int(query)])
    else:
        print(name_to_id[query])

---

백준 7568(브루트포스)

import sys

# 1. 사람 수 N 입력 받기
n = int(sys.stdin.readline())
people = []

# 2. 몸무게와 키를 튜플로 묶어서 리스트에 저장
for _ in range(n):
    w, h = map(int, sys.stdin.readline().split())
    people.append((w, h))

# 3. 한 명씩 주인공(i)이 되어 다른 모든 사람(j)과 비교
for i in range(n):
    rank = 1 # 등수는 1등부터 시작
    for j in range(n):
        # i번 사람보다 j번 사람이 몸무게도 크고 키도 큰가?
        if people[i][0] < people[j][0] and people[i][1] < people[j][1]:
            rank += 1
    
    # 4. 결과 출력 (한 칸씩 띄워서)
    print(rank, end=' ')

---

오늘 가져갈 것

1. 문자열 빈도수 (1157번 - 단어 공부)
   가져갈 것: set()으로 중복 제거하기 & count() 활용.

존재하는 종류(set)만 골라서 시간 단축.

2. 메모리 관리의 반전 (10989번 - 수 정렬하기 3)
   가져갈 것: 계수 정렬(Counting Sort).

데이터를 다 저장하지 않아도 정렬할 수 있음.
메모리 제한이 8MB처럼 극단적으로 낮을 땐 append() 대신 미리 칸을 만들어두고(리스트 초기화) 숫자만 세기

3. 양방향 초고속 검색 (1620번 - 나는야 포켓몬 마스터)
   가져갈 것: 딕셔너리(Hash Map) & isdigit().

리스트에서 index()로 찾으면 한참 걸리지만, 딕셔너리({})는 데이터가 10만 개든 100만 개든 찾음.

4. 전수 조사 (7568번 - 덩치)
   가져갈 것: 브루트 포스(Brute Force) & 2차원 리스트 인덱싱.

복잡한 정렬 알고리즘보다 가끔은 "모두 다 비교하기"가 나을 때가 있음. people[i][0] 처럼 2차원 리스트의 방 번호를 정확히 찍어서 비교.

꾸준히 합시다. 언젠가는 높은 레벨도 척척 풀겠지.