Baekjoon_2841 - 외계인의 기타 연주
문제
상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.
보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.
멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)
다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.
출력
첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.
해결방법
- 각 줄 마다 배열을 두어 줄 번호마다 누르는 프렛을 저장한다.
- 누르는 프렛을 저장하기 전
- 배열의 마지막 요소와 대소를 비교하여 저장할 프렛의 번호가 더 크면 (즉, 손가락을 그냥 해당 프렛에 올려놓기만 하면) 배열에 추가해준다.
- 저장할 프렛의 번호가 더 작으면 (즉, 해당 프렛을 연주하기 위해 하나 이상의 손가락을 떼야 한다면) 배열의 마지막 요소를 삭제한다. 그리고 재귀함수를 이용해 더이상 삭제할 필요가 없을 때 까지 반복한다.
- 배열의 마지막 요소와 저장할 프렛 번호가 같은 경우는 손을 떼거나 누를 필요가 없으므로 고려하지 않는다.
코드
import sys
input = sys.stdin.readline
n, p = map(int, input().split())
string1 = []
string2 = []
string3 = []
string4 = []
string5 = []
string6 = []
result = 0
def findMovementNum(stringArr, b):
cnt = 0
if len(stringArr) == 0:
stringArr.append(b)
cnt += 1
return cnt
else:
if stringArr[-1] < b:
stringArr.append(b)
cnt += 1
return cnt
elif stringArr[-1] > b:
stringArr.pop()
cnt += 1
cnt += findMovementNum(stringArr, b)
return cnt
for i in range(n):
a, b = map(int, input().split())
if a == 1:
result += findMovementNum(string1, b)
elif a == 2:
result += findMovementNum(string2, b)
elif a == 3:
result += findMovementNum(string3, b)
elif a == 4:
result += findMovementNum(string4, b)
elif a == 5:
result += findMovementNum(string5, b)
elif a == 6:
result += findMovementNum(string6, b)
print(result)처음에 위처럼 코드를 짰는데 통과는 했지만 뭔가 마지막 for 문에서 코드가 반복되는게 마음에 들지 않아서 더 줄일 수 있을까 고민해보았다.
for 문 안의 if 문을 보면 a 값에 따라 분기되는걸 확인할 수 있다. 그럼 a도 같이 함수의 매개변수로 넘겨버리면 if문을 한 줄로 줄일 수 있을 것이다.
코드
import sys
input = sys.stdin.readline
n, p = map(int, input().split())
stringNum = [[] for i in range(7)]
result = 0
def findMovementNum(stringNum, a, b):
cnt = 0
if len(stringNum[a]) == 0:
stringNum[a].append(b)
cnt += 1
return cnt
else:
if stringNum[a][-1] < b:
stringNum[a].append(b)
cnt += 1
return cnt
elif stringNum[a][-1] > b:
stringNum[a].pop()
cnt += 1
cnt += findMovementNum(stringNum, a, b)
return cnt
for i in range(n):
a, b = map(int, input().split())
result += findMovementNum(stringNum, a, b)
print(result)따라서 위처럼 각 기타줄 프렛 배열을 저장할 stringNum 이라는 2차원 배열을 만들었고 stringNum[a][b] 의 형식으로 접근하도록 코드를 고쳤다. 이렇게 하면 코드 길이와 가독성 면에서 효율이 더 좋아지게 된다.
이 문제는 스택의 활용 문제이긴 하지만, 함수 부분에서 재귀함수의 사용과 적절한 부분에서
return해주는 것이 더 관건인 문제였던 것 같다.
