[Python] 배열에 기록하여 문제 풀기

배열의 적절한 위치에 원하는 값을 기록하여 문제를 해결한다.

 

1. 시간과 위치

- A와 B가 1초에 1m씩 움직인다.

- A는 5초 동안 앞으로 갔다가 4초 동안 뒤로 가고 3초 동안 앞으로 간다.

- B는 3초 동안 뒤로 갔다가 7초 동안 앞으로 가고 2초 동안 뒤로 간다.

- A와 B가 만나게 되는 지점은 몇 초일까?

 

 

 

- A와 B가 만나기 위해서는 시간과 위치가 같아지는 시점이 생겨야 한다.

- 위치만 표시하게 되면 A와 B가 언제 만나는지 알기 쉽지 않다.

 

- 다른 방법으로는 1초 단위로 A와 B의 위치를 동시에 움직이며 시뮬레이션을 한다.

- 하지만 시간에 따라 어느 방향으로 이동하는 것을 판단해야 하므로 쉽지 않다.

 

- 따라서 A, B를 개별적으로 1초 단위로 어느 위치에 있는지 배열에 기록하며 문제를 해결한다.

- 시간과 위치가 일치하는 시점이 답이 된다.

- 이는 A, B의 기록된 배열의 인덱스가 i일 때, a [i]와 b [i]가 최초로 값이 같은 i가 답이 된다.

 

- 1초 단위의 위치 배열은 다음과 같다.

 

1-1. 코드로 나타내기

- A와 B가 각각 n번, m번 주어진 방향으로 시간만큼 이동한다고 하자.

- n과 m을 입력하고 n번 d, t를 입력하고 m번 d, t를 입력한다.

- d는 방향이고 L 또는 R이며 각각 왼쪽, 오른쪽을 나타낸다.

- t는 d 방향으로 이동한 시간을 의미한다.

- A와 B는 총 이동한 시간이 같다고 가정한다.

- 만약 만나지 않는다면 -1을 출력한다.

 

n, m = map(int, input().split())
pos_a, pos_b = [0], [0]
a_curr, b_curr = 0, 0


def distance_over_time(number, curr, pos):
    for _ in range(number):
        d, t = input().split()
        t = int(t)
        if d == 'R':
            arr = [curr+i for i in range(1, t+1)]
            curr += t
            pos += arr
        else:
            arr = [curr-i for i in range(1, t+1)]
            curr -= t
            pos += arr
    return pos


pos_a = distance_over_time(n, a_curr, pos_a)
pos_b = distance_over_time(m, b_curr, pos_b)

ans = -1
for i in range(1, len(pos_a)):
    if pos_a[i] == pos_b[i]:
        ans = i
        break

print(ans)

 

>> 3 3
>> R 5
>> L 4
>> R 3
>> L 3
>> R 7
>> L 2
8

 

 

- A와 B의 1초마다 이동한 후 현재 시점을 각각 배열에 기록할 변수를 지정한다. (pos_a, pos_b)

- A와 B의 현재 위치를 저장하는 변수를 지정한다. (a_curr, b_curr)

 

- n번 또는 m번만큼 방향과 시간을 입력하면 1초마다 현재 위치를 배열에 저장해야 한다.

- d가 R일 때, 오른쪽으로 이동해야 하므로 반복문을 통해 현재 위치를 1부터 t만큼 더한 t개의 값을 저장한 배열을 생성한다. (arr)

- 현재 위치는 t만큼 더하고 pos_a 또는 pos_b에 arr을 합친다.

 

- d가 L일 때, 왼쪽으로 이동해야 하므로 반복문을 통해 현재 위치를 1부터 t만큼 뺀 t개의 값을 저장한 배열을 생성한다. (arr)

- 현재 위치는 t만큼 빼고 pos_a 또는 pos_b에 arr을 합친다.

 

- 출력해야 하는 값인 A와 B가 최초로 만나는 시점을 초기값으로 -1로 지정한다. (ans)

- 인덱스가 1부터 (pos_a 또는 pos_b의 길이-1)까지 반복문을 통해 동일한 인덱스일 때 값이 같으면 그때의 인덱스를 ans에 저장한다.

- 만약 같지 않다면 초기값인 -1이 출력될 것이다.

 

 

Q) 달리기 시합 중계

- A와 B가 시작점에서 같은 방향으로 출발한다. 방향은 바꾸지 않는다.

- A는 n번, B는 m번 특정 속도로 특정 시간만큼 이동한다.

- 예를 들어, 2 4라면 4시간 동안 2의 속도를 유지한다는 것을 의미한다.

- 이 시합은 현재 1등으로 달리는 선수를 방송 화면에 출력해야 한다.

- 경기 시작 1시간 후 현재 1등으로 달리는 선수와 시간을 출력한다.

