[백준/Python] 18870. 좌표 압축 & 21736. 헌내기는 친구가 필요해

 

1. 백준 18870. 좌표압축 

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

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
sort_nums = nums.copy()
sort_nums = sorted(list(set(sort_nums)))
dic_sort_nums = {sort_nums[i]: i for i in range(len(sort_nums))}

for i in range(n):
    print(dic_sort_nums[nums[i]], end=' ')

• 단순히 for문을 통해 하나씩 비교하면 당연히... 시간초과가 난다.
• 여러 방식으로 고민하면서 코드를 작성해봐도 방법을 찾지 못했고, 고민이 길어져서 결국 답변을 참고했다.
• python 딕셔너리를! 알면서도 잘 활용하지 못한다. 저번에도 딕셔너리를 통해 풀면 매우 간단한 문제를 두 개의 리스트를 통해 풀려고 하다가 매우 고생한 적이 있다.
• 리스트 2개를 쓰면서 인덱싱이 필요한 경우는 앞으로 꼭 딕셔너리를 생각하자.
• 참고 - sort()의 시간 복잡도 : O(nlog(n)) / dictonary의 value에 접근하는 시간 복잡도 : O(1)

---

 

2. 백준 21736. 헌내기는 친구가 필요해 

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

21736번: 헌내기는 친구가 필요해

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는 N*M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N (1≤ N ≤600), M (1≤M≤600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

from collections import deque
import sys

input = sys.stdin.readline

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

for _ in range(n):
    map.append(list(input()))


for i in range(n):
    for k in range(m):
        if map[i][k] == 'I':
            start = (i, k)

visited = [[0 for _ in range(m)] for _ in range(n)]

count = 0

def bfs():
    global count
    queue = deque()
    queue.append(start)

    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 nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if map[nx][ny] == 'X':
                continue
            if map[nx][ny] == 'O' and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))
            if map[nx][ny] == 'P' and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                count += 1
                queue.append((nx, ny))


bfs()
if count > 0:
    print(count)
else:
    print('TT')

• 처음에 dfs를 통해 구현했는데 재귀에러가 났다.
• 그리고 하소연을 했더니 그래프에서 상, 하, 좌, 우로 이동하는 경우에는 bfs를 쓰니까 외워라! 라는 친절한 조언을 들을 수 있었다. ㅎㅎㅎㅎㅎ
• bfs로 푸니 바로 성공했다!
• 꼭 참고해서 앞으로는 더 빨리 잘 해결할 수 있도록 하자