제로베이스 20220411 코테 연습

1. 좌표 정렬하기

• 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.
• 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

• 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

풀이

import sys
import heapq

N = int(sys.stdin.readline())

arr = []

for _ in range(0, N):
    x, y = list(map(int, sys.stdin.readline().split()))
    arr.append((x, y))

heapq.heapify(arr)

while arr:
    x, y = heapq.heappop(arr)
    print(x, y)

채점 결과

• 정답

리뷰

• 이러니 저러니 해도 결국 조건 두개 달린 정렬 문제로 해석할수 있고, 이런 문제는 힙 정렬을 쓰면 간편하게 풀리는 느낌이 있어 실행했다.

• 힙 정렬은 최악의 경우라도 O(NlogN)의 시간복잡도는 보증해주므로, 정렬 문제에서는 좋은 선택이라고 생각한다.

더 나은 풀이

• 풀이 출처 : 아이디 satirev12님의 풀이

import sys
def thres(e):
    x, y = e.split()
    return int(x) + int(y)/1000000
input = sys.stdin.readline
print = sys.stdout.write
l = sys.stdin.readlines()[1:]
l = sorted(l, key=lambda x: thres(x))
print(''.join(l))

더 나은 풀이법 리뷰

• 기본 내장 함수인 sorted를 사용했다.
  • 생각해보니 이걸 쓰면 힙 만들고 heapify할 필요 없이 더 빨리 되는것인데, 저번에 힙 관련해서 고생하다보니 저절로 힙부터 떠오른것이 내 판단 착오였다.
• x값이 같을때 y값이 증가하는 순서대로 정렬하므로, y값을 x값에 영향을 거의 주지 못할정도로 작은값으로 만들어 더해준다는 아이디어가 핵심이다.

2. 수 정렬하기 2

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

입력

• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다.
• 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이

import sys
import heapq

N = int(sys.stdin.readline())

arr = []

for _ in range(0, N):
    arr.append(int(sys.stdin.readline()))

heapq.heapify(arr)

for _ in range(0,N):
    print(heapq.heappop(arr))

채점 결과

• 정답

리뷰

• 1번과 마찬가지로, 그냥 sorted 쓰면 될 문제를 굳이 힙까지 끌고와서 느리게 풀었다.

  • 더 나은 풀이는 블로그 글을 작성할때 보고 추가하는 방식이라서, 이때도 그냥 힙 정렬이면 만족스러운 해법이다 하고 넘어갔다.

더 나은 풀이

• 풀이 출처 : 아이디 lambda님의 풀이

def sol():
    a=[None]*2000001
    b=map(int,open(0))
    next(b)
    for i in b:a[i]=1
    print("\n".join(str(i) for i in range(-1000000,1000001,1) if a[i]))

sol()

더 나은 풀이 리뷰

• sys 라이브러리를 불러오는 시간조차 아까웠는지, open()함수로 입력값을 받았다.

• 입력받은 객체는 map함수에 의해 int형으로 바뀌어 저장되었다.

• next(b)에 의해 반복하는 횟수를 의미하는 첫번째줄은 넘어간다.

• 한줄로 써놔서 헷갈렸는데, b의 내용물 i에 대해 a[i]를 1로 변경한다는 내용이었다.

  • a 배열은 None으로 초기화 되었으므로, 입력된 인덱스의 값을 제외하면 전부 None값이 되는 셈이다.

• a[i]값이 존재할 경우, 해당 인덱스를 문자열로 바꾸어 한줄씩 출력하는것으로 마무리했다.

• 배열 안의 값을 검사하는것이 오래 걸릴줄 알았는데 시간은 가장 짧게 걸린것$^1$으로 보아 생각보다 None/ not None의 검사는 빠르게 진행되는것 같았다.

1. 보통 더 나은 풀이를 가져올때 삼는 기준은 Python으로 푼 문제중 가장 시간이 짧게 걸린 문제를 채택하는 방식이다.
   • 따라서, 해당 문제를 푼 방법중에는 이 방법이 가장 빨리 푸는 방법이라는 뜻.

3. 나이순 정렬

• 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다.

• 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

• 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

• 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다.
• 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다.
• 입력은 가입한 순서로 주어진다.

출력

• 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

풀이

import sys
import heapq

N = int(sys.stdin.readline())

arr = []
age_dic = {}

for _ in range(0, N):
    age, name = list(sys.stdin.readline().split())
    age = int(age)

    if age not in age_dic.keys():
        age_dic[age] = 0
    else:
        age_dic[age] += 1
    cnt = age_dic[age]
    arr.append((age, (cnt, name)))

