Jin의 일상

문제 설명

- 첫 번째 줄에서는 주어질 데이터의 개수(N)가 주어진다.

- 다음 줄에는 N개의 데이터가 주어진다. (1 <= N <= 500,000)

- 시간 제한  1초

출력 : 숫자 간 교환이 일어난 횟수를 구해야 한다.

버블 정렬 예시

(1) 321 : 3 2 1 => 2 3 1  => 2 1 3 => 1 2 3

(2) 4253 : 4 2 5 3 => 2 4 5 3=> 2 4 3 5 => 2 3 4 5

문제 풀이

(1) 어떤 정렬 알고리즘을 사용할지?

버블 소트는 N 제곱의 시간 복잡도를 가진다.

문제 조건에 따르면 최대 25 * (10^10)의 시간 복잡도를 가진다.

파이썬의 1초당 계산 가능 횟수는 2 * (10^7)이므로, 버블 소팅으로는 문제를 풀 수 없다.

따라서 다른 방식의 정렬을 이용해야 한다.

병합정렬을 이용하면 N * log(N)의 시간복잡도가 소요된다. 

5*(10^5) * log(5*(10^5))이므로, 시간 복잡도는 해결이 된다.

(2) 숫자 간 교환 횟수를 어떻게 구할지?

버블 정렬에서는, 

1. 두 요소 간 순서가 맞으면 가만히 두고

2. 순서가 틀렸다면 숫자를 교환한다.

2번에 착안해서 버블 정렬에서 정렬하는 과정을 살펴보자.

1. 위 그림의 맨 밑에 줄부터 A와 B를 비교해서 B가 작으면 교환이 일어난다.

이 때, 교환될 숫자의 개수는 CNT에 더해주자. (남은 A의 개수만큼 더해주면 된다.)

[3] [1] => [1, 3]           [2] [4] => [2, 4]

CNT += len(A)

2. [1, 3] [2, 4]를 비교한다. 

A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 1이 빠진다.

[1,3] [2, 4] => [3] [2, 4],  [1]

3. A의 맨 앞과 B의 맨 앞을 비교했을 때, B가 작으므로, B의 2가 빠진다.

B가 작으면, 스와핑이 일어나야 하므로 남은 A의 총 길이를 CNT에 더해준다. 

[3] [2, 4] => [3] [4],  [1, 2]

CNT += len(A)

4. A의 맨 앞과 B의 맨 앞을 비교했을 때, A가 작으므로, A의 3이 빠진다.

[3] [4], => [] [4], [1, 2, 3]

5. A에 들어있던 모든 원소가 빠졌으므로, B에 남은 원소를 추가한다

[] [4] => [] [], [1, 2, 3, 4]

6. 스와핑이 일어난 횟수(CNT):  2

반례

문제에는 동일한 원소가 나오지 않는다는 조건이 없다.

즉, 3 2 5 3 4와 같은 경우가 있을 수 있다.

이를 고려하여 코드를 작성해야 한다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def mergeSort(start, end):
    global cnt
    if start < end:
        mid = (start + end) // 2
        mergeSort(start, mid)
        mergeSort(mid + 1, end)

        a = start
        b = mid + 1
        tmp = []
        while a <= mid and b <= end:
            if arr[a] <= arr[b]:
                tmp.append(arr[a])
                a += 1

            else:
                tmp.append(arr[b])
                b += 1
                cnt += (mid - a + 1)  # 스와핑 했을 때 개수추가
        if a <= mid:
            tmp = tmp + arr[a:mid+1]
        if b <= end:
            tmp = tmp + arr[b:end+1]

        for i in range(len(tmp)):
            arr[start + i] = tmp[i]

if __name__ == '__main__':
    cnt = 0
    n = int(input())
    arr = list(map(int, input().split()))
    mergeSort(0, n-1)
    print(cnt)

programmers.co.kr/learn/courses/30/lessons/68936

코드

import sys
sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


# def printer(x, y, l):
#     for i in range(l):
#         for j in range(l):
#             print(arr[x + i][y + j], end=' ')
#         print()


