코딩테스트 문제풀이

문제풀이

1번째 문제

백준 1920 수찾기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

예제 입력 1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1
1
1
0
0
1

풀이:

def binary_search(array, target, start, end):
  while start<=end:
    mid = (start+end) //2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid -1
    else:
      start = mid +1
  return None
#input data 입력
n = int(input())
array = list(map(int, input().split()))
array.sort()
m = int(input())
x = list(map(int, input().split()))
#
for i in x:
  result = binary_search(array, i, 0, n-1)
  if result == None:
    print(0)
  else:
    print(1)

이진탐색 문제로 먼저 이진탐색을 실행하는 함수를 작성한다. while문을 통해서 내가 찾는 target이 배열의 가운데 지점과 동일하다면 가운데 지점을 리턴하고 배열의 가운데 지점의 값보다 작다면 시작점을 가운데 보다 +1 한 상태에서 다시 while문이 작동하고 그 반대의 경우 끝지점이 mid 지점의 -1인 상태에서 while문이 돌아가고 만약 아무것도 없을 시 None을 리턴한다.

만약 result가 아무것도 없다면 0을 프린트 해주고 그게 아닌 mid값이 존재한다면 1을 리턴해 주는 것이다.

2번째 문제

10816 숫자카드 2

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

예제 입력 1
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1
3 0 0 1 2 0 0 2

from sys import stdin
n = int(stdin.readline())
array = list(map(int,stdin.readline().split()))
m = int(stdin.readline())
x = list(map(int, stdin.readline().split()))
# 중복 확인 
count = {}
for i in array:
    try: count[i] += 1
    except: count[i]=1
# i가 count에 들어 있는지 확인하기
for i in x:
  if i in count:
    print(count[i], end=' ')
  else:
    print(0, end=' ')

try except를 이용해서 첫번째 array에 들어간 숫자의 중복을 파악해서 dict 형태로 갯수 파악을 했다. 그 다음 for문을 사용해서 x의 원소가 count에 들어가 있다면 count의 value를 없다면 0을 입력하도록 했다.

3번째 문제

2805 문제: 나무 자르기

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

예제 입력 1
4 7
20 15 10 17

예제 출력 1
15

n,k = map(int, input().split())
array = list(map(int, input().split()))
# 시작점과 끝점 구하기
start = 0
end = max(array)
# 잘라낸 값이 k값과 일치시킬때까지 반복
result = 0
while(start <=end):
  total = 0
  mid = (start+end) //2 
  for i in array:
    if i>mid:
      total += i-mid
  if total <k:
    end = mid -1
  else:
    result = mid
    start = mid+1
print(result)

입력값을 받은 후 시작점과 끝점을 정한다. 가장 긴 나뭇가지의 값을 끝값으로 정하고 시작점은 0으로 정한다. 그 후 while문을 통해서 시작점과 끝점이 동일할때까지 반복을 한다. 중간지점을 구하고 만약 array의 원소의 값이 중간값보다 크다면 자른 후 total에 더해주고 total 값과 k 값을 비교해서 만약 길이가 짧다면 더 왼쪽을 잘라주고 그게 아니라면 오른쪽으로 다시 중심값을 잡아주면서 k값과 동일하게 하도록 한다.