두잇뚜의 블로그

# 문제 # 문제 접근 문제만 봤을 때 굉장히 복잡할 것 같다고 느낀 문제였다. 우선 괄호로 이루어진 입력이 보기가 쉽지 않았다. 중요한 것은 "()" 모양으로 된 것은 레이저 라는 것이다. 그래서 ()를 레이저(R)로 표시한 후 생각하였다. 예시의 입력은 R(((RR)(R)R))(R) 로 바뀌게 된다. 막대기가 하나 완성이 되기 위해선 "(" 과 ")" 가 필요하다. 괄호 쌍을 맞추는 알고리즘 문제를 풀어 본 적이 있는가? 이와 유사하다. 스택에 "("를 만나면 쌓고, ")"를 만나면 스택으로 부터 pop 하여 쌍을 맞추게 되는 것이다. 그럼 R을 만났을 땐 어떻게 할 것인가? "("가 스택에 쌓였다는 것은 막대기가 하나 생성되었다는 것을 의미한다. "("가 N개 스택에 쌓였다는 것은 막대기가 N개 생..

# 문제 # 문제 접근 가격이 떨어지지 않았다는 것은 배열의 한 시점을 기준으로 뒤로 갈 수록 현재 시점보다 가격이 낮은 순간이 있는지를 판단하면 된다. 주의할 부분은, 3초 시점의 3은 바로 다음의 4초에 2로 떨어졌으나, 1초 간 가격이 유지 된 것으로 판단하여 떨어지지 않은 것으로 본다는 것이다. 바로 다음 시점에 가격이 떨어져도 1초간 가격은 유지가 된 것이다. # 문제 풀이 1. 배열의 처음부터 끝까지 루프를 돌린다. (i) 2. 현재 배열의 위치부터 다음 위치까지 루프를 돌린다. (j) 3. 인덱스 j가 증가하면 현재 시점의 카운트를 1 늘린다.(위에서 주의했듯이 바로 다음 순간에 떨어져도 1초간 가격이 유지 된 것이기 때문.) 4. 배열의 i 인덱스의 값이 배열의 j 인덱스 값보다 크면 시점..

# 문제 # 문제 접근 신호가 오른쪽에서 왼쪽으로 간다는 조건만 이해하면 어렵지 않은 문제였다. 자신의 위치를 기준으로 왼쪽방향으로 진행하면서 자신보다 높은 가장 먼저 만나는 탑을 기록하면 된다. 스택/큐 로 분류되어 있어서 스택으로 풀까 하였지만, 굳이 사용 할 필요가 없었다. # 문제 풀이 1. 탑 배열의 가장 뒤부터 순회를 시작한다. 2. 현재 탑의 위치를 기준으로 다시 배열을 뒤에서 앞으로 순회한다. 3. 현재 탑보다 높이가 높은 탑을 만나면 기록하고 다음 탑에서 반복한다. # 코드 작성 def solution(heights): # 배열의 길이, 계산을 용이하게 하기 위해. LEN = len(heights) # 정답 배열, 신호를 받지 못한 탑의 값인 0으로 미리 초기화한다. answer = [0..

# 문제 # 문제 접근 H-Index라는 개념이 굉장히 헷갈리는 문제다. 우선 N은 논문의 수인 citations의 길이다. 즉, 예제에서는 5다. h를 1 부터 증가시켜 가며 천천히 생각 해 보자. 1. h = 1 인 경우, 5편 중 1번 이상 인용된 논문은 [1, 3, 5, 6]로 4개이다. 그리고 나머지 논문 [0]은 1번 이하 인용되었다. 2. h = 2 인 경우, 5편 중 2번 이상 인용된 논문은 [3, 5, 6] 로 3개이다. 그리고 나머지 논문 [0, 1] 은 2번 이하 인용되었다. 3. h = 3인 경우, 5편 중 3번 이상 인용된 논문은 [3, 5, 6] 로 3개이다. 그리고 나머니 논문 [0, 1]은 3번 이하 인용되었다. 위에서 3번 케이스의 경우, N편(5) 중 h번(3) 이상 인용..

# 문제 # 문제 접근 주어진 정수를 이어 붙여서 가장 큰 수를 만들어 내야 한다. 얼핏 생각하기엔 가장 큰 수부터 이어붙이면 되지 않을까 라는 생각이 들지만 그렇게 하면 안된다. 예를 들어, 6과 10으로 만들 수 있는 가장 큰 수는 106이 아닌 610 이기 때문이다. 두 수를 이어 붙일 때 두 수의 크기를 비교하는 것이 아닌, 두 수를 이어붙였을 때 큰 수가 되어야 큰 수로 판별해야 되는 것이다. 예를 들어 a, b 두 수가 있다면 ab 와 ba를 비교한다. 그리고 ba가 더 크다면 리스트를 b, a로 정렬한다. 입력 예제인 [6, 10, 2] 로 예를 들어 보겠다. 1. 6 vs 10 : 610 > 106 이므로 [6, 10, 2]로 정렬된다. 2. 10 vs 2 : 102 < 210 이므로 [6..