- 이후에는 1등이 바뀔 때만 1등인 선수와 시간을 출력한다.

- 만약 1등이 2명이 된다면 바뀐 것으로 간주한다.

- 마지막으로 1등이 몇 번 바뀌었는지 출력한다.

- 이동 시간은 A와 B 동일하다.

 

def total_distance(move, dist_list, curr_dist):
    for _ in range(move):
        x, y = map(int, input().split())
        for _ in range(y):
            curr_dist += x
            dist_list.append(curr_dist)
    return dist_list


def compare_answer(idx):
    if a[idx] > b[idx]:
        code = 'a'
    elif a[idx] < b[idx]:
        code = 'b'
    else:
        code = 'c'
    return code


def print_1st(code, time):
    if code == 'a':
        print(f'time : {time}, 1st is a')
    elif code == 'b':
        print(f'time : {time}, 1st is b')
    else:
        print(f'time : {time}, 1st is a and b')


n, m = map(int, input().split())
a, b = [], []
a_dist, b_dist = 0, 0
a = total_distance(n, a, a_dist)
b = total_distance(m, b, b_dist)

cnt = 1
pre_code = compare_answer(0)

print_1st(pre_code, 1)

for i in range(1, len(a)):
    code = compare_answer(i)
    if pre_code != code:
        print_1st(code, i+1)
        cnt += 1
    pre_code = code

print(f'1st change count {cnt}')

 

>> 5 5
>> 1 2
>> 3 3
>> 2 5
>> 1 3
>> 3 2
>> 2 4
>> 1 2
>> 2 2
>> 4 3
>> 3 4
time : 1, 1st is b
time : 4, 1st is a and b
time : 5, 1st is a
time : 10, 1st is b
1st change count 4

 

 

- 각 시간에 따른 총 이동 거리를 배열에 저장한다. (a, b)

- 예를 들어, a [i]는 A가 i+1 시간까지의 이동한 거리를 의미한다.

 

● total_distance 함수

- A, B에 각각 n, m번 특정 속도와 시간이 입력된다.

- curr_dist는 현재 시간 동안 이동한 거리, dist_list는 1시간 단위로 curr_dist를 원소로 가지는 리스트이다.

- 입력한 시간을 통해 반복문으로 1부터 입력한 시간까지 curr_dist를 입력한 속도만큼 더한다.

- 동시에 속도만큼 더한 현재 이동거리를 dist_list에 삽입한다.

- 따라서 dist_list에 i번째 원소는 i+1 시간 동안 이동한 거리를 알 수 있다.

- dist_list를 반환하여 A, B가 시간 별로 이동한 거리의 리스트를 알 수 있다.

 

● compare_answer 함수

- A, B의 같은 시간에서 이동한 거리를 비교한다.

- 즉, a [i]와 b [i]를 비교하여 a [i]가 클 때, b [i]가 클 때, 두 값이 같을 때 각각 문자 a, b, c를 반환하도록 한다.

 

● print_1st 함수

- 1등인 사람과 그때의 시간을 출력한다.

- 출력은 경기 시작 후 1시간, 1등이 변경되었을 때만 한다.

 

- pre_code는 1등이 변경되었을 때 print_1st를 사용해야 하기 때문에 이를 판별하기 위한 변수이다.

- 즉 이전 시간의 비교값이고, 경기 시작 1시간 후 1등을 출력하려면 a, b의 index가 0인 값을 비교하여 출력한다.

- 나머지는 1등이 변경되었을 때만 출력하기 때문에, 1부터 a의 길이 또는 b의 길이의 1을 뺀 값까지 반복문을 실행한다.

- a [index]와 b [index]를 compare_answer로 비교하고 반환값을 code에 저장한다.

- code와 pre_code가 다르면 1등이 바뀐 것이므로 print_1st를 실행하고 바뀐 횟수를 1 증가한다.

- 반복문이 한번 실행될 때마다 pre_code는 code로 갱신한다.

- 마지막으로 바뀐 횟수를 출력한다.

 

 

Q) 만남은 반가워.

- A, B가 다리 위에서 1초에 한 칸씩 좌우로 움직인다. 

- A, B가 움직이는 횟수는 각각 n, m이다. 

- A, B는 처음에 같은 지점에서 움직이고 같은 위치에 있으면 하이파이브를 한다. 

- 단, 하이파이브는 바로 직전에 다른 위치에 있어야 한다. 

- A, B가 직전 위치와 현재 위치가 같으면 손을 잡고 같이 걸어간다. 

- 움직임을 종료한 A 또는 B는 현재 위치에 계속 머무른다. 

- A, B가 이동을 마치면 하이파이브 횟수와 손을 잡고 같이 걸어간 횟수를 출력하라.

- 입력은 n, m을 입력하고 n 줄의 시간과 이동, m 줄의 시간과 이동을 입력하라.

