-
[백준] 2002: 추월development/알고리즘 2024. 4. 12. 23:41
안녕하세요.
이번 문제는 백준의 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)
알고리즘 캔버스
아이디어
- 원본 배열을 입력받아 origin에 저장
- 현재 배열을 입력받으면서 순서대로 원본 배열과 대조해봄
- 기존 배열과 현재 배열을 순서대로 대조했을때,
- 기존 배열 참조는 i를 기준으로 하되, (origin[i])
- 이미 추월한 차의 개수만큼(비교하려는 현재 차를 기준으로, 앞선 차들이 원본과 달라진 개수만큼) i를 줄이고 참조함. (origin[i-count])
- 만약 다르다면 추월한 차 이므로 count를 올리고, 추월한 차를 기존 배열 목록에서 지움
- 기존 목록의 순서와 새로운 배열을 비교할 때, 원래 나중에 비교되어야 할 차가
- 이미 비교 되었으므로 기존 배열에서 삭제함.
- 아니라면 아무 행동도 하지 않음.
- 그리고 위 과정을 a번부터 반복함.
- 기존 배열과 현재 배열을 순서대로 대조했을때,
- 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
감사합니다.
'development > 알고리즘' 카테고리의 다른 글
[백준] 2750: 수 정렬하기 (삽입 정렬 ver) (0) 2024.04.24 [프로그래머스] 60057: 2020 KAKAO BLIND RECRUITMENT > 문자열 압축 (0) 2024.04.05 [프로그래머스] 120812: 최빈값 (1) 2024.03.29 [백준] 11047: 동전 0 (그리디) (0) 2024.03.22 [프로그래머스] JadenCase 문자열 만들기 (0) 2022.09.11