162. 외계인의 기타 연주
1) 어떤 전략(알고리즘)으로 해결?
- 스택
2) 코딩 설명
<내 풀이>
import sys
# 손가락의 가장 적게 움직이는 회수를 구하는 프로그램
n,p = map(int, sys.stdin.readline().split())
lis=[]
lis2=[[] for _ in range(7)] #각 줄
cnt =0 #손가락을 움직 횟수
for i in range(n) :
lineno, pno = map(int, sys.stdin.readline().split())
lis.append([lineno, pno])
#이전 음이 나보다 낮은 / 같은 음이면 안 움직여도 되지만,
## 여기서부턴 lis2에다가 연주음 넣는것이지
# 같은 줄을 만났으면 스택에서 빼주기, 각 줄에 하나씩만
#print("lis : " , lis,"\n")
for l,p in lis :
#print(l,p)
if not lis2[l] : # 아무것도 없음 내가 첫음~
lis2[l].append(p)
cnt+=1
else :
if lis2[l][-1]<p:
lis2[l].append(p)
cnt+=1
elif lis2[l][-1] == p:
continue
else : #이전 음이 나보다 높은 음이면 움직여
for j in range(len(lis2[l])-1,-1,-1) :
if lis2[l][j] < p :
lis2[l].append(p)
cnt+=1
break
elif lis2[l][j]> p :
#print(lis2[l])
lis2[l].pop()
cnt+=1
else : #떼다보니깐 나랑 똑같은 수 => 안움직여도됨
break
if not lis2[l] :
lis2[l].append(p)
cnt+=1
#print("lis2 : " ,lis2)
print(cnt)
<내 틀렸던 풀이, 문제점>
import sys
# 손가락의 가장 적게 움직이는 회수를 구하는 프로그램
n,p = map(int, sys.stdin.readline().split())
lis=[]
lis2=[[] for _ in range(7)] #각 줄
cnt =0 #손가락을 움직 횟수
for i in range(n) :
lineno, pno = map(int, sys.stdin.readline().split())
lis.append([lineno, pno])
#이전 음이 나보다 낮은 / 같은 음이면 안 움직여도 되지만,
## 여기서부턴 lis2에다가 연주음 넣는것이지
# 같은 줄을 만났으면 스택에서 빼주기, 각 줄에 하나씩만
#print("lis : " , lis,"\n")
for l,p in lis :
#print(l,p)
if not lis2[l] : # 아무것도 없음 내가 첫음~
lis2[l].append(p)
cnt+=1
else :
if lis2[l][-1]<p:
lis2[l].append(p)
cnt+=1
elif lis2[l][-1] == p:
continue
else : #이전 음이 나보다 높은 음이면 움직여
for j in range(len(lis2[l])-1,-1,-1) :
if lis2[l][j] < p :
lis2[l].append(p)
cnt+=1
break
elif lis2[l][j]> p :
#print(lis2[l])
lis2[l].pop()
cnt+=1
else : #떼다보니깐 나랑 똑같은 수 => 안움직여도됨
break
if not lis2[l] :
lis2[l].append(p)
cnt+=1
break
#print("lis2 : " ,lis2,'\n')
print(cnt)
반례
3 4
4 5
4 2
4 5이 부분이 잘못됐었다!
if not lis2[l] :
lis2[l].append(p)
cnt+=1
break이때 break를 하면 아예 전체 for문이 break 되는데, 내가 인덴트를 잘못보고 여따가 걸어놨다, 위에 반례를 내가 행운스럽게 맞춘 덕에 ㅠㅠ 에러를 잡을 수 있었다 ㅎㅎ
<반성 점>
- break를 조심스레 걸자
<배운 점 + 반성할 부분 + >
- 이중 for문 만들 때
lis2=[[] for _ in range(7)] #각 줄 이렇게 만들어야지
lis2=[[] * 7 ] #각 줄 이렇게 만들면 안된다!
저렇게 되면 첫번째 배열에 뭐가 삽입되면, 다 똑같은 주소를 갖고 있어서 다른 애들한테도 append가 되는 참사가 발생