- 예를 들어, 2 L 이면 2초 동안 왼쪽으로 이동하는 의미이다.

- 3 R 이면 3초 동안 오른쪽으로 이동하는 의미이다.

 

def total_move(player_position, curr, move_count):
    for _ in range(move_count):
        d, r = input().split()
        d = int(d)
        if r == 'L':
            for i in range(curr-1, curr-d-1, -1):
                player_position.append(i)
            curr -= d
        else:
            for i in range(curr+1, curr+d+1):
                player_position.append(i)
            curr += d
    return player_position


n, m = map(int, input().split())
curr_a, curr_b = 0, 0
a, b = [], []

a = total_move(a, curr_a, n)
b = total_move(b, curr_b, m)

if len(a) < len(b):
    for _ in range(len(b)-len(a)):
        a.append(a[-1])
else:
    for _ in range(len(a)-len(b)):
        b.append(b[-1])

hifive_cnt, join_hands_cnt = 0, 0
for i in range(len(a)):
    if i >= 1 and a[i] == b[i] and a[i-1] != b[i-1]:
        print(f'time {i+1} hifive')
        hifive_cnt += 1
    elif i >= 1 and a[i] == b[i] and a[i-1] == b[i-1]:
        print(f'time {i+1} join_hands')
        join_hands_cnt += 1

print(f'total hifive : {hifive_cnt}, join_hands : {join_hands_cnt}')

 

>> 5 5
>> 3 R
>> 3 L
>> 5 R
>> 1 L
>> 4 L
>> 3 L
>> 4 R
>> 1 R
>> 2 L
>> 2 R
time 6 hifive
time 7 join_hands
time 8 join_hands
time 14 hifive
total hifive : 2, join_hands : 2

 

 

 

- A, B가 현재 있는 위치를 변수 curr_a, curr_b라 한다.

 

● total_move 함수

- A는 n번, B는 m번 시간과 방향을 입력받는다.

- 방향이 L 왼쪽이면 현재 위치에서 왼쪽으로 이동하며 위치를 player_position 리스트에 삽입하고 현재 위치를 갱신한다.

- 방향이 R 오른쪽이면 현재 위치에서 오른쪽으로 이동하며 위치를 player_position 리스트에 삽입하고 현재 위치를 갱신한다.

- player_position을 반환하여 A, B의 시간별로 이동한 위치를 알 수 있다.

 

- 만약 a, b가 이동한 시간이 다를 경우 또는 a, b 리스트의 길이가 다른 경우 리스트 길이를 동일하게 만든다.

- 길이가 더 짧은 리스트에서 마지막 위치를 더 삽입하여 긴 리스트의 길이와 동일하게 만든다.

 

- 하이파이브와 손을 맞잡은 횟수의 변수를 지정한다. (hifive_cnt, join_hands_cnt)

- a 또는 b의 길이만큼 반복문을 수행해 동일한 index일 때 값이 같고 직전 index일 때 다르면 hifive_cnt를 1 증가한다.

- 반면, 직전 index도 같으면 join_hands_cnt를 1 증가한다.

- 각각의 경우에 시간과 수행한 명령을 출력한다.

- 하이파이브와 손을 맞잡은 횟수를 출력한다.

 

2. 유지하는 정보를 배열로 관리하기

Q) 벌칙 당첨

- n명의 학생이 있고 학생은 1번부터 n번까지 있다.

- m번 동안 n명의 학생이 교실에 오는 순서를 입력한다.

- 마지막으로 등교하는 학생은 벌점 1점을 부과한다.

- 벌점이 처음으로 k점이 되는 학생은 학생들에게 치킨을 쏴야 하는 벌칙이 있다.

- 벌칙을 수행하는 학생을 구하여라.

 

n, m, k = map(int, input().split())
arr = [0 for _ in range(n+1)]
penalty = []
for _ in range(m):
    order = list(map(int, input().split()))
    arr[order[n-1]] += 1
    if arr[order[n-1]] == k:
        penalty.append(order[n-1])

if len(penalty) == 0:
    print('벌칙을 받을 학생이 없습니다.')
else:
    print(f'벌칙을 받을 사람은 {penalty[0]}번 학생입니다.')

 

>> 7 10 3
>> 6 1 7 3 4 5 2
>> 7 1 6 3 2 4 5
>> 4 2 7 1 3 6 5
>> 5 7 4 2 3 1 6
>> 4 5 1 7 6 2 3
>> 5 4 2 6 7 3 1
>> 7 1 4 3 2 6 5
>> 5 6 3 4 2 1 7
>> 6 5 4 7 3 1 2
>> 4 2 3 5 1 7 6
벌칙을 받을 사람은 5번 학생입니다.

 

 

- arr은 벌점을 표기하는 배열이다. 예를 들어, arr [3]이 2이면 3번 학생이 벌점이 2점이라는 의미이다.

