[240506] 코딩테스트 문제풀이

 

1. 문자열 집합

https://www.acmicpc.net/problem/14425

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

for i in range(n):
    A.append(input())

count = 0

for i in range(m) :
    word = input()
    if A.count(word) > 0 :
        count += 1

print(count)

 

---

2. 패션왕 신혜빈

• 중요한 것은 조합 구하는 방법
  • combination *= (n+1)
  • 각 종류의 의상을 선택할 때, 의상을 선택하지 않는 경우도 있을 수 있기 때문에 +1 한 값을 곱해주고,
  • 마지막 출력값에서 아무것도 입지 않을 경우의 수 (1가지) 를 빼줌

https://www.acmicpc.net/problem/9375

from collections import Counter
n = int(input())

for _ in range(n) :
    m = int(input())
    A = list()

    for i in range(m) :
        A.append((input().split(" ")[1]))

    dict_a = Counter(A)
    combination = 1

    for i in dict_a.values() :
        combination *= (i+1)

    print(combination-1)

 

---

3. 회사에 있는 사람

• 마지막에 for문으로 출력하니깐 시간초과가 발생했다 
• join 함수써서 출력하는게, 시간초과 문제를 해결해줌

https://www.acmicpc.net/problem/7785

import sys
input = sys.stdin.readline

n = int(input())
A = set()
for i in range(n) :
    a,b = input().split()

    if b.strip()=='enter' :
        A.add(a)

    if b.strip()=='leave' :
        A.remove(a)

A= sorted(A,reverse=True)

print('\n'.join(A))

 

---

4.  알파벳 개수

• abcdef 이것도 똑바로 못 적어서 틀렷엇음

https://www.acmicpc.net/problem/10808

A = 'abcdefghijklmnopqrstuvwxyz'
A = list(A)

B = list(input())

for i in range(len(A)) :
    print(B.count(A[i]),end=' ')

 

---

5.  홀수

https://www.acmicpc.net/problem/2576

B = list()

for i in range(7) :
    number = int(input())
    if number%2 != 0 :
        B.append(number)

if len(B) == 0 :
    print(-1)
else :
    print(sum(B))
    print(min(B))

 

---

6. 명령 프롬포트

https://www.acmicpc.net/problem/1032

n = int(input())
A = list()

for i in range(n) :
    A.append(str(input()))

for i in range(len(A[0])) :
    answer = set()
    for j in range(n) :
        answer.add(A[j][i])

    if len(answer) == 1:
        print(A[j][i],end='')
    else :
        print('?',end = '')

 

---

7.  이항계수

https://www.acmicpc.net/problem/11051

# 이항계수

n,m = map(int, input().split(" "))
D = [[0 for i in range(n+1)] for j in range(n+1)]

if n == 1 :
    print(1)
else :

    # 점화식 초기화
    for i in range(1,n+1) :
        D[i][0] = 1
        D[i][1] = i
        D[i][i] = 1


    for i in range(2,n+1) :
        for j in range(1,n+1) :
            D[i][j] = (D[i-1][j-1] + D[i-1][j]) % 10007

    print(D[n][m])

 

---

8. 1,2,3 더하기

• 이렇게하면 시간초과 발생함 -> 따라서 dp 테이블을 max_number에 따라 만들어놓고 출력하는 방식으로 구현해야 함

import sys
input = sys.stdin.readline
n = int(input())

for i in range(n) :
    number = int(input())
    D = [0,1,2,4]

    if number >=3 :
        for i in range(4,number+1) :
            D.append((D[i-1] + D[i-2] + D[i-3]) % 1000000009)

    print(D[number])

import sys
input = sys.stdin.readline
n = int(input())
A = [int(input()) for _ in range(n)]

max_number = max(A)

dp = [0,1,2,4]
for i in range(4,max_number+1) :
    dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % 1000000009)
for i in A :
    print(dp[i])

 

---

9. 동전 1 (⭐️점화식 아이디어)

• 문제 예시로 점화식을 구해보면
  • dp[j] = dp[j] + dp[j-i]

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
1	2	2	3	3	4	4	5	5	6
1	2	2	3	4	5	6	7	8	10

https://www.acmicpc.net/problem/2293

n,m = map(int, input().split(" "))
A = list()

for i in range(n) :
    A.append(int(input()))

dp = [0] * (m+1)
dp[0] = 1
for i in A :
    for j in range (i,m+1) :
        dp[j] = dp[j] + dp[j-i]

print(dp[m])

 

---

 

10. 쉬운 계단 수

• 점화식 도출
  • D[N][H] : 길이가 N인 계단에서 H 높이로 종료되는 계단 수를 만들 수 있는 경우의 수
  • 높이에 따른 점화식
    • D[i][H] = D[i-1][H-1]
    • D[i][H] = D[i-1][H+1]
    • D[i][H] = D[i-1][H-1] + D[i-1][H+1]
  • 점화식 초기화
    • 길이가 1인 계단은 모두 값이 1일 것임
      • D[1][H] = 1

https://www.acmicpc.net/problem/10844

 

n = int(input())
D = [[0 for i in range(10)] for _ in range(n+1)]

# 점화식 초기화
for i in range(1,10) :
    D[1][i] = 1

if n>= 2:
    for i in range(2,n+1) :
        for j in range(10) :
            if j == 0 :
                D[i][0] = D[i-1][1]

            elif j == 9 :
                D[i][9] = D[i-1][8]

            else :
                D[i][j] = (D[i-1][j+1] + D[i-1][j-1]) % 1000000000

