λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Algorithm/BOJ

[BOJ] μΆ”μ›” (#2002)

 

 

문제 

 

λŒ€ν•œλ―Όκ΅­μ„ λΉ„λ‘―ν•œ λŒ€λΆ€λΆ„μ˜ λ‚˜λΌμ—μ„œλŠ” 터널 λ‚΄μ—μ„œμ˜ μ°¨μ„  변경을 법λ₯ λ‘œ κΈˆν•˜κ³  μžˆλ‹€. 쑰금만 κ΄€μ°°λ ₯이 μžˆλŠ” 학생이라면 터널 λ‚΄λΆ€μ—μ„œλŠ” 차선이 νŒŒμ„ μ΄ μ•„λ‹Œ μ‹€μ„ μœΌλ‘œ λ˜μ–΄ μžˆλ‹€λŠ” 것을 μ•Œκ³  μžˆμ„ 것이닀. μ΄λŠ” 차선을 λ³€κ²½ν•  수 μ—†μŒμ„ λ§ν•˜λŠ” 것이고, λ”°λΌμ„œ 터널 λ‚΄λΆ€μ—μ„œμ˜ 좔월은 λΆˆκ°€λŠ₯ν•˜λ‹€.

μ†Œλ¬Έλ‚œ λͺ…μ½€λΉ„ κ²½μ°° λŒ€κ·Όμ΄μ™€ μ˜μ‹μ΄κ°€ μΆ”μ›”ν•˜λŠ” μ°¨λŸ‰μ„ 작기 μœ„ν•΄ ν•œ 터널에 νˆ¬μž…λ˜μ—ˆλ‹€. λŒ€κ·Όμ΄λŠ” ν„°λ„μ˜ μž…κ΅¬μ—, μ˜μ‹μ΄λŠ” ν„°λ„μ˜ μΆœκ΅¬μ— 각각 μž λ³΅ν•˜κ³ , λŒ€κ·Όμ΄λŠ” μ°¨κ°€ 터널에 λ“€μ–΄κ°€λŠ” μˆœμ„œλŒ€λ‘œ, μ˜μ‹μ΄λŠ” μ°¨κ°€ ν„°λ„μ—μ„œ λ‚˜μ˜€λŠ” μˆœμ„œλŒ€λ‘œ 각각 μ°¨λŸ‰ 번호λ₯Ό 적어 λ‘μ—ˆλ‹€.

N개의 μ°¨λŸ‰μ΄ μ§€λ‚˜κ°„ ν›„, λŒ€κ·Όμ΄μ™€ μ˜μ‹μ΄λŠ” μžμ‹ λ“€μ΄ 적어 λ‘” μ°¨λŸ‰ 번호의 λͺ©λ‘μ„ 보고, 터널 λ‚΄λΆ€μ—μ„œ λ°˜λ“œμ‹œ 좔월을 ν–ˆμ„ κ²ƒμœΌλ‘œ μ—¬κ²¨μ§€λŠ” 차듀이 λͺ‡ λŒ€ μžˆλ‹€λŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλ‹€. λŒ€κ·Όμ΄μ™€ μ˜μ‹μ΄λ₯Ό 도와 이λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•΄ 보자.

 
 
μž…λ ₯ 
 

μž…λ ₯은 총 2N+1개의 μ€„λ‘œ 이루어져 μžˆλ‹€. 첫 μ€„μ—λŠ” 차의 λŒ€μˆ˜ N(1 ≤ N ≤ 1,000)이 주어진닀. λ‘˜μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” λŒ€κ·Όμ΄κ°€ 적은 μ°¨λŸ‰ 번호 λͺ©λ‘μ΄ 주어지고, N+2μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” μ˜μ‹μ΄κ°€ 적은 μ°¨λŸ‰ 번호 λͺ©λ‘μ΄ 주어진닀. 각 μ°¨λŸ‰ λ²ˆν˜ΈλŠ” 6κΈ€μž 이상 8κΈ€μž μ΄ν•˜μ˜ λ¬Έμžμ—΄λ‘œ, μ˜μ–΄ λŒ€λ¬Έμž('A'-'Z')와 숫자('0'-'9')둜만 이루어져 μžˆλ‹€.

같은 μ°¨λŸ‰ λ²ˆν˜Έκ°€ 두 번 이상 μ£Όμ–΄μ§€λŠ” κ²½μš°λŠ” μ—†λ‹€.

 
 
 
좜λ ₯ 
 

첫째 쀄에 터널 λ‚΄λΆ€μ—μ„œ λ°˜λ“œμ‹œ 좔월을 ν–ˆμ„ κ²ƒμœΌλ‘œ μ—¬κ²¨μ§€λŠ” μ°¨κ°€ λͺ‡ λŒ€μΈμ§€ 좜λ ₯ν•œλ‹€.

 

ν•΄μ„€ μ½”λ“œ 

 

import sys

t = int(sys.stdin.readline().rstrip())
cars = {}
car_out = []
cnt = 0

# 터널에 λ“€μ–΄κ°„ μˆœμ„œλŒ€λ‘œ ν•΄μ‹œλ§΅μ„ λ§Œλ“ λ‹€. 
for idx in range(t):
  cars[sys.stdin.readline().rstrip()] = idx

# ν•΄μ‹œλ§΅μ„ 기반으둜 그듀이 μ›λž˜ λ‚˜μ™”μ–΄μ•Ό ν•˜λŠ” μˆœμ„œ 배열을 λ§Œλ“ λ‹€. 
for idx in range(t):
  car = sys.stdin.readline().rstrip()
  car_idx = cars.get(car)
  car_out.append(car_idx)

# 뒀에 μžˆλŠ” μˆ˜λ³΄λ‹€ μ•žμ— μžˆλŠ” μˆ˜κ°€ 큰 경우(μ›λž˜ λ‚˜μ™”μ–΄μ•Ό ν•˜λŠ” μˆœμ„œλ³΄λ‹€ 빨리 λ‚˜μ˜¨ 경우) 의 횟수λ₯Ό μ„Όλ‹€. 
for i in range(t):
  for j in range(i,t):
    if car_out[i] > car_out[j]:
      cnt += 1
      break
print(cnt)
뢄석 > 이 문제λ₯Ό ν’€λ©΄μ„œ ν•΄μ‹œλ§΅μœΌλ‘œ λ¨Όμ € 각 차듀이 λ“€μ–΄μ˜¨ μˆœμ„œλ₯Ό value둜 지정해주고, ν„°λ„μ—μ„œ λ‚˜μ˜¨ μ°¨λ“€μ˜ μ›λž˜ valueλ₯Ό 배열에 μΆ”κ°€ν•˜λ©΄μ„œ μžμ‹ μ˜ μ›λž˜ μˆœμ„œλ³΄λ‹€ 빨리 λ‚˜μ˜¨ 차의 수λ₯Ό μ„Έλ©΄ λ¬Έμ œκ°€ ν•΄κ²°λœλ‹€λŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλ‹€. λ‚˜λŠ” ν•΄μ‹œλ§΅μ„ μ‚¬μš©ν•  생각을 μ•ˆν•˜κ³ , 쌩으둜 두 배열을 λΉ„κ΅ν•˜λ €κ³  ν•΄μ„œ λ¬Έμ œκ°€ 잘 풀리지 μ•Šμ•˜λ‹€. ν•΄μ‹œλ§΅μ„ μ‚¬μš©ν•˜λ©΄ μ’€ 더 효율적이고 κ°„λ‹¨ν•˜κ²Œ μˆœμ„œλ₯Ό 확인할 수 μžˆλ‹€λŠ” 것을 λͺ…μ‹¬ν•˜κ³  적극적으둜 μ‚¬μš©ν•΄μ•Όκ² λ‹€. 

 

 

 

 

2002번: μΆ”μ›”

μž…λ ₯은 총 2N+1개의 μ€„λ‘œ 이루어져 μžˆλ‹€. 첫 μ€„μ—λŠ” 차의 λŒ€μˆ˜ N(1 ≤ N ≤ 1,000)이 주어진닀. λ‘˜μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” λŒ€κ·Όμ΄κ°€ 적은 μ°¨λŸ‰ 번호 λͺ©λ‘μ΄ 주어지고, N+2μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” μ˜μ‹μ΄

www.acmicpc.net

 

'Algorithm > BOJ' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[BOJ] μ˜¬λ¦Όν”½  (0) 2022.05.13
[BOJ] 곡톡 λΆ€λΆ„ λ¬Έμžμ—΄  (0) 2022.05.13
[BOJ] μˆ˜κ°•μ‹ μ²­ (#13414)  (0) 2022.04.23
[BOJ] λ§ˆμΈν¬λž˜ν”„νŠΈ (#18111)  (0) 2022.04.22
[BOJ] νƒ€λ…ΈμŠ€ (#20310)  (0) 2022.04.22