오늘도 지금까지 풀은 백준 문제를 정리하며 복습하도록 하겠다.
최근에는 대부분 실버 3이나 4의 문제를 풀고 있다.

1051번: 숫자 정사각형 - 실버 Ⅲ

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

나의 코드

#1051번 - 실버 3
import sys
n, m = map(int, sys.stdin.readline().split())
li = [[0]*m for _ in range(n)]
for i in range(n):
    num = sys.stdin.readline()
    for k in range(m):
        number = int(num[k])
        li[i][k] = number

sq = min(n, m)
len_list = [0]
for i in range(n):
    for k in range(m):
        len = 0
        for _ in range(sq-1):
            len += 1
            if((i+len) > (n-1) or (k+len) > (m-1)):
                break
            if(li[i][k] == li[i][k+len] == li[i+len][k] == li[i+len][k+len]):
                len_list.append(len)

print((max(len_list)+1)*(max(len_list)+1))

해설

먼저 처음에 가로와 세로의 길이 n과 m을 받아서 [0]으로 차있는 2차원 배열 li를 생성하였다.
그리고 문제에서 받은 모양 그대로 2차원 숫자 배열을 만들었다.

배열 안에서 만들어질 수 있는 정사각형의 변의 길이는 가로와 세로값 중 더 작은 값보다 클 수 없기 때문에 최대 변의 길이를 sq로 min(n, m) 을 이용해 받았다.

이후에는 배열을 돌며 정사각형을 탐색한다.

if((i+len) > (n-1) or (k+len) > (m-1)):
                break

만약 탐색하려는 정사각형이 배열의 크기를 초과한다면 break으로 빠져나가 다음 숫자를 탐색한다.

if(li[i][k] == li[i][k+len] == li[i+len][k] == li[i+len][k+len]):
                len_list.append(len)

len의 길이만큼 떨어져 있는 배열의 꼭짓점 요소의 숫자가 모두 같다면 정사각형을 찾은 것이다.
정사각형 변의 길이를 len_list 에 추가해 놓는다.
정사각형이 여러 개 나올 수 있어서 리스트에 넣어 두었다.

마지막에는 정사각형의 최대 넓이를 출력해야 하므로 최대 길이를 제곱하여 출력하였다.
인덱스로 2칸 차이날 때 변의 길이가 3이 되야 하므로 각각 +1을 해주었다.

1064번: 평행사변형 - 실버 Ⅳ

문제

평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC)
이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나올 수도 있다.
만들어진 모든 사각형 중 가장 큰 둘레 길이와 가장 작은 둘레 길이의 차이를 출력하는 프로그램을 작성하시오. 만약 만들 수 있는 평행사변형이 없다면 -1을 출력한다.

나의 코드

# 1064번 - 실버 4
import sys
import math

xy = list(map(int, sys.stdin.readline().split()))
if (xy[2] - xy[0]) == 0 and (xy[4] - xy[2]) == 0:
    m1 = 0
    m2 = 0
elif (xy[2] - xy[0]) == 0 or (xy[4] - xy[2]) == 0:
    m1 = 0
    m2 = 1
else:
    m1 = (xy[3] - xy[1]) / (xy[2] - xy[0])
    m2 = (xy[5] - xy[3]) / (xy[4] - xy[2])

if m1 == m2:
    print(-1.0)
else: #제곱근 사용
    l1 = math.sqrt((xy[2] - xy[0]) ** 2 + (xy[3] - xy[1]) ** 2)
    l2 = math.sqrt((xy[4] - xy[2]) ** 2 + (xy[5] - xy[3]) ** 2)
    l3 = math.sqrt((xy[4] - xy[0]) ** 2 + (xy[5] - xy[1]) ** 2)
    len1 = l1 * 2 + l2 * 2
    len2 = l2 * 2 + l3 * 2
    len3 = l1 * 2 + l3 * 2
    len_list = [len1, len2, len3]
    print(max(len_list) - min(len_list))

해설

이 문제는 조금 생각을 먼저 해보면 간단한 방법이 나온다.
처음에 점이 3개 주어졌을 때 각 두 점 사이로 4번째 점을 찍는 경우에 만들어질 수 있는 평행사변형은 총 3가지이다.
처음에 주어진 세 점의 거리가 각각 a, b, c라고 했을 때, 만들어지는 3가지 평행사변형은 모두 a, b, c중 하나로 이루어져 있었다. 그래서 둘레를 구하기 위해 4번째 점의 위치를 찾을 필요는 없고, 기존의 a, b, c 변의 길이만 계산하면 된다.

세 점의 위치 리스트를 모두 한 xy 리스트에 (x1, y1, x2, y2, x3, y3) 순서로 남았다.
만약에 세 점이 모두 한 직선 위에 있다면 평행사변형이 생길 수 없다.
그래서 기울기 m1, m2를 확인해 이를 확인한다.

만약 기울기가 y축 방향으로 같은 경우 기울기가 나올 수 없다.
그래서 x의 차가 모두 0인 경우에는 m1, m2에 같은 값을 대입하였다.

또한 나중에 m1의 기울기를 구하기 위해 xy[2] - xy[0] 값으로 나눠줘야 하는데 나눠주는 값이 0이 되면 안되므로 둘 중 한 값이 0인 경우에는 m1, m2에 미리 다른 값을 대입해 주었다.