def checker(x, y, l, arr):
    s = arr[x][y]
    for i in range(l):
        for j in range(l):
            if arr[x + i][y + j] != s:
                return False
    return True


def add_startList(x, y, k, startList):
    startList.append((y, x, k))
    startList.append((y + k, x, k))
    startList.append((y, k + x, k))
    startList.append((y + k, x + k, k))
    return startList


def converter(x, y, k, arr):
    if arr[x][y] == 0:
        v = 3
    else:
        v = 4

    for i in range(k):
        for j in range(k):
            arr[x + i][y + j] = v
    return arr


def find_zero_one(arr, k):
    zero = 0
    one = 0
    for i in range(k):
        for j in range(k):
            if arr[i][j] == 0:
                zero += 1
            else:
                one += 1
    return zero, one


def solution(arr):
    k = len(arr[0])  # 탐색 길이
    startList = [(0, 0, k)]  # (y, x, k)
    zero, one = find_zero_one(arr, k)  # number of zero, one

    while startList:
        y, x, k = startList.pop()
        if checker(x, y, k, arr):
            if arr[x][y] == 0:
                zero -= k * k - 1
            else:
                one -= k * k - 1
            arr = converter(x, y, k, arr)
        else:
            k = k // 2
            if k < 2:
                continue
            startList = add_startList(x, y, k, startList)
    answer = [zero, one]
    return answer


if __name__ == "__main__":
    arr = [[1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1],
           [0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 1], [0, 0, 0, 0, 1, 1, 1, 1]]
    res = [4, 9]
    solution(arr)

문제 설명

일반 알파벳 순서와 달리 민식어는 "a b k d e g h i l m n ng o p r s t u w y" 순서를 따릅니다.

민식어 중 ng는 하나의 알파벳으로 간주됩니다.

민식어로 만든 n개의 단어가 주어졌을 때, 민식어를 기준으로 순서대로 리턴합니다.

알고리즘

1. 딕셔너리의 키를 민식어로 두고, 순서에 따라서 값으로 알파벳을 정의합니다. (문자를 기준으로 정렬하기 때문에 숫자로 값을 정의하면 12 > 101와 같은 경우가 발생합니다. )

 - 민식어 중에서 "ng"는 "z"와 같이 민식어에 포함되지 않는 알파벳을 정의합니다.

2. 민식어로 만든 단어들을 입력받고, 각 단어에서 "ng"를 찾아서 다른 알파벳으로 바꿉니다. 알고리즘 1번에서 언급했듯이 민식어에 포함되지 않는 알파벳으로 선택해야 합니다.

3. 반복문으로 민식어로 만든 문자를 한 글자씩 추출하여 딕셔너리의 키 값으로 넣습니다. value로 나온 것을 더하여 알파벳으로 치환합니다.

4. 민식어에서 알파벳으로 치환된 문자는 여러 개의 민식어가 저장된 리스트의 인덱스 번호와 함께 새로운 리스트에 담은 뒤, 문자를 기준으로 정렬합니다.

5. 정렬된 문자를 순서대로 뽑으며, 저장했던 인덱스 번호로 민식어를 출력합니다.

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

# key: ng => z (there is no 'z' in Minsik.)
minsik = {"a": 'A', "b": 'B', "k": 'C', "d": 'D', "e": 'E', "g": 'F', "h": 'G', "i": 'H', "l": 'I', "m": 'J', "n": 'K',
          "z": 'L', "o": 'M',
          "p": 'N', "r": 'O', "s": 'P', "t": 'Q', "u": 'R', "w": 'S', "y": 'T'}


n = int(sys.stdin.readline())
words = [sys.stdin.readline().rstrip() for _ in range(n)]

cvtWords = []
for i in range(n):
    word = words[i].replace('ng', 'z')
    cvtWord = ''
    for ch in word:
        cvtWord += minsik[ch]
    cvtWords.append([cvtWord, i])
cvtWords.sort(key=lambda x: x[0])
for _, i in cvtWords:
    print(words[i])

