✅ 문제 풀이 - Programmers (이분탐색)
🎈 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있고 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다. 각 심사대에서 동시에 한 명만 심사할 수 있고 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때 모든 사람이 심사받는데 걸리는 시간의 최솟값을 리턴하는 문제
def solution(n, times):
# left, right 는 시간으로 설정 left는 최소 1분, right는 최대 걸리는 시간 저장
left = 1
right = max(times) * n
# right가 더 크다는 조건에 한해
while left < right:
# mid는 중간 값, 심사를 거친 사람 수를 people로 저장
mid = (left + right) // 2
people = 0
# 걸리는 시간에 한해 사람 수는 mid // (각 심사대에서 걸리는 시간)
for i in times:
people += mid // i
# 입국 심사 수보다 현재 사람 수가 더크면 시간을 줄일 수 있으므로 right 변경
if people >= n:
right = mid
# 시간을 더 늘려야 하므로 left 변경
else:
left = mid + 1
return left< 풀이 과정 >
전형적인 이분탐색 문제
걸리는 시간을 최소로 하는 값을 리턴해야 하므로 left, right를 최소 시간, 최대 시간으로 저장해준다.
그 이후 이분탐색을 거쳐 사람 수를 계산해주는데, mid // 각 심사대에서 걸리는 시간으로 사람 수를 구해주고, 주어진 n보다 큰 지, 작은 지 여부를 판단해가며 최종적으로 left로 값을 리턴해준다.
✅ BOJ IT 기업 문제 풀이
IT기업, 대기업 코테
누가 백준에 친절하게 정리해준 문제 풀이 모음집!
이전에 풀어본 문제들도 있지만 다시 풀어보면서 실력 점검하기 💯
🎈 23971 ZOAC 4
한 명씩 앉을 수 있는 테이블이 행마다 W개씩 H행에 걸쳐 있을 때, 모든 참가자는 세로로 N칸, 가로로 M칸이상 비우고 앉아야 한다.즉 다른 모든 참가자와 세로 줄 번호의 차가 N보다 크거나 가로줄 번호가 M보다 큰 곳에만 앉을 수 있다. 최종적으로 H,W,N,M이 주어질 때 강의실에 수용할 수 있는 최대 인원 수를 구하는 문제
import sys
input = sys.stdin.readline
import math
h, w, n, m = map(int, input().split())
height = math.ceil(h/(n+1))
width = math.ceil(w/(m+1))
print(height*width)< 풀이 과정 >
주어진 h를 n+1로 나눈 후 올림한 값은 height로, 주어진 w를 m+1로 나눈 후 올림한 값을 width로 두고 이 두 변수를 곱한 값을 리턴하면 되는 문제
🎈 5073 삼각형과 세 변
삼각형의 세 변의 길이에 따라 다음과 같이 정의한다.
- Equilateral : 세 변의 길이가 모두 같은 경우
- Isosceles : 두 변의 길이만 같은 경우
- Scalene : 세 변의 길이가 모두 다른 경우
위 조건을 만족 못하면 Invalid를 출력한다.
입출력은 다음과 같다- 입력 : 삼각형 세 변의 길이가 주어지고 마지막 줄은 0,0,0이다
- 출력 : 각 입력에 맞게 위 조건을 출력하는 문제
import sys
input = sys.stdin.readline
while True:
a, b, c = map(int, input().split())
if a == 0 and b == 0 and c == 0:
break
k = max(a, b, c)
if a == b == c:
print('Equilateral')
elif k >= (a+b+c - k):
print('Invalid')
elif a != b and b != c and c!= a:
print('Scalene')
elif (a == b and a!= c) or (b == c and c!= a) or (c == a and a != b):
print('Isosceles')< 풀이 과정 >
주어진 조건에 맞게 if 문으로 구현해주면 되는 문제
🎈 2292 벌집
육각형으로 이루어진 벌집에서 중앙은 1로 시작해 이웃하는 방에 돌아가면서 1씩 증가한다. 숫자 n이 주어질 때 중앙에서 n까지 몇개의 방을 지나가는지 계산하는 프로그램
import sys
input = sys.stdin.readline
n = int(input())
a = 1
d = 6
answer = 1
while n > a:
answer += 1
a += d
d += 6
print(answer)< 풀이 과정 >
주어진 벌집을 보면 a = 1, d = 6인 등차수열로 집 크기가 커지는 것을 알 수 있다.
이를 통해 주어진 숫자 n이 a보다 큰 while 루프를 돌며 값 변화를 해주어 최종적으로 지나가는 방 수를 구할 수 있다.
🎈 1157 단어 공부
알파벳 대소문자로 된 단어가 주어지면 이 단에서 가장 많이 사용된 알파벳을 대문자로 출력하는 문제, 가장 많이 사용된 알파벳이 여러개면 ?를 출력
import sys
input = sys.stdin.readline
alphabet = input().upper().rstrip()
word = list(set(alphabet))
li = []
for i in word:
cnt = alphabet.count(i)
li.append(cnt)
if li.count(max(li)) > 1:
print('?')
else:
maxidx = li.index(max(li))
print(word[maxidx])
< 풀이 과정 >
dic을 이용해 정리하려했으나, 값 비교과정이 쉽지 않았고 그냥 리스트로 개수를 비교하며 구현하고자 했다.
주어진 알파벳들의 중복제거한 단어를 word로 지정하고 빈 리스트에는 알파벳 별 나온 횟수를 지정해놓는다.
그 이후 알파벳 나온 횟수가 최댓값이 여러개인 경우 ?를, 1개만 있는 경우 최댓값의 인덱스를 꺼내 앞서 중복제거한 word에 해당인덱스를 집어넣어 알파벳을 빼준다.
🎈 11723 집합
s라는 빈 집합이 주어지고 m이 주어진다. 이후 m줄에 걸쳐 명령이 주어지고 s를 연산하여 해당 연산에 맞는 결과를 출력하는 문제
import sys
input = sys.stdin.readline
m = int(input())
s = set()
for i in range(m):
command = input().rstrip().split()
if len(command) == 1:
if command[0] == 'all':
s = set([i for i in range(1, 21)])
else:
s = set()
else:
comm, num = command[0], command[1]
num = int(num)
if comm == 'add':
s.add(num)
elif comm == 'remove':
s.discard(num)
elif comm == 'check':
if num in s:
print(1)
else:
print(0)
elif comm == 'toggle':
if num in s:
s.discard(num)
else:
s.add(num)< 풀이 과정 >
중요한 것은, m줄에 걸쳐 들어오는 명령이 어떤 것은 split, 아닌 경우도 있다는 것이다.
따라서 len(명령) 으로 1개인 경우는 all, empty 뿐이므로 각각 조건을 걸어 s를 연산해주고, 길이가 2인 경우 각 연산을 조건에 맞게 실행시켜주면 된다.
