문제 설명

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

풀이 과정

1. left를 구간의 왼쪽(포함), right를 구간의 오른쪽(포함 X)으로 둔다.
   • 구간을 왼쪽에서 오른쪽으로 이동시키면서 합계가 M이 되는 구간을 찾는게 목표
2. 만약 구간의 합계가 M보다 크다면, 구간의 합계를 줄여야 하므로 left를 한칸 오른쪽으로 이동시켜서, 구간을 좁힘.
3. 만약 구간의 합계가 M보다 작거나 같다면, 구간의 합계를 늘려야 하므로 right를 한칸 오른쪽으로 이동시켜서 구간을 넓힘.
4. 구간의 합계가 M이라면 갯수를 하나 증가시킨다.

• while문에서 <=로 해야함에 유의. left == right일때도 봐주어야 함. (합계가 0)

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

sequence = list(map(int, input().rstrip().split()))
left = 0
right = 1
sumation = sequence[left]
answer = 0
while left <= right:
    if sumation == M:
        answer += 1

    # 합계가 M보다 크다면 왼쪽에서 하나 끌고와서 빼준다.
    if sumation > M:
        sumation -= sequence[left]
        left += 1
    # 합계가 M보다 작거나 같다면 오른쪽으로 한칸 늘려준다.
    elif sumation <= M:
        if right == N:
            break
        sumation += sequence[right]
        right += 1

print(answer)

문제 설명

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

풀이 과정

• 3차원 BFS 문제이다.

  • 큐에는 [x, y, z, 비용] 형식으로 저장
  • 시작점에서부터 시작하여 동,서,남,북,상,하를 방문하지 않았으면서 길이 있다면 큐에 다음 지점 저장 / 방문 처리
  • 만약 Queue가 비게 된다면 출구를 찾지 못한 케이스이므로 Trapped 출력
  • 만약 Queue에서 뺀 점이 출구라면 몇번 이동하였는지 출력

• 3차원 BFS 문제의 경우는 구현을 많이 신경써야 할 것 같음.. 몇번의 컴파일 에러가 있었음.

소스 코드

import sys
import copy
from collections import deque

input = sys.stdin.readline

def input_matrix(matrix, R):
    floor = [list(input().rstrip()) for _ in range(R)]
    matrix.append(floor)

def get_start_point(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            for k in range(len(matrix[0][0])):
                if matrix[i][j][k] == 'S':
                    return [i, j, k, 0]

while True:
    L, R, C = map(int, input().rstrip().split())
    if L == 0 and R == 0 and C == 0:
        break

    matrix = []
    for _ in range(L):
        input_matrix(matrix, R)
        input() # 1칸 띄워줌

    start = get_start_point(matrix)
    visited = copy.deepcopy(matrix)
    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, 1, -1, 0, 0]
    dz = [0, 0, 0, 0, 1, -1]

    queue = deque([start])
    answer = -1
    while queue:
        x, y, z, cost = queue.popleft()
        if matrix[x][y][z] == 'E':
            answer = cost
            break
        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
            if 0 <= nx and nx < L and 0 <= ny and ny < R and 0 <= nz and nz < C:
                if not visited[nx][ny][nz] == 'O' and matrix[nx][ny][nz] != '#':
                    queue.append([nx, ny, nz, cost+1])
                    visited[nx][ny][nz] = 'O'

    if answer != -1:
        print("Escaped in %d minute(s)."%(answer))
    else:
        print("Trapped!")

문제 설명

문제

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 레슨의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 레슨의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)로 주어진다. 각 레슨의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

풀이 과정

