4/18 Coding Test

✅ BOJ IT 기업 문제 풀이

🎈 8979 올림픽 - 단순 구현

각 국가의 금, 은, 동메달 정보를 입력받아 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하는 문제로 다음 조건을 거쳐 순위가 결정되고 조건은 다음과 같다.

• 금메달 수가 더 많은 나라
• 금메달 수가 같으면 은메달 수가 더 많은 나라
• 금, 은메달 수가 같으면 동메달 수가 더 많은 나라
  입출력은 다음과 같다.
• 입력: 첫 줄에 국가 수 N, 등수를 알고 싶은 국가가 빈칸을 사이에 두고 주어진다. 이후 각 국가별 번호와 금, 은, 동메달 수가 주어진다.
• 출력: 입력받은 국가 K의 등수를 출력

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
rank = []
for _ in range(n):
    rank.append(list(map(int, input().split())))
rank.sort(key = lambda x : (x[1], x[2], x[3]), reverse = True)
for i in range(n):
    if rank[i][0] == k:
        idx = i
for i in range(n):
    if rank[idx][1:] == rank[i][1:]:
        print(i+1)
        break

< 풀이 과정 >
for 문으로 인덱싱과 if 조건문을 통해 구현하는 문제
rank 리스트를 만들어 입력값을 정리하고, 금, 은, 동 순서대로 내림차순으로 정렬해준다.
이후 for문으로 입력받은 k와 같은 인덱스를 idx로 저장한 후 해당 번호를 이용해 금, 은, 동메달 수가 같은 조건을 걸어준다. (은메달, 동메달 수가 0이고 금메달 수가 모두 동일한 경우 idx 순서의 금은동과 i번째 금은동이 같으므로 공동 i+1등 표시 처리를 위해 for문 추가 진행 必)

🎈 20006 랭킹전 대기열

플레이어수, 플레이어 닉네임, 플레이어 레벨, 한 개의 정원이 주어질 때 아래와 같은 방법으로 매핑하여 최종적으로 만들어진 방 상태와 입장 플레이어들을 출력하는 프로그램 작성하는 문제
조건은 아래와 같다.

• 플레이어가 입장 신청할 때 매칭 가능한 방이 없다면 새로운 방 생성 후 입장 (해당 방에는 처음 입장한 플레이어 레벨 기준 +-10 까지 입장 가능)
• 입장 가능한 방이 있으면 방의 정원이 찰 때 까지 대기
• 먼저 생성된 방에 입장, 방의 정원이 모두 차면 게임 시작
  입출력은 다음과 같다.
• 입력 : 첫 줄에 플레이어 수 p, 방의 정원 m이 주어지고 이후 p줄 만큼 플레이어 레벨 l과 닉네임 n이 공백을 두고 주어진다.
• 출력 : 방이 시작되면 Started!, 대기 중이면 Waiting, 모든 생성된 방에 대해 게임 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력하는 문제

import sys
input = sys.stdin.readline

p, m = map(int, input().split())
# 이중리스트 생성
rooms = []
for _ in range(p):
    level, nickname = input().rstrip().split()
    level = int(level)
    # 현재 방에 인원이 없으면 처음 인원 넣어주고 continue처리
    if not rooms:
        rooms.append([[level, nickname]])
        continue
    # 방 정원 여부 
    check = False
    for room in rooms:
    	# 정원이 미달이거나, 레벨 [-10, +10]인 경우만 같은 방에 추가
        if len(room) < m and room[0][0]-10 <= level <= room[0][0]+10:
            room.append([level, nickname])
            check = True
            break
    # 만약 위 조건 미달인 경우, 새로운 방에 해당 인원 추가
    if not check:
        rooms.append([[level, nickname]])
# 각 방마다 닉네임 기준 정렬
for room in rooms:
    room.sort(key = lambda x: x[1])
# 각 방마다 정원 꽉 찼는지 여부로 출력해주고 이후 레벨, 닉네임 순차적으로 출력
for room in rooms:
    if len(room) == m:
        print('Started!')
    else:
        print('Waiting!')
    for l, n in room:
        print(l, n)

< 풀이 과정 >
이중리스트를 얼마나 잘 다루는 가에 대해 구현하는 문제
처음 방에 들어온 사람의 레벨을 기준으로 정원 미달여부, 레벨 충족여부를 두고 같은 방에 넣어주고 조건에 충족되지 않는 사람에 한해 새로운 방에 넣어준다.
이후 각 방마다 닉네임으로 정렬하여 미달 조건여부로 출력을 다르게 해주고, 사람마다 레벨, 닉네임을 출력해주는 문제

🎈 15989 1, 2, 3 더하기 4

정수 n이 주어졌을 때 1, 2, 3의 합으로 정수 n을 나타내는 방법의 수를 구하는 문제로 입출력은 다음과 같다

• 입력 : 첫 줄에 테케 수가 주어지고 이후 테케 수만큼 정수 n이 주어진다.
• 출력 : 각 테케마다 주어진 정수 n을 1,2,3 의 합으로 나타내는 방법의 수를 출력

import sys
input = sys.stdin.readline
dp = [1]*10001
for i in range(2, 10001):
    dp[i] += dp[i-2]
for i in range(3, 10001):
    dp[i] += dp[i-3]
t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n])

