[백준] 2002: 추월

안녕하세요.

이번 문제는 백준의 2002번 '추월' 입니다.

 

문제

코드

import sys

n = int(input())
count = 0

origin = [sys.stdin.readline().rstrip() for i in range(n)]

for i in range(n):
    s = sys.stdin.readline().rstrip()

    if origin[i - count] != s:
        count += 1
        origin.remove(s)

print(count)

 

알고리즘 캔버스

아이디어

1. 원본 배열을 입력받아 origin에 저장
2. 현재 배열을 입력받으면서 순서대로 원본 배열과 대조해봄
   1. 기존 배열과 현재 배열을 순서대로 대조했을때,
      1. 기존 배열 참조는 i를 기준으로 하되, (origin[i])
      2. 이미 추월한 차의 개수만큼(비교하려는 현재 차를 기준으로, 앞선 차들이 원본과 달라진 개수만큼) i를 줄이고 참조함. (origin[i-count])
   2. 만약 다르다면 추월한 차 이므로 count를 올리고, 추월한 차를 기존 배열 목록에서 지움
      1. 기존 목록의 순서와 새로운 배열을 비교할 때, 원래 나중에 비교되어야 할 차가
      2. 이미 비교 되었으므로 기존 배열에서 삭제함.
   3. 아니라면 아무 행동도 하지 않음.
   4. 그리고 위 과정을 a번부터 반복함.
3. count를 리턴함.

시간 복잡도 (Big-O)

- O(N)

 

테스트 케이스 

[입력]

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

[출력]
1

[입력]

5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

[출력]
3

[입력]

5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN


[출력]
2

 

 

감사합니다.