[프로그래머스](파이썬)나머지한점-Level2-2가지 방법 문제풀이

안녕하세요.진또배기입니다. 오늘은 프로그래머스에 올라와있는 '나머지 한점'문제를 파이썬을 사용해 2가지 방법으로 풀이를 해보겠습니다. 한 가지는 해시를 이용한 방법, 다른 한 가지는 Counter를 이용한 방법입니다.

1. 문제 소개

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 라이트닝 볼트 → 스파크 → 썬더일때, 썬더를 배우려면 먼저 스파크를 배워야 하고, 스파크를 배우려면 먼저 라이트닝 볼트를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 라이트닝 볼트 → 힐링 → 스파크 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 힐링 → 썬더 → 스파크와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skills_order과 유저가 만든 스킬트리1를 담은 배열 skill_tree가 매개변수로 주어질 때, 해당 스킬트리가 적절한지 아닌지 return 하는 solution 함수를 작성해주세요.

제한 조건

• 스킬 이름은 알파벳 소문자와 공백 문자로 구성되어 있으며, 길이는 15 이하입니다.
• skills_order는 길이가 1 이상 100,000 이하인 배열입니다.
  • skill_orders에는 중복된 원소가 없습니다.
• skill_tree는 길이가 1 이상 100,000 이하인 배열입니다.
  • skill_tree에는 중복된 원소가 없습니다.

 

2. 슈도코드

방법 1. 해시를 사용했습니다. x좌표와 y좌포를 해시로 관리해 풀이하면 쉽게 풀 수 있습니다.

방법 2. 핵심은 중복 여부 판단이라 생각했는데, collections 모듈의 Counter 클래스를 처음 알게 되어 문제에서 활용하고자 했습니다. x, y 좌표 구분은 언패킹과 zip() 함수를 사용했습니다.

3. 문제 풀이 

방법 1

방법 2

• 시간복잡도: 좌표 배열의 길이 n에 대해, O(nlogn)