그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 2-친구가 되기 위해서는 간단하게 보면 직접 친구이거나, 한명의 친구를 거쳐서 친구이면 된다. 따라서 플로이드 알고리즘을 사용하여 거리 배열을 구한다.
   1. 직접 친구인 경우의 거리는 1이다.
   2. 한명의 친구를 거쳐서 친구인 경우의 거리는 2이다.
2. 각 사람별로 거리가 2 이하인 친구의 명수를 구해준 다음 최댓값을 구해준다.
3. (2)에서 구한 최댓값을 출력해 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

matrix = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 'N':
            matrix[i][j] = int(10e9)
        else:
            matrix[i][j] = 1

for i in range(N):
    for j in range(N):
        for k in range(N):
            matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])

answer = 0
for i in range(N):
    count = 0
    for j in range(N):
        if j != i and matrix[i][j] <= 2:
            count += 1
    answer = max(answer, count)


print(answer)

전체적인 과정을 살펴보면 각각의 문자열을 한자리씩 끊어서 char 타입의 배열로 만들어준 다음, char 타입의 배열을 정렬하는 방식으로 진행하는 것이다..

이 과정을 스트림을 사용하여 구현하기 위해서는, 다음과 같은 순서로 진행한다.

1. 문자열을 chars() 메소드를 사용하여 Intstream으로 바꿔준다.
2. Intstream을 박싱하여 IntegerStream으로 바꾸어준다.
3. sorted 메서드를 사용하여 정렬된 스트림을 얻는다. 이 때, Comparators.reverseOrder를 인자로 넘겨주면 내림차순으로 정렬된다.
4. 이후 정렬된 스트림을 int[] 타입의 배열로 얻어준 다음, Char형으로 바꿔주면서 한자리씩 추가해주는 방식으로 정렬된 문자열을 얻을 수 있다.

- char형 타입을 스트림으로 다룰때는 잘 되지 않는 점이 많으니 intstream으로 간주하고 int 배열로 처리하는것이 훨씬 편하다. 맨 마지막에 (char)만 붙여주면 아스키 코드가 문자화 되니까ㅎㅎ

import java.util.Comparator;

class Solution {
    public String solution(String s) {
        String answer = "";

        int[] temp = s.chars()
                .boxed()
                .sorted(Comparator.reverseOrder())
                .mapToInt(i -> i)
                .toArray();
        for (int ch : temp) {
            answer += (char)ch;
        }
        return answer;
    }
}

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

풀이 과정

문제에서 어떻게 구현하라고 다 나와있기 때문에 그대로 구현해주면 된다. 여기서는 개인적으로는 map과 filter을 잘 사용하면 소스코드가 많이 간결해질 수 있을 것이라고 생각된다.

1. 각 후보가 점수별로 몇점을 획득하였는지 저장해 둔다.
2. 전체 점수의 합계가 가장 큰 후보군을 먼저 골라준다.
3. 후보군이 2명 이상인 경우에는 다음 단계로 진행한다.
   1. 3점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
   2. 이후, 2점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
4. 모든 단계를 거치고 난 다음에도 후보군이 2명 이상이라면 0과 최대 점수를 출력해 주고, 후보군이 1명이라면 해당 인원의 번호와 점수를 출력해 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

score = [[0] * 3 for _ in range(3)]

for _ in range(N):
    a, b, c = map(int, input().split())
    score[0][a-1] += a
    score[1][b-1] += b
    score[2][c-1] += c

total_score = [[idx, sum(sc)] for idx, sc in enumerate(score)]
max_score = max(map(lambda x: x[1], total_score))
candidate = list(filter(lambda x: x[1] == max_score, total_score))

if len(candidate) >= 2:
    max_three_count = max(map(lambda x: score[x[0]][2], candidate))
    candidate = list(filter(lambda x: score[x[0]][2] == max_three_count, candidate))
    max_two_count = max(map(lambda x: score[x[0]][1], candidate))
    candidate = list(filter(lambda x: score[x[0]][1] == max_two_count, candidate))

if len(candidate) >= 2:
    print(0, max_score)
else:
    print(candidate[0][0] + 1, candidate[0][1])

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

풀이 과정

1. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 구성한다.
   1. 최소 비용인 간선을 하나 선택하고 Cycle을 형성하는지 체크한다
   2. Cycle을 형성하는지 체크하는 방법은 간선에 연결된 두 점이 하나의 집합에 속해있는지 확인하면 된다.
      1. Union-find 알고리즘 사용
   3. Cycle을 형성하지 않는다면 두 점을 연결해 주고 비용을 더해준다.
   4. 위 과정을 총 N-1개의 간선을 선택할 때까지 반복해 준다.
2. 최소 비용 신장 트리의 비용의 합계를 출력시켜 준다.

풀이 과정

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
heap = []
cost = [list(map(int,input().split())) for _ in range(N)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(heap, [cost[i][j], i, j])

answer = 0
parent = [i for i in range(N+1)]
edge_count = 0
while heap and edge_count < N-1:
    cost, fr, to = heapq.heappop(heap)
    if find(parent, fr) != find(parent, to):
        union(parent, fr, to)
        answer += cost
        edge_count += 1


print(answer)

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

풀이 과정

1. 맨 앞자리에 K가 들어오려면 이전 자리에는 K~9가 들어올 수 있다.
   1. 따라서 점화식을 구성하면 DP[i][K] = DP[i-1][K] + DP[i-1][K+1] + ... + DP[i-1][9]
   2. 해당 점화식을 이용하여 DP 테이블을 채워주면 된다. 단, 한자리일때는 자기 자신을 고를때밖에 없으므로 1로 설정하여 준다.
2. 이후 각각의 테스트 케이스에 입력받은 자리수에 맞추어서 DP 테이블에서의 합계를 구해서 출력시켜 준다.
   • 예를 들어, 자릿수 4를 입력받으면 DP[4]의 합계를 출력시켜 주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
dp = [[0] * 10 for _ in range(65)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, 65):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] += dp[i-1][k]

T = int(input())
for _ in range(T):
    C = int(input())
    print(sum(dp[C]))

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

풀이 과정

1. 현재 가진 연료로 어떤 주유소를 들릴 수 있는지를 업데이트 해주는게 핵심
2. 현재 가진 연료로 마을까지 갈 수 없다면 주유소를 무조건 하나 이상 들려야 함. 
   1. 따라서, 방문할 수 있는 주유소를 따로 기름의 양을 기준으로 최대 히프에 넣어 관리한다. 
   2. 이 때, 방문할 수 있는 주유소들 중 기름을 가장 많이 넣을 수 있는 주유소를 하나 방문해서 들려준다. 즉, 최대 히프에서 하나의 요소를 꺼내서 기름을 채워준다. 이 때 해당 주유소를 들리게 되므로 따로 카운트를 하나 늘려준다.
   3. 주유소를 방문해서 기름을 넣었으므로 넣은 기름으로 더 이동해서 방문할 수 있는 주유소를 다시 최대 히프에 넣어준다.
3. 방문할 수 있는 주유소가 더이상 없는데 마을에 도착하지 않았다면 -1을 리턴해 주고, 마을에 도착하였다면 방문한 주유소의 수를 출력시켜 준다.

소스 코드

import sys
import heapq
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
stations = [list(map(int, input().split())) for _ in range(N)]
dist, current_gas = map(int, input().split())
heap = []

stations.sort(key=lambda x:x[0])
queue = deque(stations)

answer = 0
while True:
    while queue and queue[0][0] <= current_gas:
        _, gas  = queue.popleft()
        heapq.heappush(heap, -gas)

    if dist <= current_gas:
        break
    else:
        if not heap:
            answer = -1
            break
        append_gas = -heapq.heappop(heap)
        current_gas += append_gas
        answer += 1

print(answer)

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

풀이 과정

1. 각각의 알파벳이 있는 자리가 1이라고 할 때 모두 더했을때 값이 얼마나 나오는지 구한다.
   • 예를 들어, Axxxx + xxAxx라 하면 10100이 나온다.
2. (1)에서 구한 값들중 가장 큰 값에 9를 부여하고, 다음 큰 값에 8을 부여하고 , .. 이러한 방식으로 값을 부여해준 다음 합계를 구해 준다.
   1. 값을 부여할 때는, (1)에서 구한 값에 부여한 값을 곱해주면 된다.
   2. 값을 부여한 후, 그대로 더한다.
3. (2)에서 구한 합계를 출력해 준다.

소스 코드

import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()


alpha = defaultdict(lambda: 0)
N = int(input())
for _ in range(N):
    word = input()
    size = len(word)
    for idx, ch in enumerate(word):
        alpha[ch] += (10 ** (size-1-idx))