나머지의 경우는 원래대로 y의 차를 x의 차로 나누어 기울기를 구해주었다.

이후에는, 기울기가 다르다면, 평행사변형이 성립되는 것이므로 각각의 길이를 구해준다.
math 모듈의 math.sqrt 함수를 사용해서 제곱근의 값을 구하였다.
파이썬에서 제곱의 표시는 **2 이다.

그리고 둘레를 각각 구해서 최댓값에서 최솟값을 출력한다.

1026번: 보물 - 실버 Ⅳ

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

나의 코드

#1026번 - 실버 4
import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
s = 0
a.sort()
a.reverse()
b.sort()
for i in range(n):
    s = s + a[i]*b[i]
print(s)

해설

이 문제는 A 배열과 B 배열을 모두 정렬하여 큰 값에는 작은 값을 곱해주면 S의 최솟값이 나오는 간단한 문제이다.

A 배열은 sort() 함수로 정렬을 한 후에, reverse() 함수로 뒤집어 주었다.
최댓값 -> 최솟값 순으로 가는 리스트로 변한 것이다.
B 배열은 sort() 함수로 정렬만 해주었다.
이렇게 정렬된 A 배열과 B 배열을 원소별로 곱해주면 최솟값 S가 나온다.

1590번: 캠프가는 영식 - 실버 Ⅳ

문제

영식이는 민식이와 함게 고속버스를 타고 캠프를 가야 하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.
영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 시각이 특점 시점을 기준으로 10분 후이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.
영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 기다려야 하는지 구하는 프로그램을 작성하시오.

나의 코드

#1590번 - 실버 4
import sys
n, t = map(int, sys.stdin.readline().split())
start = []
inter = []
count = []
for i in range(n):
    s, i, c = map(int, sys.stdin.readline().split())
    start.append(s)
    inter.append(i)
    count.append(c)

wait = []
for i in range(n):
    if(t > start[i] + inter[i]*(count[i]-1)):
        continue
    for _ in range(count[i]):
        if(t <= start[i]):
            wait.append(start[i] - t)
            break
        start[i] += inter[i]
if not wait: #리스트가 비어 있는 경우 not 사용
    print(-1)
else:
    print(min(wait))

해설

이 문제에서는 버스가 여러 대가 나올 수 있기 때문에 각 버스의 시작 시각, 간격, 대수를
start, inter, count 리스트를 이용해서 받았다.

이제 버스별로 기다릴 최솟값을 wait 리스트에 담았다.

if(t > start[i] + inter[i]*(count[i]-1)):
        continue

for 문을 돌 때 마지막 버스가 도착할 때 이후에 영식이가 도착한다면 어차피 버스를 타지 못하니 바로 다음 버스 검사로 넘어가도록 코드를 작성해 주었다.

이후에는 버스 시작점부터 돌기 시작해서 inter 값을 한 개씩 증가시키며 버스 도착 시작이 영식이가 도착하는 시간 이후에 오는 순간 기다린 시간을 계산하여 wait 리스트에 집어 넣고 break 문으로 빠져나와 다음 버스 검사로 넘어간다.

마지막에는 만약 n개의 버스를 모두 놓쳐서 모두 타지 못하는 경우에는 not 을 사용하여 리스트가 비어있는지 확인하고, -1을 출력한다.
그게 아니라면 n개의 버스별로 기다리는 시간이 들어있는 wait 리스트 중에 최솟값을 출력한다.

2751번: 수 정렬하기 2 - 실버 Ⅴ

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

나의 코드

이 문제는 아주 간단한 문제인데 정수를 입력받는 곳에서 시간초과 때문에 고생한 문제이다.

처음에는 int(input()) 함수를 이용해 정수를 입력받아서 시간초과가 났다.
나는 sort() 정렬 때문에 시간 초과가 나는 줄 알고 여러가지 정렬 방법을 시도해 봤었다.

# O(n)이 커서 힙 정렬으로
# 이것도 시간 초과임..
import heapq

n = int(input())
list = []
for _ in range(n):
    i = int(input())
    list.append(i) # 여기까진 위와 동일

heapq.heapify(list)
nlist=[]

while list:
    nlist.append(heapq.heappop(list))

for i in nlist:
    print(i)

그래서 heapq 을 이용해 힙 정렬을 해봤는데, 이것도 시간초과였다.
그래서 계속 검색을 하다보니 input() 함수가 시간을 많이 잡아먹는다는 것을 알게 되었다.

#2751번 - 실버 5
#시간초과 -> 해결
import sys

n = int(input())
list = []
for _ in range(n):
    list.append(int(sys.stdin.readline())) 
    #정수를 입력받는데서 시간초과였다. sort가 문제가 아녔다. input()를 sys 모듈로 입력받는 것으로 바꿔줌

list.sort()
for i in list:
    print(i)

해설

그래서 이후에는 sys 모듈을 이용해서 sys.stdin.readline() 함수를 사용하니 시간 초과 문제가 간단히 해결됐다.
이 문제를 푼 이후부터는 입력을 받을 때 sys 모듈을 주로 이용하게 된 것 같다.