heapq.heapify(arr)

while arr:
    age, name = heapq.heappop(arr)
    print(age, name[1])

채점 결과

• 정답

리뷰

• 오늘 푼 문제중 절반 가까이를 힙으로 푼거같은 느낌이지만, 이 문제는 진짜 힙으로 푸는것이 맞다고 판단했다.

• 판단 근거는 다음과 같았다.
  1. 정렬해야하는 기준이 두가지였다.
  2. 입력해야할 값이 사실상 세가지(나이, 입력받은 순서, 이름)였기에 튜플 사용해서 묶어주고싶은 마음이 있었다.

• 한번이라도 나온 나이는 age_dic이라는 dict에 넣어 해당 나이의 사람중 몇번째 사람인지 cnt로 표기할수 있도록 했다.

• 나머지는 늘 그렇듯, 힙정렬 실시.

더 나은 풀이

• 풀이 출처 : 아이디 lens0021님의 풀이

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

from sys import stdin, stdout

users_by_age = [[] for _ in range(200+1)]

for line in stdin.read().splitlines(True)[1:]:
    users_by_age[int(line.split()[0])].append(line)

stdout.write(''.join(
    ''.join(u)
    for u in
    users_by_age
))

더 나은 풀이 리뷰

• 입출력 단계에서의 빠름을 위해 stdin뿐 아니라 stdout까지 사용했다.

• 나이는 1~200사이라고 정해져 있으므로 해당 범위에 맞춰 리스트를 초기화 시킨다.

• 들어온 입력에 대해 첫번째 값(입력값 개수)는 넘겨주고, users_by_age에 나이를 인덱스로 주어 입력받은 라인 전체를 append했다.
  • 이렇게하면 나이를 인덱스로 참조했을때, append된 순서대로 이름이 출력될것이다.
  • dictionary를 안쓰고도 비슷한 효과가 나올수 있음에 놀랐다.
• users_by_age를 탐색하며 있는 값들을 하나씩 출력해주면 끝.

3. 이항 계수

• ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다.
• 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다.
• 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다.
  • 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.
• 문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자.
• 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99).
• 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다.
• 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다.

• 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

• 방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다.

• 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.

• 손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다.
  • 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다.
  • 같은 이유로 102 호보다 2101 호를 더 선호한다.
• 여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다.
• 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다.

입력

• 프로그램은 표준 입력에서 입력 데이터를 받는다.
• 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다.
• 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W).

출력

• 프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.

풀이

import sys

T = int(sys.stdin.readline())

for _ in range(0, T):
    H, W, N = list(map(int, sys.stdin.readline().split()))

    if W > 9:
        room_arr = ['0' + str(x) for x in range(1, 10)] + [str(x) for x in range(10, W + 1)]
    else:
        room_arr = ['0' + str(x) for x in range(1, W + 1)]

    stair_arr = [str(x) for x in range(1, H + 1)]
    room = room_arr[(N - 1) // H]
    stair = stair_arr[N % H - 1]

    print(stair+room)

채점 결과

• 정답

리뷰

• 말이 겁나 복잡하게 서술되어 있는데 짧게 요약하면 세로 첫줄채우고, 둘째줄 채우고..를 반복하면서 손님을 채워넣는 프로그램을 작성하시오와 크게 다른소리는 아니다.

  • 각 층의 1호실을 전부 채운후에 1층의 2호실부터 다시 채우고..를 반복하는 문제이다.

• 각 층 1호실을 전부 채운후 2호실로 넘어간다 => 방 번호는 (손님 수-1) // (층 높이)

• 층수는 ((손님수) % (층 높이)) - 1

• 두개를 문자열로 바꿔 더해주면 끝.

더 나은 풀이

• 아이디 byran1302님의 풀이

import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    h,w,n = map(int,input().split())
    print(str((n-1)%h+1) + str((n-1)//h+1).rjust(2,'0')) 

더 나은 풀이법 리뷰

• 다른건 다 같으나, rjust 함수를 통해 10의자리가 0인 경우에 ‘0’을 채워주도록 설정한 부분이 인상깊다.

• rjust(int, string), ljust(int,string)

  • 문자열의 길이가 첫번째 인자로 준 int값보다 작을 경우, 문자열의 길이에 맞도록 오른쪽,왼쪽 공백을 두번째 인자로 준 string으로 채운다.

  • ex) “12”.rjust(5,”a”)

    • “aaa12”