- penalty는 벌점이 k점이 된 학생들을 모아 놓은 리스트이다.

- m번 동안 교실에 온 순서대로 n명의 학생들을 입력한다. (order)

- order 리스트의 제일 마지막의 원소 값이 마지막으로 등교한 학생이다. (order [n-1])

- arr에 order [n-1] 번째 값을 1 증가한다.

- 만약 그 값이 k가 된다면 학생 order [n-1]은 penalty에 삽입된다.

- penalty의 길이가 0이라면 벌칙을 받는 학생이 없다는 것을 의미한다.

- 그렇지 않다면 penalty에 0번째 index인 값을 출력한다.

 

 

Q) 바이러스 감염자

- n명의 사람들이 있고 이 중 1명이 신종 바이러스에 감염되었다.

- 신종 바이러스는 사람들에게 전파할 수 있고 이로 인한 바이러스 감염자들을 찾아야 한다.

- 감염자와 만나면 무조건 바이러스에 감염된다.

- 기록을 통해 서로 만난 사람과 시간을 알 수 있다.

- 예를 들어 10 3 4라고 하면 10초에 3번과 4번이 만났다는 의미이다.

- 정보는 m개가 있고 최초 감염자는 k번이다.

- 또한 바이러스의 특이점은 최대 h번 옮길 수 있다.

- h가 3이라면 감염자가 바이러스를 옮길 수 있는 횟수가 3번이라는 의미이고 그 이후에 만나는 사람들은 감염되지 않는다.

- 감염된 사람들은 총 몇 명이고 누구인지 출력한다.

- 단, 감염된 사람들끼리 만나면 옮긴 횟수에 포함되고, 옮긴 횟수는 증가하지 않는다.

- 입력은 n, m, k, h이고 정보의 시간은 각각 다르다.

 

def make_diseases(a, b):
    if virus_count[a] != 0:
        ans[b] = 1
        virus_count[a] -= 1


n = int(input('사람들은 총 몇 명인가요? '))
t = int(input('사람들과 만난 정보는 총 몇개가 있나요? '))
k, h = map(int, input('최초 감염자 번호와 바이러스는 몇 번 옮길 수 있나요? ').split())
info = []
for _ in range(t):
    time, x, y = map(int, input().split())
    info.append((time, x, y))
info.sort()

ans = [0 for _ in range(n+1)]
ans[k] = 1
virus_count = [h for _ in range(n+1)]
for time, x, y in info:
    if ans[x] == 1 and ans[y] == 1:
        make_diseases(x, y)
        make_diseases(y, x)
    elif ans[x] == 1:
        make_diseases(x, y)
    elif ans[y] == 1:
        make_diseases(y, x)

cnt = 0
infected_info = str()
for idx, val in enumerate(ans):
    if val == 1:
        infected_info += str(idx)+' '
        cnt += 1
print(f'감염자는 {infected_info}이며 총 {cnt}명이다.')

 

>> 사람들은 총 몇 명인가요? 5
>> 사람들과 만난 정보는 총 몇개가 있나요? 5
>> 최초 감염자 번호와 바이러스는 몇 번 옮길 수 있나요? 4 3
>> 10 1 4
>> 8 3 5
>> 17 2 4
>> 14 4 5
>> 5 3 4
감염자는 1 3 4 5 이며 총 4명이다.

 

 

- 서로 만난 사람의 번호와 시간을 입력하고 정보를 info에 삽입한다.

- info를 시간을 기준으로 오름차순 정렬을 한다.

 

- ans 리스트를 만들어 감염 여부를 확인한다. 0으로 초기화한다.

- ans [2]가 1이라면 2번 사람이 감염이 되었다는 의미이다.

- 0이라면 그 사람은 감염이 되지 않았다는 의미이다.

- virus_count는 각 사람이 바이러스를 전달할 수 있는 횟수를 의미한다.

 

● make_diseases 함수

- 만난 두 사람 중 한 사람이라도 감염되었으면 실행한다.

- virus_count의 값이 0이면 바이러스를 전달할 수 없으므로 감염되지 않는다.

- 그렇지 않으면 바이러스를 감염시키고 받는 사람의 ans를 1로 갱신하며 주는 사람의 virus_count를 1 감소한다.

 

- info의 데이터와 make_diseases를 사용해 감염이 확산되는지 알 수 있다.

- 서로 만난 두 명 모두 감염된 경우, 두 명의 virus_count가 1 감소한다.

- 한 명만 감염된 경우, 바이러스를 다른 사람에게 감염시킨다.

 

- ans를 반복문을 통해 감염된 사람들의 정보를 알기 위해 값이 1인 index를 출력한다.

- cnt를 1 증가시켜 감염자들의 전체 인원수를 출력한다.