< 풀이 과정 >
DP 문제
우선 모든 양수는 정수 1의 합으로만 표현이 가능하므로 모든 dp는 1로 채워진다.
이후 1, 2를 이용하여 모든 정수를 표현하는 방법의 점화식은 i-2번째를 더해주면 되고
이후 3까지 활용한다면 i-3번째도 더해준 값으로 표현할 수 있다.

🎈 13549 숨바꼭질 3

A는 현재 점 N에 있고 B가 점 K에 있을 때 A는 1초 후 N-1, N+1 혹은 0초 후에 2*X로 이동한다고 한다. N에서 K로 이동하는 가장 빠른 시간을 구하는 문제

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

n, k = map(int, input().split())
def bfs(n, k):
    visited = [0] * 100001
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:
            return visited[k]
        for next in (x-1, x+1 ,2*x):
            if 0<=next<100001 and not visited[next]:
                if next == 2*x and next != 0:
                    visited[next] = visited[x]
                    queue.appendleft(next)
                else:
                    visited[next] = visited[x] + 1
                    queue.append(next)
print(bfs(n, k))

< 풀이 과정 >
위치 n에서 k로 이동하는 최단 시간을 구하는 BFS 탐색 문제
BFS로 구현하였고, 큐에서 꺼낸 위치가 K인 경우 방문하는데 소요한 시간을 출력한다.
다음 위치를 x-1, x+1, 2x중 고르고, 주어진 범위 내 방문하지 않은 곳에 한해 경로를 탐색한다.
만일 다음 위치가 2x이고 0이 아니라면, 다음 위치를 시간 소요없이 그대로 쓰고 queue에 제일 왼쪽에 넣어 우선순위를 부여해준다.
아닌 경우 일반적인 BFS 탐색 진행!

🎈 20055 컨베이어 벨트 위의 로봇 (해결 완료✍️)

위 그림과 같이 길이가 총 2N인 벨트에서 N만큼의 컨베이어 벨트가 존재한다. 이떄 1번 칸은 올리는 위치, N번 칸은 내리는 위치라고 할 때 이 벨트를 이용하여 로봇을 옮기려고 한다. 각 칸에는 내구도가 주어지고 내구도가 0인 순간 해당 칸은 소모할 수 없다
로봇을 옮기는 과정은 다음과 같이 순차적으로 일어난다.

• 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸씩 회전
• 2. FIFO로 로봇은 이동하며 만약 이동하지 못하면 가만히 있는다.
• 2-1. 로봇이 이동하기 위해선, 다음 칸의 로봇이 없어야 하고 내구도가 1이상이어야 한다.
• 3. 올리는 위치에 있는 칸의 내구도가 0이 아니여야만 올리는 위치에 로봇을 올릴 수 있다.
• 4. 내구도가 0인 칸의 개수가 K개 이상이면 과정을 종료, 아니면 1번부터 다시 진행
     N, K가 입력으로 주어질 때 몇 단계를 거쳐 종료되는지 출력하는 문제

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

n, k = map(int ,input().split())
# 주어진 컨베이어 벨트와 robot을 deque로 입력
belt = deque(map(int, input().split()))
robot = deque([0]*n)
answer = 0

while True:
	# 맨 뒤를 맨 앞으로 옮기며 주어진 그림대로 진행
    belt.rotate(1)
    robot.rotate(1)
    # 로봇의 끝 값 0 처리 (로봇 빠져나감)
    robot[-1] = 0
    # 주어진 컨베이어 벨트 위에 로봇이 존재하면,
    if sum(robot):
    	# 1번 칸, N번 칸 제외하고 뒤 부터 탐색 진행해
        for i in range(n-2, -1, -1):
        	# 현위치 로봇있고, 다음 위치에 로봇 없고 다음 칸의 내구도가 1이상인 경우만 처리
            if robot[i] == 1 and robot[i+1] == 0 and belt[i+1] >= 1:
                robot[i] = 0
                robot[i+1] = 1
                belt[i+1] -= 1
        robot[-1] = 0
    # 로봇 들어올 조건 만족하면 처리 (벨트는 내구도 - 1)
    if robot[0] == 0 and belt[0] >= 1:
        robot[0] = 1
        belt[0] -= 1
    # 과정 + 1
    answer += 1
    # 주어진 벨트 내 각 칸의 내구도가 0인 것이 K개 이상이 되면 종료
    if belt.count(0) >= k:
        break
print(answer)

< 풀이 과정 >
deque 자료구조와 queue를 통해 rotate함수를 이용하여 해결하였다.
주어진 컨베이어 벨트는 길이가 2N이고 로봇이 위치할 수 있는 칸은 최대 N개이다.

• 이를 각각 deque으로 구성해주고 while문으로 반복하며 각 deque에 rotate를 진행한다.

• 로봇이 현재 벨트 위에 존재하면 1번칸, N번칸을 제외하고 뒤부터 인덱스를 i로 둔다. 이후 현위치에 로봇이 있고 다음 위치에 로봇이 없는 조건에서 다음 칸의 내구도가 1이상인 경우에만 로봇을 한 칸씩 옮겨준다.

• 로봇이 들어올 조건도 걸어주고 로봇 추가

• 최종적으로 주어진 벨트 내 각 칸의 내구도가 0인 것들의 개수가 k개 이상이면 while문을 종료하고 과정 수인 answer를 리턴한다.