[HackerRank] 1Week + Day5 - Pairs

Day 5 Interview Questions | HackerRank

 

1. 문제

배열이 주어질 때, 각 element의 차가 k인 쌍의 개수를 반환해야 합니다.

 

2. 풀이

주어진 배열을 오름차순으로 정렬한다면 쉽게 풀 수 있는 문제입니다.

단! 기본적인 이중 for문으로 수행한다면 시간 초과가 발생할 수 있기 때문에 적절한 조건문을 반드시 추가해주어야 합니다.

 

어떤 조건문을 추가할 수 있을까요?

오름차순으로 정렬한 element들을 하나씩 비교하다보면 그 차이가 k보다 카지는 경우가 있을 것입니다.

이후의 element들은 검사할 필요가 없기 때문에(무조건 k보다 크기 때문에) 반복문을 종료해주면 됩니다. 🤗

# arr[i]: 앞 element, arr[j]: 뒤 element
if arr[j] - arr[i] > k: break

 

전체적인 코드는 아래와 같습니다.

3. 코드

Python

def pairs(k, arr):
    # Write your code here
    size = len(arr)
    arr.sort()
    
    answer = 0
    for i in range(size-1):
        a = arr[i]
        for j in range(i+1,size):
            if arr[j] - a == k: answer += 1
            if arr[j] - a > k: break

 

4. Day5 추가 문제

4.1 Queue using Two Stacks

제목 그대로 python을 사용하여 풀 수 있는 문제였습니다.

q = int(input())
result = []

for _ in range(q):
    query = input().split()
    if query[0] == '1':
        result.append(query[1])
    elif query[0] == '2':
        result.pop(0)
    elif result:
        print(result[0])

 

4.2 Balanced Brackets

여러 코딩테스트 문제에서 볼 수 있는 괄호 짝짓기 문제입니다.

이는 queue를 이용해 쉽게 풀 수 있으며, 코드는 아래와 같습니다. 😌👍🏻

def isBalanced(s):
    # Write your code here
    q = []
    
    for i in s:
        if i == '(' or i == '[' or i == '{':
            q.append(i)
        else:
            if not q: return "NO"
            last = q[-1]
            if last == '(' and i == ')': q.pop()
            elif last == '{' and i == '}': q.pop()
            elif last == '[' and i == ']': q.pop() 
            else: return "NO"
    return "NO" if q else "YES"