꾸준히 문제 풀기 - 9월 3주차

9/11. 나이순 정렬 (백준 10814번)

 

https://www.acmicpc.net/problem/10814

 

#python

from sys import stdin

n = int(stdin.readline())
data = []

for i in range(0, n):
    num, name = map(str, stdin.readline().split())
    
    data.append([])
    data[i].append(int(num))
    data[i].append(name)

data.sort(key=lambda x:x[0])

for i in range(0, n):
    print(data[i][0], data[i][1], sep=" ")

 

처음에는 딕셔너리로 데이터를 받고 딕셔너리 정렬을 해서 풀려고 했다. data[나이] = 이름 이런 식으로 했는데 생각해보니까 이렇게 하면 나이가 중복되는 경우에 문제가 생기므로 안 된다. 그래서 막 이것저것 수정해봤지만 해결이 안 되어서 이차원 리스트 정렬을 통해서 풀기로 했다. lst.sort(key=lambda x:x[0]) 이렇게 하면 0번째 인덱스에 대해서 정렬된다. 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬해야 하는데, 혹시나 섞일까봐 걱정했지만 다행히 그렇지는 않았다. 혹시 섞인다면 들어온 순서를 세번째 인덱스에 넣고 lst.sort(key=lambda x: (x[0], x[2])) 이렇게 하면 될 것 같다. (정답)

[참고] https://haesoo9410.tistory.com/193

 

---

 

9/11. 수 찾기 (백준 1920번)

 

https://www.acmicpc.net/problem/1920

 

#python

from sys import stdin

def binary_search(target, data, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
    
    return binary_search(target, data, start, end)

n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
num = list(map(int, stdin.readline().split()))

a.sort()

for i in range(0, m):
    if binary_search(num[i], a, 0, n-1) == None:
        print(0)
    else:
        print(1)

 

드디어 내가 그렇게 공부해서 써먹고 싶었던!! 이진 탐색 문제가 나왔다 흐흐 (정답)

 

---

 

9/12. 수 정렬하기 3 (백준 10989번)

 

https://www.acmicpc.net/problem/10989

 

#python

from sys import stdin

n = int(stdin.readline())
count = [0] * 10000

for i in range(0, n):
    num = int(stdin.readline())
    count[num-1] += 1

for i in range(0, 10000):
    for j in range(0, count[i]):
        print(i+1)

 

예전에 풀었다가 틀린 문제였다. 당연하게 n개의 수를 리스트로 입력받아 정렬하고 출력했던 것 같은데 메모리 초과로 틀렸던 것 같다. 찾아보니 메모리가 엄청 작은 편에 속하는 문제라고 한다. 어차피 수의 범위는 10000이하이므로, 길이가 10000인 리스트를 미리 만들어 0으로 채워넣고 1씩 추가하는 방법으로 풀었다. (정답)

 

---

 

9/15. 분해합 (백준 2231번)

 

https://www.acmicpc.net/problem/2231

 

#python

from sys import stdin

n = int(stdin.readline())

for m in range(1, n+1):
    sum = m
    temp = m

    while temp != 0:
        sum += temp % 10
        temp //= 10
    
    if sum == n:
        print(m)
        break
    
    if m == n:
        print(0)

 

역시나 브루트포스 알고리즘 문제. 처음에는 큰 수부터 차례로 확인하는 방식으로 했는데, 생각해보니 생성자가 여러개일 경우에는 가장 작은 생성자를 출력해야 하므로 작은 수부터 차례로 확인하는 방식으로 바꿨다. 그리고 생성자가 없는 경우는 m을 계속 늘리다가 n과 같아졌을 때 0을 출력하도록 했다. (정답)