temp = sorted(alpha.values(), reverse=True)
pos = 0
answer = 0
for i in range(9, 0, -1):
    answer += temp[pos] * i
    pos += 1
    if pos == len(temp):
        break

print(answer)

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

풀이 과정

1. 초기에 설치해둔 폭탄의 위치를 저장해 둔다.
2. 폭탄이 없는곳에 모두 폭탄을 설치시켜 준다.
   • 이 때, 초기에 설치해둔 폭탄과 터지는 시간이 다르기 때문에 폭탄이 없는곳에 폭탄을 설치하면서 위치를 따로 저장해 두어야 한다.
3. 직전에 설치한 폭탄이 아닌, 더 이전에 설치해둔 폭탄을 터트린다.
   • 이 때, 직전에 설치한 폭탄도 터질 수 있으므로 만약 직전에 설치한 폭탄도 터진다면 직전에 설치한 폭탄 집합에서 해당 폭탄을 제거해 준다.
4. 입력받은 시간에 맞추어서 2-3 과정을 반복해 주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
R, C, N = map(int, input().split())

matrix = [list(input()) for _ in range(R)]
boompos = []
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'O':
            boompos.append([i, j])

def set_boom(matrix):
    next_boom = set()
    for i in range(R):
        for j in range(C):
            if matrix[i][j] == '.':
                next_boom.add((i, j))
                matrix[i][j] = 'O'
    return next_boom

def boom(matrix, boompos, next_boom):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    destroypos = set()
    for x, y in boompos:
        destroypos.add((x, y))
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                destroypos.add((nx, ny))

    for x, y in destroypos:
        if (x, y) in next_boom:
            next_boom.remove((x, y))
        matrix[x][y] = '.'
        

time = 1
while time < N:
    next_boom = set_boom(matrix)
    time += 1
    if time == N:
        break
    boom(matrix, boompos, next_boom)
    boompos = next_boom
    time += 1

for m in matrix:
    print("".join(m))

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

풀이 과정

1. 문제에서 다리를 하나 무너뜨려 서로 왕복할 수 없는 섬이 생겼다고 주어졌으므로 두개의 섬으로 분리되었다는걸 알 수 있음.
2. Union-Find 알고리즘을 사용하여 두개의 섬의 집합을 구해준다.
   1. 이어진 섬의 parent는 같으며, 이어지지 않은 섬의 parent는 다르다는 점을 이용하여 1번째 섬에서부터 N번째 섬까지 방문하면서 인접한 섬과의 parent를 비교한다.
   2. parent 값이 다른 경우 떨어진 섬이므로 두 섬을 연결해주면 된다.

소스 코드

import sys

sys.setrecursionlimit(10**5)
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
parent = [i for i in range(N+1)]


def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    par1 = find(parent, a)
    par2 = find(parent, b)

    if par1 != par2:
        parent[par1] = par2

for _ in range(N-2):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

for i in range(2, N+1):
    if find(parent, i) != find(parent, i-1):
        union(parent, i, i-1)
        print(i, i-1)

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

풀이 과정

1. 그리디 알고리즘 문제인데 처음 생각할 때 꼬여서 어떻게 풀어야 할지 고민을 정말 많이한 문제다ㅜ
2. 숫자를 오름차순으로 정렬한다.
   1. 숫자들로 두개의 정수를 만들어야 하므로 a, b 리스트를 만들어 둔다.
   2. a, b 리스트에 번갈아가면서 작은 숫자부터 넣어준다.
   3. a, b 리스트에서 맨 앞에 넣을때는 0이 아닌 수중에 가장 작은 숫자를 넣어주어야 한다.
   4. 리스트에 채우는 작업이 종료되면, 두 리스트를 정수화하여 더해주면 된다.
3. 더해준 값을 출력한다.

 소스 코드

import sys
from collections import deque, defaultdict

input = lambda: sys.stdin.readline().rstrip()
while True:
    p = list(map(int, input().split()))
    numbers = defaultdict(lambda: 0)
    if p[0] == 0:
        break
    
    for n in p[1:]:
        numbers[n] += 1
    
    a = []
    b = []
    flag = True
    for i in range(p[0]):
        target = None
        if flag:
            target = a
        else:
            target = b
        for j in range(10):
            if len(target) == 0 and j == 0:
                continue
            if numbers[j] > 0:
                numbers[j] -= 1
                target.append(j)
                break
        flag = not flag

    print(int("".join(map(str, a))) + int("".join(map(str, b))))