윤태영블로그

1236번 문제 같은 경우, 모든 행과 모든 열에 한 명 이상의 경비원이 있어야 한다고 한다.

그러면 행 기준,열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수를 출력하면 최소한의 경비원의 수가 된다.

이 문제를 풀기 위해선 행 기준 열 기준으로 비어있는 경비원을 구하기만 하면 된다.

행 기준으로 보았을 때, 만약 두 행에 대해서 경비원이 존재하지 않고,

열 기준으로 보았을 때 , 한 열에 대해서 경비원이 존재하지 않으면,

더 큰 값을 가지는 행 부분이 필요한 경비원의 수라고 할 수 있다.

n, m = map(int, input().split())
array = []

for _ in range(n):
    array.append(input())

row = [0] * n
column = [0] * m

for i in range(n):
    for j in range(m):
        if array[i][j] == 'X':
            row[i] = 1
            column[j] = 1

row_count = 0
for i in range(n):
    if row[i] == 0:
        row_count += 1

column_count = 0
for j in range(m):
    if column[j] == 0:
        column_count += 1

print(max(row_count, column_count))

여기서는 경비원이 존재하는 위치가 if array[i][j] == 'X': 로 담기게 된다.

그렇기 때문에, 각각의 행과 열에 대해 반복문을 통해서 경비원이 존재하지 않는 행에 대해 count를 증가 시킨다.

그 다음에 행,열 기준으로 각각의 count를 비교해서 더 큰값이 print(max(row_count, column_count))를 통해 필요한 최소 경비원의 수가 출력 되도록 했다.

 해당 문제는 트로피가 에제 입력 1처럼 1자로 쭉 나열되어 있을 때, 각각의 값들이 트로피의 높이라고 할 수 있다.

트로피의 높이를 왼쪽에서 보았을 때, 오른쪽에서 보았을 때 높이가 다르기 때문에 높이가 작은 트로피 큰 트로피에 가려져서 안보인다고 한다. 그래서, 왼쪽에서 보았을 때와 오른쪽에서 보았을 때 각각 보이는 개수를 출력하는 문제이다. 

이 문제는 트로피의 개수 N이 최대 50이라고 했으므로, 요구하는 대로 문제를 풀어보면 된다.

우선 3 , 4, 6, 4, 3, 7, 2 트로피가 있다고 가정 해보면 왼족에서 보았을 때, 6뒤에 4 3이 가려져서 안보이고 7뒤에 2가 가려져서 안보이기에  왼쪽에는 4,3,2를 제외한 총 4개가 보이는 것이다.

오른쪽에서 보았을 때는 7이 너무 커서 뒤에 있는 3, 4, 6, 4, 3은 전부 안보이기에 총 2개가 보이는 것이다.

def ascending(array):
    now = array[0]
    result = 1
    for i in range(1, len(array)):
        if now < array[i]:
            result += 1
            now = array[i]
    return result

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

for _ in range(n):
    array.append(int(input()))

print(ascending(array))
array.reverse()
print(ascending(array))

ascending()이란 하나의 함수를 만들었는데,  왼쪽에서 보았 을 때 트로피 갯수를 세는 함수라고 볼 수 있다.

오름차순으로 원소들만 센다.

예를 들어, 3,5,7,2,9 라는 숫자가 있으면 3,5,7 센 다음 2는 오름차순이 아니기에 건너뛰고 9를 센다.

now가 현재 보고 있는 트로피의 높이라고 할 수 있고,

결과적으로 result를 현재 보고 있는 트로피가 더 높은 트로피라면 +=1을 하는 방식으로 구현 한다. 

이 함수를 이용해서

print(ascending(array))를 통해, 왼쪽에서 보고 있는 걸 출력해두고,

array.reverse()를 통해 반대로 뒤집어서 오른쪽에서 보고 있는걸 출력 할 수 있다.

내용을 보면,가장 많이 팔린 책을 출력하면 되는 간단한 문제이다. 예를 들어 예제 입력1에서 top이 4번 나왔고,kimtop이 허1번 나왔으면, top이 가장 많이 나왔으니 top을 출력하면 되는 것이다.

이 문제는 가장 많이 등장한 문자열을 출력하는 문제이므로, 어떠한 원소를 나왔는지 안나왔는지를 구분하기 위해

set() 자료형이나  Dictionary()자료형을 이용할 수 있다. 이 문제 같은 경우, 나온 횟수를 세어야 하기 때문에 Dictionary() 자료형을 이용한다. 횟수를 계산할 때는 Dictionary()를 이용하면 효과적이다.

n = int(input())

books = {}

for _ in range(n):
    book = input()
    if book not in books:
        books[book] = 1
    else:
        books[book] += 1
        
