[코테준비] Python 해커랭크(HackerRank) 문제풀이 - 1 (Socks Merchant)

* 코딩인터뷰시 기업들에서 널리 활용중인 해커랭크(HackerRank)의 Python 문제 정리.

---

 

1. 문제

 

 

• 주어진 양말들의 짝은 몇개인가?
  • sort를 활용하여 풀 수 있었던 Easy 문제
  • 이 문제는 어떤 분류에 속하는지를 모르겠다. 스스로 풀 수는 있었지만, 내 머리 속에 아직 각 문제별로 유형화가 덜 되어있어서 그런 것 같다.
  • 문제를 좀 더 풀다가 한번 알고리즘/자료구조 개념정리를 하는 시간을 가져야겠다.

---

2. 정답

def sockMerchant(n, ar):
    temp = 0; cnt = 0;

    ar.sort()
    for i in range(0,n-1):
        if temp == 1 :
            temp = 0
            continue

        if ar[i] == ar[i+1]:
            cnt += 1
            temp = 1
        
    return cnt

• SQL 문제풀이와는 다르게 스크립트형 언어를 통한 코딩테스트는 답이 정말 여러개가 나올 수 있는 것 같다.
• 위의 코드는 내 방식대로 풀어본 코드이다. 최적화된 코드인지는 잘 모르겠으나 일단 Test Case 15개는 모두 통과
  • 1) 먼저 주어진 양말들을 순서대로 정렬한뒤 (sort)
  • 2) 앞에서부터 순서대로 짝을 찾아간다. 짝을 찾았다면 다다음 양말로 넘어가고, 아니라면 다음 양말로 넘어가서 오른쪽에 이웃한 양말이 짝인지 확인한다. 
    • 짝을 못찾았다는 것은 그 이웃한 양말과 다른 양말이라는 뜻으로, 경계선에 도달했다는 의미
    • 짝을 찾을때 마다 cnt에 1을 추가로 더해 갱신해준다.
  • 3) 여태껏 누적하여 갱신한 cnt 숫자를 반환

• 다 풀고나서 생각해보니, 굳이 양말들을 하나하나 일일히 비교해줄 필요 없이, 동일한 종류의 양말의 갯수를 각각 카운트하여 나눈뒤, 그 몫만 모조리 더해주는 방법도 있다는 생각이 든다.
• Discussion을 참고하니 Hashset을 쓰는 방법이 vote가 가장 많다.
  • 파이썬의 정렬은 퀵정렬로 시간복잡도가 n*logn 이지만, 그럼에도 Hashset이 더 많이 쓰이는 추세인건가 싶다.
  • 위 개념을 활용하여 문제를 다시 풀어볼것! 해시셋 공부할 것!

---

3. 결과

 

 

해커랭크(HackerRank)의 Python for Interview'를 풀며 정리한 글입니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 내용 수정 피드백은 댓글로 적어주세요.

감사합니다 :-)