[Python] 백준 5052, 프로그래머스 성격 유형 검사하기, 백준 13459

1. 문제 - 백준 5052 전화번호 목록

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

 

✅ 내 풀이

from collections import defaultdict

t = int(input())
for _ in range(t):
  dic = defaultdict(int)
  words = set()        # 15번째 줄에서 단어 찾을떄 시간복잡도 줄이기 위해 set 사용 (탐색 -> O(1))
  flag = False
  n = int(input())
  for _ in range(n):
    number = input()
    words.add(number)          # 단어들 set에 추가
    for i in range(1, len(number)+1):    # 가능한 모든 접두어들 딕셔너리에 추가
      dic[number[:i]] += 1
  
  for (k, v) in dic.items():
    if k in words and v>=2:     # 접두어 key중에 단어들 집합에 있고, 2번 이상이라면 접두어가 다른 단어에 포함되어있다는 의미임
        print("NO")
        flag = True
        break

  if not flag:
    print("YES")

 

✅ 다른사람 풀이

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    flag = True
    n = int(input())
    nums = []
    for _ in range(n):
        tmp = input().strip()
        nums.append(tmp)
    nums.sort()
    for n1, n2 in zip(nums, nums[1:]):
        if n2.startswith(n1):
            flag = False
            print("NO")
            break
    if flag:
        print("YES")

 

1) num.sort() --> 예를들어 "123", "12345" 일때 접두어인 "123"은 "12345"보다 앞에 오게되고, 둘은 인접하게 되므로 먼저 정렬하면 비교하는 데 시간복잡도를 줄일 수 있다.

2) for n1, n2 in zip(nums, nums[1:]):  --> 인접한 두 수 끼리 비교할 수 있도록 하게해줌

nums = ["119", "1195524421", "97674223"]

zip(nums, nums[1:])
# [("119", "1195524421"), ("1195524421", "97674223")]

 

2. 문제 - 프로그래머스 성격 유형 검사하기

https://school.programmers.co.kr/learn/courses/30/lessons/118666

 

✅ 내 풀이

from collections import defaultdict

def solution(survey, choices):
    dic = defaultdict(int)
    jipyos = [("R", "T"), ("C", "F"), ("J", "M"), ("A", "N")]
    
    for i, s in enumerate(survey):
        if choices[i] < 4:
            dic[s[0]] += 4 - choices[i]
        elif choices[i] > 4:
            dic[s[1]] += choices[i] - 4
        
    answer = ''
    for a, b in jipyos:
        if dic[a] >= dic[b]:
            answer += a
        else:
            answer += b
    
    return answer

 

3. 백준 13459 - 구슬탈출

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

 

from collections import deque

n, m = map(int, input().split())
board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]

for i in range(n):
  board.append(list(input()))
  for j in range(m):
    if board[i][j] == "R":
      red_cur_x, red_cur_y = i, j
    if board[i][j] == "B":
      blue_cur_x, blue_cur_y = i, j

def move(x, y, i):

  count = 0
  
  while True:
    if board[x+dx[i]][y+dy[i]] == "#" or board[x][y] == "O":
      return x, y, count
    x += dx[i]
    y += dy[i]
    count += 1

q = deque([(red_cur_x, red_cur_y, blue_cur_x, blue_cur_y, 1)])
visited[red_cur_x][red_cur_y][blue_cur_x][blue_cur_y] = True

while q:
  red_x, red_y, blue_x, blue_y, n = q.popleft()

  if n > 10:
    break
    
  for i in range(4):
    red_nx, red_ny, red_count = move(red_x, red_y, i)
    blue_nx, blue_ny, blue_count = move(blue_x, blue_y, i)
        
    if board[blue_nx][blue_ny] == 'O':
      continue    
      # 예제 7을 보면 아래에서 겹치지 않게 처리하기 전에 파란색 구슬이 빠지면 실패 처리하므로 
      # 겹치지 않게 처리하기 전에 먼저 실패처리

    # 파란 구슬이 빠지지 않고, 빨간 구슬이 빠지면 성공처리
    if board[red_nx][red_ny] == 'O':
      print(1)
      exit(0)

    if red_nx == blue_nx and red_ny == blue_ny:
      if red_count > blue_count:
        red_nx -= dx[i]
        red_ny -= dy[i]
      else:
        blue_nx -= dx[i]
        blue_ny -= dy[i]

    if not visited[red_nx][red_ny][blue_nx][blue_ny]:
      q.append((red_nx, red_ny, blue_nx, blue_ny, n+1))
      visited[red_nx][red_ny][blue_nx][blue_ny] = True

print(0)

 

오늘 배운 점

1. 한 단어가 다른 단어의 접두어로 포함되어있다면 --> 정렬 시 인접하게 되어 시간복잡도를 줄일 수 있다.

2. zip(iterable1, iterabel2) --> 이터레이블한 객체 2개를 밭아 각각의 쌍을 튜플 리스트로 만들어 순환할 수 있도록 한다.

numbers = [1, 2, 3]
letters = ["A", "B", "C"]
for pair in zip(numbers, letters):
     print(pair)
# (1, 'A')
# (2, 'B')
# (3, 'C')