# 문제 # 문제 접근 문제 설명이 곧 풀이 방법이다. 문제만 잘 읽으면 되고, commads 에서 i, j, k를 획득하여 입력 array를 자르고 정렬하는 것이 주 포인트이다. # 문제 풀이 문제 설명에 문제를 푸는 방법이 전부 나와있다. i, j, k의 의미에 대해서 이해를 한다면 어렵지 않게 문제를 풀 수 있다. 1. 원본 입력 array를 보존해야 한다. 2. commands를 순회하면서 현재의 i, j, k를 구한다. 3. 원본 array를 i~j 까지 슬라이싱하고 정렬한다. 4. 위에서 얻은 리스트의 k번째 수를 결과 리스트에 담는다. # 코드 작성 def solution(array, commands): answer = [] for command in commands : // 현재 comma..

# 문제 # 문제 접근 정답을 도출하기 위해 필요한 것은 가장 많이 재생 된 장르의 순서 / 장르별로 포함 된 노래의 재생 횟수 ,노래의 고유 번호 가장 많이 재생 된 장르의 순서를 알기 위해선, "장르" : "총 재생된 횟수" 가 필요하다. 장르별로 포함 된 노래의 재생 횟수를 알기 위해선, "장르" : "노래의 재생 횟수 리스트" 가 필요하다. 장르별로 포함 된 노래의 고유 번호를 알기 위해선, "장르" : "노래 고유 번호 리스트" 가 필요하다. 위를 딕셔너리로 구조화 시키면, { "장르" : { "총 재생 횟수" : N, "노래 리스트" : (재생 횟수, 고유 번호) } } 와 같이 만들 수 있다. # 문제 풀이 1. 위에서 구조화한 딕셔너리를 만들기 위해 빈 딕셔너리를 생성한다. 2. genre..

# 문제 # 문제 접근 문제를 읽고 처음 입출력 예를 보고 나면 의상의 종류와 의상들을 묶어서 가능한 조합들을 모두 구하면 되겠다고 생각할 수 있다. 하지만 조금만 생각해보면 의상의 종류와 그 종류가 몇 개의 의상이 있는지만 알면 경우의 수를 구할 수 있다. 또한 같은 이름을 가진 의상이 존재하지 않기 때문에 별다른 예외처리도 필요 없음을 짐작할 수 있다. 따라서 의상의 종류가 "키"가 되고 의상의 개수가 "값"이 되는 딕셔너리를 생성하여 문제를 풀 수 있을 것이다. # 문제 풀이 1. "의상의 종류 : 의상의 개수" 의 구조를 가진 딕셔너리를 생성한다. 2. clothes 리스트를 순회하며 딕셔너리에 저장한다. 3. 딕셔너리를 순회하며 경우의 수를 구하여 반환한다. 4. 경우의 수를 구하는 것은 수학적..

# 문제 # 문제 접근 phone_book의 길이가 1,000,000 이기 때문에 이중루프로 돌면 시간초과가 날 것이 분명하기 때문에 다른 방법을 생각해야 한다. A 번호가 B 번호의 접두어 이려면, B번호에서 앞에서부터 A번호 만큼의 길이를 잘라낸 부분이 A와 동일해야 한다. phone_book을 순회하며 한 전화번호를 앞에서부터 잘라가며 접두어 리스트를 만들어 놓고 있는지 없는지 판별하면 될 것 같다. 그런데 생각해보니 단순히 리스트면 시간초과가 날 것 같으니, 읽는 속도가 빠른 set을 사용하도록 하자. # 문제 풀이 1. 접두어들을 저장할 set을 만든다. 2. phone_book 리스트를 순회하며 전화번호의 앞에서부터 1글자, 2글자, .. N글자 까지의 접두어를 위의 set에 저장한다. 3. ..

# 문제 # 문제 접근 participant에 존재하는 이름 중에 completion에 존재하지 않는 이름을 찾아서 return하면 되는 문제다. 제한사항에서 "참가자 중에는 동명이인이 있을 수 있습니다." 라는 문구가 있는 것과 입출력 예의 세번 째를 참고하면 같은 이름을 가진 참가자가 있고 답이 그 이름일 때 어떻게 처리할 것인가가 중요 포인트인 것 같다. 또한 참가자 수가 100,000명까지 가능하기 때문에 N^2으로 풀면 시간초과가 날 가능성이 있다는 것을 염두하자. # 문제 풀이 1. 동명이인이 존재할 수 있기 때문에, 특정 이름이 몇명이 존재하는 지 구분할 수 있어야 한다. 즉 "어떤 이름" : "몇 명" 이란 데이터를 저장할 수 있어야 하는데, 이 형태는 (키 : 값) 을 띄고 있기 때문에 ..