1. blueray의 길이를 절반씩 조사한다.
   • 초기 범위를 레슨들중 최대 길이 ~ 100000 * 10000으로 설정(최대 레슨의 길이 * 최대 레슨의 수)
   • 중간 길이 middle에 대해서
     1. 전체 레슨들을 듣는데 몇개의 blueray가 필요한지 계산
     2. blueray의 개수가 M보다 작거나 같다면, 길이의 최솟값을 구해야 하므로 정답 저장 후 왼쪽 구간에 대해서 진행
     3. blueray의 개수가 M보다 크다면 길이를 늘려야 하므로, 오른쪽 구간에 대해서 진행

틀렸던 점

1. blueray의 초기 범위를 0부터 했다가 틀림.
   • 레슨이 10이라고 할때, blueray를 5 5로 할 수 없음.
2. 처음에는 blueray의 개수가 M과 같을때만 정답에 저장하였으나.. M보다 작거나 같을때로 수정하여야 함.
   • M보다 작다면 맞출 수 있으므로
     • M = 2, [1, 2, 3] 이라고 할 때
     • 예시로 길이가 6일때 [1, 2, 3] 모두 포함되나..
     • 1에다가 blueray 하나를 통째로 주고 [2, 3]에 blueray 하나를 주는 방식으로 두개 맞출수 있음.

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
lessons = list(map(int, input().rstrip().split()))

left = max(lessons)
right = 100000 * 10000

answer = max(lessons)

while left <= right:
    # middle : blueray의 길이
    middle = (left + right) // 2

    blueray = 1
    current = middle

    # blueray의 길이가 middle일때 몇개 나오는지 
    for lesson in lessons:
        if current - lesson < 0:
            blueray += 1
            current = middle - lesson
        else:
            current = current - lesson

    # blueray의 길이가 M보다 작다면 정답 저장 후 blueray를 줄여야 함
    # blueray의 길이가 M보다 크다면 blueray를 늘려야 함
    if blueray <= M:
        answer = middle
        right = middle - 1
    elif blueray > M:
        left = middle + 1

print(answer)

문제 설명

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1= 1, P2= 5, P3= 6, P4= 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1= 5, P2= 2, P3= 8, P4= 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1= 3, P2= 5, P3= 15, P4= 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

풀이 과정

1. 현재 i장의 카드라고 할때, 현재 카드에 도달하기 위해서는
   • i-1장의 카드에서 1장짜리 카드팩 구매
   • i-2장의 카드에서 2장짜리 카드팩 구매
   • ...
2. 따라서, i-k장의 카드의 가격 + k장의 카드 가격이 최대가 되는 값을 dp[i]의 값으로 하면 된다.
3. 위 과정을 1부터 N까지 반복
4. dp[N] 출력

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())

cards = list(map(int, input().rstrip().split()))
dp = [0] * (N+1)
for i in range(1, N+1):
    for idx, cost in enumerate(cards):
        ridx = idx + 1 # enumerate가 0부터 시작하므로 1 더해야..
        if i - ridx >= 0:
            dp[i] = max(dp[i], dp[i-ridx] + cost)
        else:
            break

print(dp[N])

풀이 과정

1. 모든 직업군을 탐색하면서 주어진 언어별 선호도와 직업군 언어 점수의 곱셈의 합을 구한다.
   • 만약, 이 합계가 최대값인 경우 갱신 / 직업군 이름 저장
   • 이 과정에서, 직관적으로 계산하기 위해 파이썬 딕셔너리 활용
   • {직업군명 : 점수} 형식으로 저장
2. 계산시, 개발자가 선호하는 언어에는 있지만, 직업군에서 선호하는 언어에 없을수도 있음.
   • 딕셔너리의 get 메서드를 써서 있는지 확인해주어야 한다.
   • 없는 경우에는 계산 생략
3. 동점인 경우에는 사전순으로 앞서는걸 정답으로 해주어야 한다.

소스 코드