target = max(books.values())
array = []

for book, number in books.items():
    if number == target:
        array.append(book)
        
print(sorted(array)[0])

책이 등장한 횟수를 세기 위해서 books = {} 라고 하나의 dictionary자료형을 만들었다.

그 다음 데이터를 입력 받을 때 마다. 해당 책이 dictionary에 들어있지 않다면 1로 설정한다. 이유는 하나의 책이 새로 들어온 것이니까. 그다음, 해당 책이 한번이라도 등장한 경험이 있다면 등장횟수에 1을 더해주는 것이다.

for _ in range(n):
    book = input()
    if book not in books:
        books[book] = 1
    else:
        books[book] += 1

이 코드를 수행하게 되면 책이 등장한 횟수만큼 1을 더해주게 된다.

그 다음, 해당 books를 값을 기준으로 정렬을 해서, 가장 큰 값을 가져오는 것이다. max를 가장 큰 함수를 가져오는 함수니까 target에 넣는다. 이 코드를 예를 들자면,  예제출력 1에서 보았던 top에서 4번 등장한 횟수가 가장 많았던 것처럼 top이 출력되는 것이다. 

for book, number in books.items():
    if number == target:
        array.append(book)

여기서 등장횟수가 가장 큰 것과 동일 하다면 array에다가 담고, 사전 순으로 가장 책의 이름이 앞 쪽에 있는 것을 출력하게 만들도록, sorted 로 print했다.   

개인적으로는 난이도가 조금 있어서, 연습 해야겠다.

여기서 N이 최대 10⁹ 이니까 1,000,000,000 이다.

새들은 1부터 오름차순으로 반복적으로 증가하므로, 날아가는 새의 마리 수는 빠르게 증가한다는 것을 알 수 있다.

그럼 등차수열이기에 O(n²)으로 시간복잡도가 분류된다. 그렇기에 N이 큼에도 불구하고 단순하게 요구하는대로 풀 수 있다.예시입력이 14인 것을 보면, 1 2 3 4 에서 5마리의 새는 날아가지 못하니까(15가 됨) 다시  1부터 시작해서 1 2 에서 13이 되고 3마리의 새는 날아가지 못하고 다시 1이 되니까 1 2 3 4 1 2 1 이니까 총 7초가 걸린다.

n = int(input())
result = 0
k = 1

while n != 0: # 모든 새가 날아갈 때까지
    if k > n:
        k = 1
    n -= k
    k += 1
    result += 1

print(result)

여기서 k는 1부터 출발을 하고, 입력된 숫자 'n'의 값이 0이 될 때까지, 즉 모든 새가 다 날아갈 때까지 반복한다. 순차적으로 증가하는 수 'k'를 이용해서 'n'에서 계속 빼는데, k가 n보다 커질 시, k는 다시 1로 재설정되면서 반복된다.

각 루프가 완료될 때마다 result 변수는 1씩 증가해서 총 몇 초가 걸리는지 확인할 수 있다.

문서가 있을 때, 단어를 찾는 문제, 동시에 셀 수 없기에 하나의 단어만 찾을 수 있다. 

예제 입력1 같은 경우  aba aba가 두번 찾을 수 있기에 예제출력에서 2와 같은 것이 나오고, 

예제 입력2 같은 경우 aa가 두번 있기에 2번

예제 입력3 같은 경우 ababa가 한번 있기에 1

예제 입력4 같은 경우 aa가 매치가 안되는 것 없이 전부 매치되기에 3이 출력된다. 

문서의 길이는 최대 2,500이고 단어의 길이는 최대 50이다.

그러면 단순하게 모든 경우의 수를 계산하여 문제를 해결 가능 하다. 그럼 시간복잡도 O(NM)의 알고리즘으로 해결 가능하다. 모든 경우를 탐색해도 약 10만정도의 작은 수 이기 때문이다. 

document = input()
word = input()

index = 0
result = 0

while len(document) - index >= len(word):
    if document[index:index + len(word)] == word: # 문서에서 보고 있는 단어가 찾고자 하는 단어인 경우
        result += 1
        index += len(word)
    else:
        index += 1
 
print(result)

index = 0을 만들어 줌으로 써 index 0부터 차례대로 비교할 수 있도록 설계를 시작한다.

이후 while문을 통해서 단어가 벗어나지 않을 때 까지 반복을 해주면서, 비교를 할 때 마다 문서에서 index부터 단어의 길이만큼 확인을 해서 == word로 단어와 정확히 일치하는지,만약 찾고자 하는 단어와 일치하는 경우 단어의 길이만큼 ( index += len(word) )를 통해서  index를 더해준다. 찾지 못한 경우,

 else:
        index += 1

