[CLASS 2]백준 7568번, 10814번, 11650번, 11651번, 1920번

7568번 : 덩치

 

몸무게와 키가 모두 큰 사람이 있는 만큼 순위가 밀린다. 즉 A부터 한 사람씩 다른 모든 사람과 비교하면서 자신보다 몸무게와 키가 둘 다 큰 사람이 있다면 순위를 +1 해주면 된다.

 

내 코드:

weight = []
height = []
n = int(input())
for _ in range(n):
    w,h = map(int,input().split())
    weight.append(w)
    height.append(h)

ranks = [1] * n
for i in range(n):
    for j in range(n):
        if weight[j] > weight[i] and height[j] > height[i]:
            ranks[i] += 1

for rank in ranks:
    print(rank)

 

한 사람을 체크할 때마다 모든 사람을 다 검사해야 해서 비효율적일 수 있지만, n이 2명부터 50명으로 제한되기 때문에 충분히 사용 가능한 코드이다.

 

10814번 : 나이순 정렬

간단하게 나이순으로 출력하면 된다. 다만 주의할 점은 나이가 같다면 처음에 입력한 순서대로 출력해야 하기 때문에 나이로 정렬할 때 안정적인 정렬 알고리즘을 사용해야 할 것이다.

 

안정적인 정렬 알고리즘이란, 해당 알고리즘을 수행했을 시, 같은 key에 대해서 value의 순서가 바뀌지 않는 알고리즘을 뜻한다.

 

내 코드:

import sys
input = sys.stdin.readline
people = []
for _ in range(int(input())):
    temp = input().split()
    age = int(temp[0])
    name = temp[1]
    people.append((age,name))

people = sorted(people, key=lambda person: person[0])

for person in people:
    print(str(person[0]),str(person[1]))

 

sorted 함수와 lambda를 이용하여 person의 첫번째 요소(나이)를 기준으로 정렬하였다. 내장함수인 sorted를 이용하면 안정적인 정렬을 사용할 수 있다.

 

11650, 11651번 : 좌표 정렬하기 1, 2

 

두 문제는 거의 동일한데, 정렬 기준이 x인지 혹은 y인지만 다르다.

 

이전 문제와 비슷한 코드를 사용하면 된다. sorted + lambda

 

내 코드(11650번):

import sys
input = sys.stdin.readline
coords = [input() for _ in range(int(input()))]
coords = sorted(coords, key=lambda coord: (int(coord.split()[0]),int(coord.split()[1])))

print(''.join(coords))

 

이는 11650번의 답이고, 11651은 lambda의 split() 해서 얻은 함수의 인덱스만 서로 바꿔주면 된다.

 

1920번 : 수 찾기

 

배열 안에 해당 숫자가 존재하는지 찾는 문제이다. 처음 보고 엄청 쉽네! 라고 생각해서 다음과 같은 코드를 작성했다.

 

내 코드(시간 초과):

import sys
input = sys.stdin.readline
int(input())
numbers = tuple(map(int,input().split()))
int(input())
checkList = tuple(map(int,input().split()))
for number in checkList:
    print(int(number in numbers))

 

어디서 시간 초과가 날까.. 하고 생각해봤는데, 답은 중복숫자였다. 아마 채점 케이스에서 중복되는 숫자를 엄청 많이 줘서 탐색하는데 고의로 시간을 많이 걸리게 한 것으로 추측된다.

 

내 코드:

import sys
input = sys.stdin.readline
n,numbers,m = input(),set(input().split()),input()
for number in input().split():
    print(int(number in numbers))

 

결과적으로 이렇게 작성했다. 간단하게 set을 사용해서 집합으로 만들어 준다면 중복이 싹 사라진다. 마지막 출력은 파이썬에서 boolean 값을 int로 형변환하면 True 는 1 False는 0을 반환하므로 저렇게 사용할 수 있다.

 

number in numbers 대신 이진 탐색을 직접 구현하여 작성할 수도 있다.

 

내 코드(이진탐색):

import sys
input = sys.stdin.readline
def binarySearch(array,target,start,end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return True
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  
  return False

n,numbers,m = input(),sorted(list(set(input().split()))),input()
for number in input().split():
    print(int(binarySearch(numbers,number,0,len(numbers)-1)))

 

조금 지저분해지긴 했지만 잘 작동한다.