def solution(table, languages, preference):
    answer = ''

    score = {languages[i]: preference[i] for i in range(len(languages))}    
    max_score = 0
    for information in table:
        inf = information.split()
        # 언어별 점수 부여
        current_score = {inf[i]: 6-i for i in range(1, len(inf))}
        total_score = 0
        # 현재 직업에서의 점수 구함
        for lan in score.keys():
            if current_score.get(lan) != None:
                total_score += (current_score[lan] * score[lan])

        # 동점이면 사전순으로 앞서는걸 정답으로
        if total_score == max_score:
            if answer > inf[0]:
                answer = inf[0]

        # 최대 점수일때 갱신
        if total_score > max_score:
            max_score = total_score
            answer = inf[0]

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이 과정

1. 높이가 1 이상 100 이하이므로 높이가 0일때부터 100일때까지 각각 안전한 영역의 개수를 구해보면 된다.
   • 두번의 BFS 과정을 거쳐야 한다.
   • 1. 높이 i일때 i 이하의 각각의 영역들을 잠기게 할때 진행
   • 2. 남아있는 영역들을 하나씩 잠기게 하면서 영역의 개수를 세준다.
2. 영역의 개수를 출력해주면 된다.

소스 코드

import sys
import copy
from collections import deque

input = sys.stdin.readline

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

def bfs(matrix, point, target):
    queue = deque([[point[0], point[1]]])
    visit = int(10e9)
    length = len(matrix)
    matrix[point[0]][point[1]] = visit
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < length and 0 <= ny and ny < length:
                if matrix[nx][ny] != visit and matrix[nx][ny] <= target:
                    matrix[nx][ny] = visit
                    queue.append([nx, ny])

answer = 0
for i in range(0, 101):
    temp_matrix = copy.deepcopy(matrix)

    # 잠기는 모든 부분 잠기도록 처리
    for j in range(N):
        for k in range(N):
            if temp_matrix[j][k] <= i:
                bfs(temp_matrix, [j, k], i)

    # 안잠긴 부분들 한 영역씩 잠기게 하면서 영역의 수 계산
    area_count = 0
    for j in range(N):
        for k in range(N):
            if temp_matrix[j][k] != int(10e9): 
                # 안잠긴 부분이 있다면 해당 영역 잠기도록
                area_count += 1
                bfs(temp_matrix, [j, k], int(10e9))

    answer = max(area_count, answer)

print(answer)

문제

한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.

1. 먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.
2. 만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.
3. 어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문자를 구분치 않는다.
4. 위의 규칙을 첫 번째 옵션부터 N번째 옵션까지 차례대로 적용한다.

입력

첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하의 알파벳으로 표현된다. 단어는 공백 한 칸으로 구분되어져 있다.

출력

N개의 줄에 각 옵션을 출력하는데 단축키로 지정된 알파벳은 좌우에[]괄호를 씌워서 표현한다.

풀이 과정

1. 저장된 알파벳을 넣어둘 set을 하나 만들어 둔다.
2. 각 단어별로 첫글자가 set에 존재하는지 확인
   • 이 때, 대소문자 구분하지 않으므로, 대문자로 모두 치환하여 진행
   • 모든 단어의 첫글자가 set에 존재한다면, 다음 단계로 넘어감.
   • 왼쪽 단어에서부터 진행하면 첫글자가 set에 존재하지 않는다면, 해당 단어를 [첫글자]단어 형태로 바꾸어주고, 첫글자는 set에 저장해준 다음 종료
3. 단어 전체 글자를 왼쪽에서부터 오른쪽으로 진행하면서, set에 존재하는지 확인
   • set에 존재하지 않는다면, 해당 문자를 [문자] 형태로 바꾸어 주고 종료
     • 전체 글자 모두 set에 존재한다면, 그냥 종료

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())

option_set = set()

for _ in range(N):
    options = input().rstrip('\n').split()

    end = False

    for i in range(len(options)):
        if options[i][0].upper() not in option_set:
            option_set.add(options[i][0].upper())
            options[i] = '[' + options[i][0] + ']' + options[i][1:]
            end = True
            break

    if not end:
        for i in range(len(options)):
            for j in range(len(options[i])):
                if options[i][j].upper() not in option_set:
                    option_set.add(options[i][j].upper())
                    options[i] = options[i][:j] + '[' + options[i][j] + ']' + options[i][j+1:]
                    end = True
                    break
            if end:
                break

    print(*options)

