매일 성장하는 블로그

www.acmicpc.net/problem/9012

괄호의 조합들을 입력받았을 때, 쌍이 제대로 맞으면 'YES', 아니면 'NO를 출력하는 문제이다.

* 힌트

1. 스택의 개념을 사용한다.

* 풀이

end = 0

1. 입력을 받아 차례로 스택에 넣는다.

2. 스택의 원소들을 하나씩 pop하며 아래 조건에 따른다.

  1) pop한 원소 = ')'

     : end + 1 을 해준다.

  2) pop한 원소 = '('

     : end - 1을 해준다.

  3) end <0일 경우 break

3. for문이 끝났을 때 end가 0인지 확인한 후 0이면 'YES', 아니면 'NO'를 출력한다.

해당 문제는 알고리즘 문제에 자주 등장하는데, 스택의 개념을 활용해서 풀 수 있다는 것을 처음 알았다.

import sys
r = sys.stdin.readline

n = int(r())
# (이면 end - 1
# )이면 end + 1
# 두번째 for문 내에서 end 가 0보다 작아지면 No를 출력하고, 마지막에 end가 0인지 확인한다.
for i in range(n):
    string = list(r().strip())
    end = 0

    for i in range(len(string)):
        x = string.pop()
        if x == ')':
            end += 1
        else:
            end -= 1
        if end <0:
            break
    if end !=0:
        print('NO')
    else:
        print('YES')
    

https://www.hackerrank.com/challenges/frequency-queries/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

[ 문제 ] 주어지는 query들을 정해진 규칙에 따라 수행하고 최종 출력을 return한다.

query 형태 = [a,b]

a에 따라 수행 작업이 달라지며, b는 수행의 대상이다.

arr, output = []

1) a = 1 : b를 arr에 넣는다.

2) a = 2 : b를 arr에서 뺀다.(존재할 경우)

3) a = 3 : list에서 frequency가 b인 것이 존재할 경우 1을, 존재하지 않을 경우 0을 output에 넣는다.

[ 예시 ]

[ 방법 ] : 리스트를 만들지 않고 dictionary로 처리한다.

dict = {}

output = []

1. query를 읽는다.

query[0] = a

query[1] = b

   1) a == 1일 경우 : dict[b]에 1을 추가한다. 

   2) a == 2일 경우 : dict[b]에서 1을 뺀다.

   * 이 때, dict[b]가 음수가 되어서는 안된다.

   3) a == 3일 경우 : dict.values()에 b가 있다면 1을, 없다면 0을 output에 추가한다.

간단한 문제이지만 Time out으로 해결되지 않는 case도 있어서 몇가지 Trick을 추가해줘야 합니다-!

https://www.hackerrank.com/challenges/count-triplets-1/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

간단해 보이지만 어김없이 시간 제약에 걸리는 문제입니다.

문제 : 숫자 리스트 arr과 공비 r이 주어졌을 때,

arr[i] = 임의의 숫자 k

arr[j] = k * r

arr[k] = k * r * r

를 만족하는 (i,j,k)의 총 갯수를 구하는 문제입니다. 이 때 i < j < k를 만족해야 합니다.

예를 들어,

arr = [1, 2, 2, 4] , r = 2라고 할 때

arr[0] = 1, arr[1] = 2, arr[3] = 4 (i = 0, j = 1, k = 3)

arr[0] = 1, arr[2] = 2, arr[3] = 4 (i = 0, j = 2, k = 3)

라는 두개의 해를 찾을 수 있습니다. 

방법 : 저는 찾아야 하는 3개의 숫자 중 가운데 숫자(arr[j])를 기준으로 i,j,k의 조합을 찾아내기로 했습니다.

* arr[j]의 특성은 r로 나눴을 때 나머지가 0이라는 점입니다.(arr[k]도 마찬가지긴 합니다.)

1) Counter 라이브러리를 활용하여 arr의 구성 요소에 대한 dict를 생성한다.

2) 빈 라이브러리 dict2를 생성한다.

3) 리스트에 대해 for loop을 돌리면서 나오는 숫자(num)가 r로 나눴을 때 나머지가 0인지 확인한다.

  3.1) 나머지가 0이 아닌 경우 : dict2[num]에 1을 더하고, dict[num]에 1을 빼준다.

  3.2) 나머지가 0인 경우 :

          1) dict2[num//r]이 존재하고, dict[num*r]이 존재할 경우, 정답에 dict2[num//r] * dict[num*r]을 더한다.

          2) 위의 둘 중 하나가 없는 경우 dict2[num]에 1을 더하고, dict[num]에 1을 빼준다.

위의 작업을 리스트의 처음부터 끝까지 반복하면 정답을 구할 수 있습니다 -!

https://www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

매우 골치를 썩였던 문제입니다.