answer = sum(D[n]) % 1000000000

print(answer)

 

---

11.  카드

from collections import Counter

n = int(input())
A = list()

for i in range(n) :
    A.append(int(input()))

count_a = Counter(A)
a_keys = list(count_a.keys())
a_value = list(count_a.values())
B = [[0 for i in range(2)] for _ in range(len(a_keys))]
for i in range(len(a_keys)) :
    B[i][1] = a_keys[i]
    B[i][0] = -a_value[i]

B.sort()
answer = B[0][1]
print(answer)

 

---

12. 부분 문자열 (⭐️복습하기)

• input 값이 몇 개인지 가르쳐주지 않았을 떄
  • while - try - except 문으로 

https://www.acmicpc.net/problem/6550

def word_tf(a,b) :
    idx = 0
    answer = 0

    for i in range(len(b)) :
        if a[idx] == b[i] :
            idx += 1

        if len(a) == idx :
            answer = 1
            break

    if answer :
        return("Yes")

    else :
        return("No")

while True :
    try :
        a,b = input().split(" ")
        answer=word_tf(a,b)
        print(answer)

    except :
        break

 

---

13. 섬의갯수

• 근데 나 되게 멍청하게 푸는 듯

https://www.acmicpc.net/problem/4963

from collections import deque
directions = [(1,0),(-1,0),(1,1),(-1,-1),(0,1),(0,-1),(1,-1),(-1,1)]

def bfs(b,a,grid) :
    queue = deque()
    area_cnt = 0
    for row in range(a) :
        for col in range(b) :
            if grid[row][col] == 1 :
                queue.append((row,col))
                while queue :
                    curr_x, curr_y = queue.popleft()
                    for dx,dy in directions :
                        next_x, next_y = curr_x + dx, curr_y + dy
                        if 0<=next_x<a and 0<=next_y<b and grid[next_x][next_y] == 1:
                            queue.append((next_x,next_y))
                            grid[next_x][next_y] = 0
                area_cnt +=1
    return area_cnt


while True :
    n,m = map(int, input().split(" "))
    if n==0 and m==0 :
        break
    else :
        grid = []
        for i in range(m) :
            grid.append(list(map(int, input().split(" "))))

    print(bfs(n,m,grid))

 

---

14. 안전영역

• 진짜 멍청하게 코드 짜는 듯
• 계속 헤맨이유 : 최대 높이는 input 값에 없는 값일수도 있음 예를 들어 5 4 5 5 7 이렇게 들어왔을 때, 최대높이 값이 6으로 설정될 수도 있음. 나는 하지만 input 값에서 최댓값을 꺼낼려고 계속 했었다...
• 또 visited 배열 사용을 안하고, grid에서 한번 돌면 max_number 값으로 바꿔줄려고 했었는데, 그러면 함수가 한번 돌 때 grid 값이 바껴져있어서, 다름 for k in range 구문에서 당연히 틀린 값이 나올 수 밖에 없음 !! 

https://www.acmicpc.net/problem/2468

from collections import deque
directions = [(1,0),(-1,0),(0,1),(0,-1)]

def bfs(n,grid,B) :
    answer = 0
    for k in range (B) :
        max_number = k
        queue = deque()
        count = 0
        visited = [[False for i in range(n)] for _ in range(n)]
        for row in range(n) :
            for col in range(n) :
                if grid[row][col] > max_number and not visited[row][col]:
                    queue.append((row,col))
                    visited[row][col] = True
                    while queue :
                        curr_x, curr_y = queue.popleft()
                        for dx,dy in directions :
                            next_x, next_y = curr_x+dx, curr_y + dy
                            if 0<=next_x<n and 0<=next_y<n and grid[next_x][next_y] > max_number and not visited[next_x][next_y] :
                                queue.append((next_x,next_y))
                                visited[next_x][next_y] = True

                    count += 1

        answer = max(answer,count)

    return answer

n = int(input())
A = list()
for i in range(n) :
    A.append(list(map(int, input().split())))

B = max(max(row) for row in A)



print(bfs(n,A,B))

 

---

15. 제곱근 (⭐️복습하기)

• import math -> math.sqrt(n) 하면 런타임 에러 뜸 ㅠㅠ
• 근데 이진탐색으로 구현할 수 있다니 !! 

n = int(input())
start = 1
end = n

while 1 :
    mid = ( start + end ) // 2
    if mid ** 2 == n:
        print(mid)
        break

    elif mid ** 2 > n :
        end = mid -1

    elif mid ** 2 < n :
        start = mid + 1

 

---

16. 현수막

• 스스로 짜는게 어디야...

https://www.acmicpc.net/problem/14716

# 현수막
from collections import deque
n,m = map(int, input().split(" "))
A = list()
for i in range(n) :
    A.append(list(map(int, input().split(" "))))

directions = [(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1),(0,-1),(0,1)]

def dfs(n,m,A) :
    count = 0
    queue = deque()
    for row in range(n) :
        for col in range(m) :
            if A[row][col] == 1 :
                queue.append((row,col))
                while queue :
                    now_x, now_y = queue.popleft()
                    for dx,dy in directions :
                        ne_x,ne_y = now_x + dx, now_y + dy
                        if 0<=ne_x<n and 0<=ne_y<m and A[ne_x][ne_y] == 1 :
                            queue.append((ne_x,ne_y))
                            A[ne_x][ne_y] = 0

                count += 1

    return count

print(dfs(n,m,A))