문제

왼쪽과 같이 데이터가 주어진다.

첫째 줄은 테스트 케이스의 개수(f)다.

둘째 줄은 하나의 테스트 케이스에 포함된 데이터의 개수(n)이다.

셋째 줄부터 n개의 데이터가 주어진다.

각 데이터는 전화번호를 의미하며, 다른 전화번호의 접두어가 될 수없다.

모든 전화번호에 접두어가 없다면 YES를 출력하고 하나라도 접두어가 있다면 NO를 출력한다.

(이 문제의 경우 2123이 21235의 접두어가 될 수 있으므로 NO가 출력된다.)

문제 풀이

1. n개의 데이터를 문자 형태로 리스트에 입력 받는다.

2. 정렬한다.

3. 리스트의 각 인덱스의 뒤에 위치한 문자와 비교한다.

   - 접두어가 될 수 있다면 NO를 출력한 뒤 break로 빠져나온다.

   - 접두어가 될 수 없다면 계속해서 진행하고 for문이 종료되면 YES를 출력한다.

코드

sys.stdin.readline()을 사용해야 합니다. input()을 하면 시간초과가 나옵니다.

많은 양의 데이터를 읽을 때는 sys.stdin.readline()이 유리하다고 합니다.

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
f = int(sys.stdin.readline())
for _ in range(f):
    n = int(sys.stdin.readline())
    numberList = [sys.stdin.readline().strip() for _ in range(n)]
    numberList.sort()

    for i in range(n - 1):
        if numberList[i] == numberList[i + 1][:len(numberList[i])]:
            print("NO")
            break
    else:
        print("YES")

문제

첫째 줄에 F, S, G, U, D가 주어집니다.

U는 올라가는 엘리베이터 버튼을 의미하고, D는 내려가기 위한 버튼을 의미합니다.

엘리베이터는 F층까지 있고, S층에 있는 강호가 G층으로 가기 위해 최소로 눌러야 하는 버튼 수를 리턴해야 합니다.

 - G에 도착할 수 없다면 "use the stairs"를 출력합니다.

문제풀이

1. 각 층을 리스트로 표현합니다.

 - 0이면 아직 방문하지 않은 층이고, 1이면 방문한 적 있는 층입니다.

2. 도착해야 하는 층인 G를 향해 최대한 U 버튼을 누릅니다.

 - G층 이상으로는 올라갈 수 없습니다.

 - 이미 리스트 값이 1인 곳에는 재방문하지 않습니다.

 - G에 도착했다면, 리스트의 총합을 정답으로  리턴합니다.

 - 각 층에 도착할 때 마다 리스트의 값을 1로 변경합니다.

 - 현재 위치를 갱신합니다.

3. 더 이상 G를 향해 올라갈 수 없다면 D만큼 내려갑니다.  

 - 1층 이하로는 내려갈 수 없습니다.

 - 이미 리스트 값이 1인 곳에는 재방문하지 않습니다.

 - G에 도착했다면, 리스트의 총합을 정답으로  리턴합니다.

 - 각 층에 도착할 때 마다 리스트의 값을 1로 변경합니다.

 - 현재 위치를 갱신합니다.

4. 2번와 3번을 반복적으로 실행합니다.

 - 2와 3번이 더 이상 실행될 수 없다면, 반복을 종료하고 use the stairs를 출력합니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
F, S, G, U, D = map(int, input().split())

visited = [0] * (F + 1)  # 0: 방문하지 않음, 1: 방문한 적 있음
visited[S] = 1
q = [S]

while q:
    curr_f = q.pop()
    if visited[G] == 1:
        print(sum(visited)-1)
        break

    if (curr_f + U) <= G and visited[curr_f + U] == 0:
        visited[curr_f + U] = 1
        q.append(curr_f + U)

    elif (curr_f - D) >= 1 and visited[curr_f - D] == 0:
        visited[curr_f - D] = 1
        q.append(curr_f - D)
else:
    print("use the stairs")

www.acmicpc.net/problem/11508