로 한칸만 이동하게 만든다.

 N개의 수가 주어졌을 때, 이를 ASC순으로 정렬하는 문제

그러나 첫째 줄에 수의 개수가 최대 백만 개 까지 주어질 수 있으며, 2초 이내에 정렬해야 되는 문제이다.

그렇기 때문에 효과적인 알고리즘을 이용해야 한다. 여기서는 시간 복잡도 O(NlogN)의 정렬 알고리즘을 이용 해보았다. 그럼 약 2천만번의 연산 횟수가 만들어 진다.(파이썬으로 할 시, 1초에 2천만번 정도의 연산이 가능하다.)

알고리즘은 병합 정렬,퀵 정렬, 힙 정렬을 사용 할 수 있지만 퀵 정렬에서는 O(n²)이 나올 수 있기에, 병합,힙을 이용하거나, 파이썬의 기본 정렬 라이브러리를 이용할 수 있다.

병합 정렬은 시간복잡도 O(NlogN)을 보장하기에 병합 정렬을 이용하고, 메모리 제한이 없는 문제이기에 PyPy3를 이용했다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    if i == len(left):
        while j < len(right):
            array[k] = right[j]
            j += 1
            k += 1
    elif j == len(right):
       while i < len(left):
            array[k] = left[i]
            i += 1
            k += 1
    return array

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array = merge_sort(array)
for data in array:
    print(data)

return array까지 기존 병합정렬 코드에서 array만 넣어주면, 자동으로 해당 리스트를 정렬 해준다는 특징이 있기에 병합정렬을 이용하기 위해 n = int(input())로 데이터의 개수를 받고,  

for _ in range(n):
    array.append(int(input())) 으로 차례대로 데이터의 개수 만큼 리스트에 원소를 채워 넣는 다음, 

array = merge_sort(array)로 정렬을 한 뒤에 

정렬한 데이터를

for data in array:
    print(data)로 한 줄에 하나씩 출력하도록 만들었다.

아니면 Python 기본적으로 제공해주는 내장함수  sorted를 이용해서 더 쉽게 문제 해결도 가능하다.

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)
for data in array:
    print(data)

시간제한 : 1초

메모리 제한 : 128MB

난이도 : 하

문제

------

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

------

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

------

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

5 21
5 6 7 8 9

21

10 500
93 181 245 214 315 36 185 138 216 295

497

핵심아이디어:

카드 중 3개씩 뽑는 모든 경우의 수는 C(n,3)이며, n은 최대 100개 이다.

n은 최대 100까지 가능. 즉 카드가 100개 까지 가능.

3개를 뽑는다고 했을 때, n개에서 3개를 뽑는 것과 동일

즉 전체 수를 전부 고려한다고 해도 최대 100밖에 안되기에 대략 이것을 100만이라고 설정하더라도 컴퓨터가 충분히 계산 가능하기에 완전탐색을 이용하여 푼다.

일반적으로 파이썬은 1초에 2천만정도의 계산이 가능하다.

n, m = list(map(int, input().split(' ')))
data = list(map(int, input().split(' ')))

result = 0
length = len(data)

count = 0
for i in range(0, length):
    for j in range(i + 1, length):
        for k in range(j + 1, length):
            sum_value = data[i] + data[j] + data[k]
            if sum_value <= m:
                result = max(result, sum_value)

print(result)

음계 

시간제한 1초 메모리제한 128MB

문제

-------

다장조는 c d e f g a b C, 총 8개의 음으로 이루어져 있다.이 문제에서 8개 음은 다음과 같이 숫자로 표현한다. c는 1로, d는 2로,...C는 8로 바꾼다.

1부터 8까지 차례대로 연주한다면 ascending. 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다.

연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지 아니면 mixed인지 판별하는 프로그램을 구현하라.

입력

-------

첫째 줄에 8개 숫자가 주어진다. 이 숫자는 문제 설명에서 설명한 "음"이며, 1부터 8까지의 숫자가 한 번씩 등장한다.

출력

------

첫째 줄에 ascending, descending,mixed 중 하나를 출력한다.

예제 입력                          예제 출력

1 2 3 4 5 6 7 8                   ascending

8 7 6 5 4 3 2 1                   descending

8 1 7 2 6 3 5 4                   mixed 

푸는 법 

1.리스트에서 원소를 차례대로 비교한다.

2.비교할 때 두 원소를 기준으로 오름차순/내림차순 여부를 체크한다.

a = list(map(int, input().split(' ')))
ascending = True
descending = True
for i in range(1, 8):
    if a[i] > a[i - 1]:
        descending = False
    elif a[i] < a[i - 1]:
        ascending = False

if ascending:
    print('ascending')
elif descending:
    print('descending')
else:
    print('mixed')