문제 설명

문제

Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동혁이는 Java는 프로그램이 느리고, 긴 소스 코드를 갖는 점과 제네릭 배열의 인스턴스화의 무능력을 비웃었다.

또, 김동규와 김동혁은 변수 이름을 짓는 방식도 서로 달랐다. Java에서는 변수의 이름이 여러 단어로 이루어져있을 때, 다음과 같은 방법으로 변수명을 짓는다.

첫 단어는 소문자로 쓰고, 다음 단어부터는 첫 문자만 대문자로 쓴다. 또, 모든 단어는 붙여쓴다. 따라서 Java의 변수명은javaIdentifier,longAndMnemonicIdentifier,name,bAEKJOON과 같은 형태이다.

반면에 C++에서는 변수명에 소문자만 사용한다. 단어와 단어를 구분하기 위해서 밑줄('_')을 이용한다. C++ 변수명은c_identifier,long_and_mnemonic_identifier,name,b_a_e_k_j_o_o_n과 같은 형태이다.

이 둘의 싸움을 부질없다고 느낀 재원이는 C++형식의 변수명을 Java형식의 변수명으로, 또는 그 반대로 바꿔주는 프로그램을 만들려고 한다. 각 언어의 변수명 형식의 위의 설명을 따라야 한다.

재원이의 프로그램은 가장 먼저 변수명을 입력으로 받은 뒤, 이 변수명이 어떤 언어 형식인지를 알아내야 한다. 그 다음, C++형식이라면 Java형식으로, Java형식이라면 C++형식으로 바꾸면 된다. 만약 C++형식과 Java형식 둘 다 아니라면, 에러를 발생시킨다. 변수명을 변환할 때, 단어의 순서는 유지되어야 한다.

재원이는 프로그램을 만들려고 했으나, 너무 귀찮은 나머지 이를 문제를 읽는 사람의 몫으로 맡겨놨다.

재원이가 만들려고 한 프로그램을 대신 만들어보자.

입력

첫째 줄에 변수명이 주어진다. 영어 알파벳과 밑줄('_')로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

입력으로 주어진 변수명이 Java형식이면, C++형식으로 출력하고, C++형식이라면 Java형식으로 출력한다. 둘 다 아니라면 "Error!"를 출력한다.

풀이 과정

• 와.. 쉬운줄 알았는데 예외처리 할게 생각보다 너무 많아서 소스가 되게 길어짐..
• 예외 처리 많이 생각해보기. 많이 틀렸음..

1. 2가지 과정으로 진행한다.
   • 해당 문자열이 C++ 변수명인지 JAVA 변수명인지 ERROR인지 판별
   • C++이나 JAVA라면 각각 JAVA, C++ 변수명으로로 변환시켜 주기
2. C++/JAVA/ERROR 판별
   • 첫글자가 대문자이거나 _ 가 나오는 경우 에러(Ab , b_ )
   • 마지막 글자에 _ 가 나오는 경우 에러(ab_)
   • ' _ ' 가 중복되어 두번 나오면 에러(ab__cd)
   • 대문자와 _ 가 동시에 나오는 경우 에러
   • 이외의 경우에 대해서
     • _ 가 나온 경우 -> c++
     • 대문자가 나온 경우 -> java
3. 판별이 되었다면 문자열을 바꾸어 준다.
   • _ 의 경우는 해당 문자를 없애고 뒷 문자를 대문자로 (C++ -> Java)
   • 대문자의 경우는 _ 문자 + 소문자로 변환 (Java -> C++)

소스 코드

import sys

