📍 문제
(원문은 영어여서 어색한... 한국어로 번역했어요)
Pairing Socks 문제 영어 원문 보기
문제
사이몬의 어머니는 가정에서 사이몬이 돕지 않는다는 불평을 자주 합니다.
그런 그녀의 말에 대해 그는 자신의 엄마가 시키는 일 중 많은 일들이 최적화하여 수행하는 것이 어렵다고 지적합니다. (예로는 집 청소나 저녁 식사 테이블 주위에 작은 형제들을 갈등 없이 앉히는 것, 형제들의 할로윈 전리품을 공정하게 나누는 것들을 들 수 있습니다.)
사이몬의 어머니는 컴퓨터 과학자로써, 사이몬의 이의를 합당하다고 생각합니다.
그녀는 아직 해결하지 못한 집안 일 목록을 살펴보던 중,
양말을 짝지어 맞추는 일을 쉬운 문제로 생각하고 사이몬에게 주었습니다.
집안 일을 본격적으로 시작하려고 보니, 2n개의 양말이 한 더미에 쌓여 있는 상황입니다.
사이몬은 양말을 짝지어 맞추기 위해 아래 활동들 중 하나의 동작을 반복적으로 수행할 수 있습니다!
1. 원래 양말 더미의 맨 위에서 양말을 보조 더미의 맨 위로 이동시킵니다. (보조 더미는 원래 비어 있습니다.)
2. 보조 더미의 맨 위에서 양말을 원래 더미의 맨 위로 이동시킵니다.
3. 만약 같은 종류라면, 두 더미의 맨 위 양말을 짝지어 맞춥니다.
사이몬은 두 개의 더미만 사용할 수 있으며, 한 종류의 양말이 두 개 이상 있을 수 있습니다.
이 경우 사이몬은 그 양말들 중에서 원하는 대로 양말을 짝지어 맞출 수 있습니다.
자, 이제 여러분이 해결할 문제는 양말을 짝지어 맞추기 위해 사이몬이 필요로 하는 최소한의 동작 횟수를 구하는 것입니다. 물론, 양말을 짝지어 맞추는 것이 가능하다면 말이죠!
예제 입력 1
2
1 2 2 1예제 출력 1
4예제 입력 2
1
3 7예제 출력 2
impossible예제 입력 3
3
5 5 5 5 5 5예제 출력 3
6📍 아이디어
문제를 보면 알 수 있듯이, 너무나도 명확한 stack 문제이다!
보조 더미를 stack으로 지정한 다음, 원래 더미의 양말 값을 넣어주고
그 이후부터는 원래 더미의 가장 위에 있는 양말 값과 보조 더미 위에 있는 양말 값을 비교한다.
같을 때에만 pop한 뒤 최종적으로 보조 더미에 양말이 남아있는 지의 여부로 문제를 풀어주면 된다.
📍 시간 초과 코드와 통과한 코드
시간 초과 코드
import sys
n = int(sys.stdin.readline().rstrip())
raw = list(map(int, sys.stdin.readline().rstrip().split(" ")))
stack = []
move = 0
for i in range(len(raw)):
if raw[i] in stack:
stack.pop()
move += 1
else:
stack.append(raw[i])
move += 1
if len(stack) != 0:
print("impossible")
else:
print(move)pop할 때 보조 더미에 원 더미의 값이 있는지 전체적으로 in 연산자를 써서 확인하는 로직으로 했더니, 해당 요소를 찾느라 전체 리스트를 돌다가 시간 초과가 났다(...)
통과한 코드
import sys
n = int(sys.stdin.readline().rstrip())
raw = list(map(int, sys.stdin.readline().rstrip().split(" ")))
stack = []
moves = 0
while raw:
moves += 1
if not stack:
stack.append(raw.pop())
continue
if raw[-1] == stack[-1]:
raw.pop()
stack.pop()
continue
stack.append(raw.pop())
if not stack:
print(moves)
else:
print("impossible")- pop할 걸 찾을 때 전체 요소를 다 돌 필요 없게끔 수정한 코드.
for 문 돌릴 때 제발 범위 좀 생각하자 나 자신~^^