단순히 풀리나 싶더니 어김없이 Time Limit을 걸어놓았더군요 ㅎㅎ

discussion을 조금 보고서야 풀 수 있었습니다.

문제 : 길이가 n이며 원소가 모두 0인 배열 arr이 주어질 때, 주어지는 query에 따라서 arr[a:b]에 k만큼 더한다. query들이 끝나면, 배열 내에서 가장 큰 수를 찾는다.

input : n, m, a, b, k

n : array의 길이

m : query의 수

a : 시작 index

b : 끝 index

k : 더하는 수

Ex) n = 5, m = 3 a,b,k = [[0, 1, 100], [1, 2, 100], [2, 3, 100]]

n= 5이므로 처음 배열의 시작은 

[0,0,0,0,0]

1) a = 1, b = 2, k = 100

arr 배열의 1번째 원소부터 2번째 원소까지 k만큼 더합니다.

→ [100, 100, 0, 0, 0]

이와 같이 문제를 풀어나가시면 됩니다. 다만 단순히 구현만 해서는 Timeout에 걸릴 수 있으니 주의하세요.

직접 풀어보시길 추천합니다. 저는 방법에 대한 힌트를 얻어서 이미 불가능했습니다..

방법 :

0) arr = [0] * (n+1) 

* n+1개를 만드는 이유는 1)번 과정을 보시면 이해할 수 있습니다.

1) query가 주어질 때([a,b,k]), a-1번째 원소에 +k를, b번째 원소에 -k를 해줍니다.

 * a와 b의 index는 1부터 시작하기 때문에, a,b가 주어졌을 때 arr[a-1: b] += k를 해줘야 합니다.

 * 여기서 (1)번을 수행하는 이유는, a-1번째 원소부터 b-1번째 원소들의 최대값을 표시한 것입니다. 모두 동일한 값을 더했기 때문에 우리가 구하길 원하는 최댓값을 구하는 방법을 간단히 구현하였습니다.

(arr의 최댓값을 구하는 3번 과정을 보시면 더 잘 이해할 수 있습니다.)

2) 1)번이 완료되면, arr에 for loop을 돌리면서 값들을 더해줍니다. 더해주는 과정에서 max가 될 때의 값을 찾아냅니다.

max, x = 0

for i in arr:

    x += i

    if(max<x):

        max = x

https://www.hackerrank.com/challenges/minimum-swaps-2/submissions/code/149223858?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

이번 문제는 주어진 배열을 정렬하기 위해 필요한 최소의 swap 수를 구하는 것입니다.

[4, 3, 2, 1]이란 배열이 주어진다면, 이 배열을 [1,  2 3, 4]로 정렬하기 위해 필요한 swap의 수를 구하면 됩니다.

이 때, swap은 아무 위치에 있는 숫자끼리도 바꿀 수 있습니다.

위의 예를 보면,

[4,1] swap → [1, 3, 2, 4]

[3,2] swap → [1, 2, 3, 4]

따라서 위의 배열을 정렬하는데 필요한 최소의 swap 수는 2입니다.

1. 방법

  1) for loop에 enumerate 함수를 사용하여 idx, 숫자를 순차적으로 뽑아냅니다.

  2) 만약 idx와 숫자(x)가 일치하지 않는다면(정렬되어있지 않다는 뜻), 해당 숫자(x)의 고유 idx 위치에 숫자(x)를 입력합니다.(일치하면 for loop 지속)

  3) swap 횟수를 1을 더해줍니다.

  4) x의 고유idx에 존재하던 숫자(y)와 y의 고유 idx에 있는 숫자 z를 비교하고, 다르다면 swap한 뒤 swap 횟수에 1을 더합니다.(같아질 때까지 반복하고, 같다면 swap 횟수에 1을 빼고 for loop로 복귀합니다.) 

  5) for loop이 완료될 때까지 (2) - (4)를 반복한다.

* 이 때 for loop 복귀 전에 swap 횟수를 1을 빼주는 이유는, 위에서 주어진 예시[4,3,2,1]에서의 [1,4], [3,2]와 같이 한번 swap을 통하여 두 숫자가 제자리를 찾아가는 경우가 있습니다. 하지만 이 알고리즘에서는 해당 경우를 즉각적으로 검출해내지 못하므로, 1을 빼주는 것입니다.

Ex) Input : [4, 3, 2, 1] (이 때 보기 쉽게 idx는 1, 2, 3, 4로 지정하겠습니다. 실제로는 0, 1, 2, 3)

for idx, num in enumerate(Input):

→ idx = 1, num = 4

→ idx != num이므로 4가 있어야 할 원래 위치(idx : 4)에 4를 입력하고, num을 1로 바꿔줍니다. [swap 횟수 = 1]

→ [4, 3, 2, 4], num = 1

→ num(=1)이 있어야할 원래 위치(idx : 1)의 숫자(=4)와 num(=1)을 비교합니다.

