오늘밤 공부

🗓️ 문제 설명

• 길이가 같은 두 개의 큐가 주어질 때, 하나의 큐를 골라 원소를 추출하고 추출된 원소를 다른 큐에 집어넣는 작업을 통해 두 큐의 원소 합을 같게 만들려고 합니다.
• 두 큐의 원소 합을 같게 만드는 작업의 최소 횟수를 구하고자 합니다.
• 한 번의 추출작업(pop)과 한 번의 집어넣는 작업(insert)를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
• 만일 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 반환합니다.
• 제한 사항
  • 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300000
  • 1 ≤ queue1의 원소, queue2의 원소 ≤ 10⁹
  • 주의 : 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
• 입출력 예시

💻 코드

최종 코드

• 3차 시도 이후 수정 사항
  • 시간 복잡도를 줄이기 위해 최대 반복횟수인 "max_length *2" 를 "len(queue1) * 8"로 변경
  • 두 번째 조건문에서 sum이 중복으로 사용되는 것을 막기위해 처음에 구한 q1, q2에 추출된 원소를 더하는 방식으로 변경

코드 풀이

더보기

⚙️ 시행착오

1차 시도

더보기

- 테스트 결과

>> 테스트 1번 실패
>> 테스트 11, 12, 15, 19, 20, 21, 22, 23, 24, 28, 30 번 시간 초과

2차 시도

더보기

- 1차 시도 이후 수정사항 : while 반복문에서 for 반복문으로 변경

- 테스트 결과
>> 테스트 11, 12, 15, 19, 20, 21, 22, 23, 24, 28, 30 번 시간 초과

3차 시도

더보기

- 2차 시도 이후 수정 사항 : 리스트를 deque로 변경, pop을 popleft로 insert를 append로 변경

- 테스트 결과
>> 테스트 11, 12, 15, 19, 20, 21, 22, 23, 24, 28, 30 번 시간 초과

알게된 점