문제

n개의 제품이 주어진다.

마트에서는 2+1 행사를 하며, 꾸러미에 3개의 제품을 담으면 1개는 무료로 판매된다.

이 때, 주어진 제품을 모두 구입한다고 했을 때 최소 비용은 얼마인가?

문제 풀이

가장 비싼 제품을 3번째 꾸러미에 담으면 된다.

따라서 제품들을 내림차순으로 정렬하고, 3의 배수가 되는 제품의 비용을 총 가격에 포함시키지 않으면 된다.

코드

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
prices = [int(input()) for _ in range(n)]
prices = sorted(prices, reverse=True)

res = 0
for i in range(1, n+1):
    if i % 3 == 0:
        continue
    res += prices[i-1]
print(res)

www.acmicpc.net/problem/13458

문제

세 줄로 데이터가 주어진다.

각 줄은 시험장의 개수 (n), 각 시험장의 응시자 수 (a), 총 감독관 역량(b), 부 감독관 역량(c)를 의미한다.

 - b와 c는 감독 가능한 응시자 수를 의미한다.

총감독관은 각 시험장에 최소 한 명 들어가야 하며, 부 감독관은 여러 명이 들어가도 된다.

이 때, 모든 응시자를 감독하기 위한 감독관의 수를 구해야 한다.

알고리즘

1. 시험장에는 최소 한 명의 총 감독관이 들어가야 한다.  따라서 각 시험장의 응시자 수에서 b를 뺀다.

 (1) n - b <= 0인 경우에는 정답으로 제출할 총 감독관 수에 1을 더한다.

   한 명의 총 감독관이 모든 응시자를 감독할 수 있으므로, 부 감독관이 필요없기 때문이다.

 (2) n - b > 0인 경우에는 2번으로 넘어간다.

2. n - b를 한 값에 부 감독관의 역량인 c를 나누어 준다.

 (1) 나머지가 있는 경우에는 정답으로 제출할 총 감독관 수에 3을 더해준다.

   - 총 감독관 1명 + 부 감독관 2명

 (2) 나머지가 없는 경우에는 정답으로 제출할 총 감독관 수에 2를 더해준다.

  - 총 감독관 1명 + 부 감독관 1명

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

n = int(input())
a_list = list(map(int, input().split()))
b, c = map(int, input().split())

cnt = 0
for i in range(n):
    tmp = a_list[i] - b
    if tmp <= 0:
        cnt += 1
    else:
        q, r = divmod(tmp, c)
        if r == 0:
            cnt += (q + 1)
        else:
            cnt += (q + 2)
print(cnt)

programmers.co.kr/learn/courses/30/lessons/42578

문제설명

1. 리스트에 1개 이상의 [의상의 이름, 의상의 종류]이 주어집니다.

ex) [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]

2. 최소 한 개 이상의 옷을 착용 한다고 했을 때, 착용 가능한 옷의 조합 수를 구해야 합니다.

 - 동일한 종류의 의상은 착용이 불가능합니다.

ex) 위의 예시에서 yellow_hat과 green_turban은 동시착용이 불가능합니다.

문제 풀이

1. 다음과 같은 테스트 케이스가 주어졌다고 가정합니다.

2. 입력받은 데이터는 딕셔너리로 표현될 수 있습니다. 

3. 착용할 수 있는 의상을 종류에 따라 트리로 정리하면 아래와 같습니다.

- 의상 종류별로 입을 수 있는 경우의 수는 "총 개수 + 1" 입니다.

  - 예를 들어, headgear에 관한 경우의 수는 "yellow_hat", "green_turban", "착용X"이 있습니다.

따라서 모든 종류의 의상을 착용하지 않는 경우의 수를 제외하면

(headergear의 개수+1) * (eyewear의 개수+1) -1이 정답으로 출력 됩니다.

코드

def solution(clothes):
    types = {}
    for v, k in clothes:
        types[k] = types.get(k, 0) + 1

    cnt = 1
    for _, v in types.items():
        cnt *= v+1
    return cnt-1