less than 1 minute read

2002 추월 / c++ / Silver1 / 22분

문제 및 코드

풀이 과정

자료구조 / 해시맵 / 문자열

  1. 터널을 입장한 순서대로 자동차들의 번호판이 주어지고, 퇴장한 순서대로 자동차들의 번호판이 주어질 때, 추월한 자동차의 수를 출력하는 문제
  2. 입장한 자동차들을 그 순서대로 CarNumberMap에 번호판을 저장하며 번호를 붙인다.
  3. 그리고 그 번호판은 다시 vector에 따로 저장해둔다. (번호판으로 번호를 찾기 위함)
  4. 이후 퇴장한 자동차들의 번호판을 입력 받을 때 마다 아래의 로직을 수행
    1. 이미 추월해 간 자동차가 있다면 비교 대상에서 제외해야하므로, while을 돌면서 체크하여 CheckIndex 증가 (이 때, 몇 번째 입력인지와는 별개로 입장한 순서 기준으로 현재 어느 위치에 있는 자동차와 비교해야하는지를 저장하기 위해 CheckIndex 변수를 사용)
    2. 현재 퇴장한 자동차의 번호판을 CarNumberMap을 통해 정수로 바꾸고, CarNum 변수에 저장
    3. 만약 CarNum과, CarNumberMap[Enters[CheckIndex]] (현재 비교하고자 하는 자동차의 번호)가 일치한다면, IsAlreadyExit[CarNum]을 true 로 바꿔주고, checkIndex를 증가
    4. 일치하지 않는다면, 추월이 발생한 것이므로 Answer를 증가, IsAlreadyExit만 true 로 바꿔주고, checkIndex는 유지
  5. Answer를 출력
  6. 해결

회고

  1. 문자열로 비교와 인덱싱을 해야한다는 부분을 보고 ‘정수로 바꿔야겠다’라고 생각했다. (정보의 가공)
  2. string 을 int 로 변환하기 위한 용도이므로, 원소의 순서는 중요하지 않으므로 해싱만 사용하는 unordered_map 을 사용했다.