알고리즘의 정석 - 실력 테스트

문자열 뒤집기

문자열이 주어질 때, 이 문자열을 뒤집어서 출력하는 프로그램을 작성하시오. 단, 재귀호출을 이용하여 구현한다.

• 입력 예시

Elice is so coooool

• 출력 예시

loooooc os si ecilE

def get_reverse(myString, cnt):
    if cnt == len(myString):
        return ''
        
    return get_reverse(myString, cnt+1) + myString[cnt]

def stringReverse(myString) :
    '''
    문자열 myString을 뒤집어서 반환하는 함수를 작성하세요.
    ''' 
    
    return get_reverse(myString, 0)

def main():
    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    myString = input()

    print(stringReverse(myString))
if __name__ == "__main__":
    main()

약수의 개수 구하기

숫자 nn의 약수의 개수를 구하는 프로그램을 작성하시오.

• 입력 예시

12

• 출력 예시

6

• 문제 조건

  • 1 ≤ n ≤ 100,000

def numDivisor(n):
    '''
    n의 약수의 개수를 반환하는 함수를 작성하세요.
    '''
    
    cnt = 0
    

    
    for i in range(1, int(n**(1/2))+1):
        print(n, i)
        if n % i == 0:
            if n / i != i :
                cnt += 2
            else:
                cnt += 1

    return cnt

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    number = int(input())
    print(numDivisor(number))

if __name__ == "__main__":
    main()

부분 문자열 개수 세기

두 문자열 A, B가 주어질 때 B가 A에 포함되어 있는 횟수를 출력하는 프로그램을 작성하시오. 예를 들어, A = “abcab” 이고 B = “ab” 이면, B는 A에 2번 포함되어 있다.

• 입력 예시 1

abcab
ab

• 출력 예시 1

2

• 입력 예시 2

aaaaa
aa

• 출력 예시 2

4

• 문제 조건

  • 각 문자열의 길이는 1000을 넘지 않는다.

import sys

def numSubstr(A, B) :
    '''
    B가 A에 포함되어 있는 횟수를 반환하는 함수를 작성하세요.
    '''
    cnt = 0
    
    for i in range(len(A)-len(B)+1):
        check = True
        for j in range(len(B)):
            if A[i+j] != B[j]:
                check = False
                break
        if check:
            cnt+=1

    return cnt

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    A = input()
    B = input()

    print(numSubstr(A, B))

if __name__ == "__main__":
    main()

색종이 만들기

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

첫째줄에 잘라진 하얀색 색종이의 개수를, 둘째줄에 잘라진 파란색 색종이의 개수를 출력해 봅시다.

• 입력 예시

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1 
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

• 출력 예시

9
7

• 문제 조건

  • N은 2, 4, 8, 16, 32, 64, 128 중 하나이다.

import sys

def cut_Paper(myMap,w_and_b,r_start, r_end, c_start, c_end):
    white = False
    blue = False
    check = False
    for i in range(r_start, r_end):
        for j in range(c_start, c_end):
            if myMap[i][j] == 1:
                blue = True
            if myMap[i][j] == 0:
                white = True
            if blue and white:
                check = True
                break
        if check:
            break
    if check:
        r_mid = (r_start+r_end)//2
        c_mid = (c_start+c_end)//2
        cut_Paper(myMap, w_and_b, r_start, r_mid, c_start, c_mid)
        cut_Paper(myMap, w_and_b, r_start, r_mid, c_mid, c_end)
        cut_Paper(myMap, w_and_b, r_mid, r_end, c_start, c_mid)
        cut_Paper(myMap, w_and_b, r_mid, r_end, c_mid, c_end)
    else:
        if white:
            w_and_b[0] +=1
            return
        if blue:
            w_and_b[1] +=1
            return

def getPaperCount(myMap) :
    '''
    n x n 의 색종이가 주어질 때, 하얀색 색종이의 개수와 파란색 색종이의 개수를 tuple로 반환하는 함수를 작성하세요.
    '''
    
    w_and_b = [0 for i in range(2)]
    
    cut_Paper(myMap,w_and_b,0, len(myMap),0, len(myMap))
    
    print(w_and_b)
    
    whiteCnt = w_and_b[0]
    blueCnt = w_and_b[1]
    
    return (whiteCnt, blueCnt)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())

    myMap = []
    for i in range(n) :
        myMap.append([int(x) for x in input().split()])

    retValue = getPaperCount(myMap)

    print(retValue[0])
    print(retValue[1])

if __name__ == "__main__":
    main()

회의실 준비 (Big)

엘리스씨는 보다 더 나은 서비스를 제공하기 위하여 정기적인 회의를 하는 것을 선호하는 편이다. 여기서 엘리스씨의 역할은 n개의 회의가 언제 시작하는지, 그리고 언제 끝나는지를 모두 모으고, 그 이후 각 회의가 어느 장소에서 이루어져야 하는지를 정한다. 각 회의가 시작하는 시간, 그리고 끝나는 시간은 초단위로 주어진다고 하자. 예를 들어, 하나의 회의는 10초에 시작하여 99초에 끝날 수 있다.

당연하게도, 두 개의 회의가 시간이 겹칠 경우에는 같은 회의실을 사용할 수 없다. 또한, 만약 정확히 10초에 끝나는 회의가 있고, 또 다른 회의가 정확히 10초에 시작한다면, 이 두 회의는 같은 회의실을 사용할 수 있다.

회의실을 빌리는 데에는 돈이 들기 때문에, 엘리스씨는 가능한한 적은 수의 회의실을 준비하고자 한다. n개의 회의에 대한 정보가 주어질 때, 모든 회의가 이루어지기 위하여 빌려야 하는 회의실의 최소 개수를 출력하는 프로그램을 작성하시오.

• 입력 첫째 줄에 회의실의 개수 n이 주어진다. (1≤n≤100,000) 이후 각 회의에 대하여 회의가 시작하는 시간, 그리고 끝나는 시간이 주어진다. 이 시간은 정수로 주어진다.

• 출력 엘리스씨가 예약을 해야 하는 최소 회의실의 개수를 출력한다.

• 입력 예시 1

4
1 4
3 5
2 7
4 6

• 출력 예시 1

3

import sys
from heapq

def reservation(meetingList) :
    '''
    회의 일정이 list로 주어질 때, 엘리스씨가 준비해야 하는 회의실의 수의 최솟값을 반환하는 함수를 작성하세요.

    각 일정은 tuple로 주어진다. 예를 들어, 주어진 입력의 경우 다음과 같이 저장된다.

    meetingList[0] = (1, 4)
    meetingList[1] = (3, 5)
    meetingList[2] = (2, 7)
    meetingList[3] = (4, 6)
    '''

    meetingList.sort()
    arr = []
    result = 0

    for meet in meetingList :

        while len(arr) >= 1 :
            front = arr[0]

            if front <= meet[0] :
                heapq.heappop(arr)
            else :
                break

        heapq.heappush(arr, meet[1])
        result = max(result, len(arr))

    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())
    meetingList = []

    for i in range(n) :
        data = [int(x) for x in input().split()]
        meetingList.append( (data[0], data[1]) )

    print(reservation(meetingList))

if __name__ == "__main__":
    main()