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

1. 전쟁 - 전투

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

from collections import deque

directions = [(1,0),(-1,0),(0,1),(0,-1)]
def BFS(v,team) :
    team_list = v
    queue = deque()
    answer = 0
    count = 0

    for row in range(m) :
        for col in range(n) :
            if team_list[row][col] == team :
                queue.append((row,col))
                team_list[row][col] = '0'
                while queue :
                    x,y = queue.popleft()
                    count += 1
                    for dx,dy in directions :
                        next_x, next_y = x + dx, y + dy
                        if 0<=next_x<m and 0<=next_y<n and team_list[next_x][next_y] == team :
                            queue.append((next_x, next_y))
                            team_list[next_x][next_y] = '0'

                answer += count*count
                count = 0

    return answer


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

for i in range(m) :
    A.append(list(input()))

print(BFS(A,'W'),end = ' ')
print(BFS(A,'B'))

 

---

2.  숨바꼭질(🥲복습 및 심화문제 풀기)

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

def bfs(s,e) :
    # 1. 큐, visited 배열 생성
    q = []
    v = [0] * 200001

    q.append(s)
    v[s] = 1

    while q :
        c = q.pop(0)
        if c == e :
            return v[e] - 1

        for n in (c-1, c+1, c*2) :
            if 0<=n<200000 and v[n] == 0 :
                q.append(n)
                v[n] = v[c] + 1

    return -1


N,K = map(int, input().split())
ans = bfs(N,K)
print(ans)

 

---

3. 소수찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

from itertools import permutations
import math
def solution(numbers):
    numbers = list(numbers)
    set_a = set()
    for i in range(len(numbers)) :
        for j in permutations(numbers, i+1) :
            number =int(''.join(j))
            if number != 0 and number != 1:
                set_a.add(number)

    max_number = max(set_a)

    count = 0
    # 소수 리스트
    A = [i for i in range(max_number+1)]
    for i in range(2, int(math.sqrt(max_number))+1) :
        for j in range(i+i, max_number+1, i) :
            if A[j] in set_a :
                count += 1

            A[j] = 0


    return len(set_a) - count

 

 

---

4. ATM

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

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

S = [0] * n
S[0] = A[0]

for i in range(1,n) :
    S[i] = S[i-1] + A[i]


print(sum(S))

 

---

5. 소트인사이드

• 쉬운 문제지만 선택정렬로 해결 

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

A = list(map(int, input()))

for i in range(len(A)) :
    max_number = i
    for j in range(i+1, len(A)) :
        if A[max_number] < A[j] :
            max_number = j


    A[i], A[max_number] = A[max_number],A[i]

for i in A :
    print(i, end = '')

 

---

6. 통계학

• 마지막에 최빈값 -> Counter 구현하는 것이 조금 어려웠다. 

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

import sys
from collections import Counter
input = sys.stdin.readline


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

A.sort()

print(round(sum(A)/len(A)))
print(A[i//2])
counter_a = Counter(A)
counter_a = sorted(counter_a.items(), key = lambda item : item[1], reverse = True)

if n == 1 :
    print(counter_a[0][0])
else :
    if counter_a[0][1] != counter_a[1][1]  :
        print(counter_a[0][0])
    else :
        print(counter_a[1][0])
print(max(A) - min(A))