def mode_check(s):
    upp_count = 0
    underbar_count = 0
    dup = 0
    dup_flag = False

    if len(s) > 0 and s[0].isupper():
        return 'ERROR'


    if len(s) > 0 and s[0] == '_':
        return 'ERROR'

    if len(s) > 0 and s[-1] == '_':
        return 'ERROR'

    for c in s:
        if c.isupper():
            upp_count += 1
            dup = 0
        elif c == '_':
            underbar_count += 1
            dup += 1
            if dup == 2:
                return 'ERROR'
        else:
            dup = 0

    if upp_count != 0 and underbar_count != 0:
        return 'ERROR'

    if underbar_count > 0:
        return 'C'
    else:
        return 'JAVA'

def convert_java_to_cpp(s):
    cv = ''
    for c in s:
        if ord('A') <= ord(c) and ord(c) <= ord('Z'):
            cv += '_'
            cv += c.lower()
        else:
            cv += c

    return cv

def convert_cpp_to_java(s):
    cv = ''
    upper_flg = False
    for c in s:
        if c == '_':
            upper_flg = True
        else:
            if upper_flg:
                cv += c.upper()
                upper_flg = False
            else:
                cv += c

    return cv

variable_name = sys.stdin.readline().rstrip('\n')
mode = mode_check(variable_name)

if mode == 'JAVA':
    print(convert_java_to_cpp(variable_name))
elif mode == 'C':
    print(convert_cpp_to_java(variable_name))
else:
    print('Error!')

BOJ 4458, 첫 글자 대문자 만들기

바로가기

소스 코드

• 문자열의 길이가 0일 때 유의

import sys

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


for _ in range(n):
    k = input().rstrip('\n')
    if len(k) > 0:
        upper = k[0].upper()
        k = upper + k[1:]
        print(k)
    else:
        print('')

BOJ 1357, 뒤집힌 덧셈

바로가기

소스 코드

• rev 함수를 정의(자리수 역순으로 바꾸어주는 함수) ex) 123 -> 321
• 이후 두 입력값에 대해 rev 함수 적용 후 합계에 대해서도 rev 함수 적용

import sys

input = sys.stdin.readline

def rev(x):
    convert = ''
    while x > 0:
        convert += str(x % 10)
        x //= 10

    return int(convert)

X, Y = map(int, input().rstrip().split())
answer = rev(rev(X) + rev(Y))
print(answer)

문제 설명

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

• 다익스트라 알고리즘을 다르게 적용하여서 풀이함.
  • 최소 비용 -> 최대 비용

1. 기본적으로 다익스트라 알고리즘 사용

   • 연결된 노드들 중에서 중량이 최댓값인 노드 선택
   • 해당 노드에 연결된 인접 노드들의 중량 갱신 / 히프에 추가

2. 기존에는 그냥 deque를 사용하였으나.. 시간 초과 문제가 생김.

   • 최대 히프 사용하여 중량이 가장 큰 노드부터 방문
   • 이미 갱신된 경우, 생략하는 과정 추가

3. 목표 지점의 중량 출력

소스 코드

import sys
from collections import deque
import heapq

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, weight = map(int, input().rstrip().split())
    graph[a].append([b, weight])
    graph[b].append([a, weight])

start, end = map(int, input().rstrip().split())

INT_MAX = int(10e9)
distance = [0] * (N+1)
heap = [[-INT_MAX, start]]
distance[start] = INT_MAX

while heap:
    cost, node = heapq.heappop(heap)
    cost = -cost

    # 이미 갱신된 경우라면 생략
    if distance[node] > cost:
        continue

    for next_node, next_cost in graph[node]:
        new_cost = min(cost, next_cost)
        # 기존 무게보다 현재 거쳤을때의 무게가 더 크다면 갱신
        if distance[next_node] < new_cost:
            distance[next_node] = new_cost
            heapq.heappush(heap, [-new_cost, next_node])

print(distance[end])