→ num(=1)이 있어야할 원래 위치(idx : 1)에 num을 입력하고, num을 4로 바꿔줍니다. [swap 횟수 = 2]

→ num(=4)이 있어야할 위치에 해당 숫자(4)가 위치해 있으므로 for loop을 벗어납니다.

이상 끝-!

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

이번에 풀어본 문제입니다.

문제) 사람들이 일렬로 물건을 사기 위해 줄을 서있습니다. 이 때, 모든 사람들은 앞 사람들에게 돈을 주고 자리를 바꿀 수 있고, 특정 사람이 다른 사람을 매수할 수 있는 최대 횟수는 2회입니다.(즉, 자신의 자리보다 최대한 2칸까지 앞으로 갈 수 있습니다.) 숫자들의 List가 주어질 때, 매수가 일어난 최소 횟수를 구하시오.

[예시]

초기 상태 : [1, 2, 3, 4, 5]

최종 상태 : [2, 1, 5, 3, 4]

* 엄청나게 큰 Input이 테스트 항목에 있으므로, 단순히 풀기만 해서는 안됩니다.(여기서 많은 시간을 보냈습니다. 사실 답을 찾지 못해서 discussion에 들어가서 힌트를 얻었습니다 ㅠㅠ)

1. 방법

* (매수가 일어난 총 횟수) = (각각의 사람들이 매수당한 횟수의 총 합)

  -> 각 사람들이 매수당한 횟수는 특정 사람(x)보다 앞에 있지만 뒷번호를 가진 사람(y: y>x)을 찾으면 됩니다.

  -> 특정 사람의 순서(x)보다 뒷 번호를 가진 사람(y : y>x)은, 특정 사람의 원래 자리(x) 보다 1자리 앞(x-1)까지 갈 수 있습니다.(y : y≥x-1)

     (이 부분을 이해하는 것이 중요합니다. 뒤에 있던 사람이 매수를 하면 뒤에 있던 사람은 자리 (x)로 오게 됩니다.)

  -> 즉, 원래 특정 사람이 x에 위치해 있었고 현재 위치가 i라면, x-1부터 i-1까지 위치에 x보다 큰 숫자가 몇개 있는지 찾으면 됩니다.

코드는 매우 간단하므로 생략하겠습니다. -!

Weighted Mean을 구하는 문제입니다.

숫자 행렬 X = [1, 2, 3]

가중치 행렬 W = [4, 5, 6]

과 같이 행렬이 주어지면 Weighted Sum은 (1x0.1 + 2x0.2 + 3x0.3)/(4 + 5 + 6) 과 같이 구할 수 있습니다.

https://www.hackerrank.com/challenges/s10-weighted-mean/problem

https://www.hackerrank.com/challenges/30-nested-logic/problem

이번 문제는 Nested Logic입니다. 간단한 문제이지만 괜히 이상하게 푼 것 같습니다..

이 문제는 책을 반납받을 때 내야하는 연체료를 계산하는 문제였습니다. 

연체료를 내는 조건은 다음과 같습니다.

i) 반납 예정 일자 이전(혹은 당일)에 반납할 경우 0원

ii) 반납 예정 일자 이후에 반납할 경우 : 

  1) 같은 해, 같은 월에 반납할 경우 (연체된 일수 * 15)원

  2) 같은 해 다른 월에 반납할 경우 (연체된 월수 * 500)원

  3) 다른 해에 반납할 경우 10000원

변수 : 

  1) return_date_input : 입력 받은 반납 날짜 (Input Format은 'day month year'입니다.)

  2) expected_date_input : 입력 받은 반납 예정 날짜

  3) date_list : input들을 저장하는 list, string 을 가공하여 datetime 객체로 만든다.

  4) return_date : datetime Format로 변경된 반납 날짜

  5) expected_date : datetime Class로 변경된 반납 예정 날짜

방법 : 

  1) input을 datetime형식으로 변경하여 저장한다. (저는 연체 날짜가 1달을 넘어갈 경우 (연체된 달 * 500)이 아니라 (연체된 날짜 * 500)으로 이해해서 datetime형식으로 변환했습니다. 30일/31일/28일/29일 등 달마다 일의 개수는 다르니까요. 하지만 문제를 잘못 읽었었습니다.)

  2) return_date의 연/월/일, expected_date의 연/월/일 비교를 통하여 연체료를 계산한다.

이 때 주의해야 할 점은,

1) Input format에서 연도는 항상 4자리가 아니다.(Datetime 객체로 변환할 시 문제가 됩니다.)

2) 반납 날짜와 반납 예정 날짜의 연도 / 월이 다르지만 연체료를 내지 않는 경우도 있습니다.(1년 혹은 1달 이상 빨리 반납했을 경우)

이상 끝-!