BJ_ 15501 부당한 퍼즐

문제링크

https://www.acmicpc.net/problem/15501

15501번: 부당한 퍼즐

---

 

문제 설명/ 풀이

수열을 조작할 수 있는 방법은 1. 뒤집기와 2. 밀기 밖에 없으므로, reverse()메소드로 뒤집기를 해결하고, 리스트를 원순열로 만들어서 밀기를 해결하기로 생각했다.

 

 - 수열을 원순열로 만들기

rotate 메서드가 있지만, rotate()는 항상 수열의 끝 길이나 첫 길이에서 index 값을 조정해주어야해서 indexing 하기 힘들다.

그래서 나는 메모리를 많이 사용하겠지만, 그냥 두개의 수열을 붙여서 원순열 개념으로 사용했다.

 

1

2

3

4

1

2

3

4

두개의 순열을 붙여서 4개씩 잘라보면, (1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3)  2.밀기로 만들어지는 수열이 모두 포함된다.

---

코드

 - 실패코드 -1

#숫자가 2자리 이상일 경우 올바르지 않은 알고리즘임

n = int(input())
# 첫 수열과 다음 수열을 문자열로 바꾼다
first = "".join(input().split())
last = "".join(input().split())

# 밀기: 퍼즐 두개를 연결하여 원순열 같이 만들어주면서 처리
# 뒤집기: 뒤집기를 두번한 경우 원래의 순열과 같아지므로 뒤집기 한번한 경우만 고려
puzzle_forward = first+ first # 밀기만
puzzle_reverse = first[::-1] + first[::-1] # 뒤집기 한번 + 밀기

# 둘 다에 해당하지 않으면 bad
if(puzzle_forward.find(last) == -1 and puzzle_reverse.find(last) == -1):
    print("bad puzzle")
else: # 해당하면 good
    print("good puzzle")

숫자가 한자리인 경우 문자열로 find() 메서드를 사용하는게 가능하지만, 숫자가 두자리 이상인경우 몇자리 숫자인지에 대한 정보가 없어 직접 비교가 불가능하다. -> 입력 조건을 제대로 생각하지 못하여 실패

 

 

- 성공 코드

n = int(input())
# 리스트로 받기
first = list(map(int, input().split()))
last = list(map(int, input().split()))


#forward
last.extend(last) # 원순열로 만들기 위해 list extend
idx = last.index(first[0]) # 첫번째 원소 위치 찾아주기

# 각 리스트의 첫번째 원소 위치부터 맞게 가는지 확인
for i in range(n):
    if(first[i] != last[idx + i]):
        break
else:
    # 모두 맞았으면 good puzzle & 종료
    print("good puzzle")
    exit()

# backward
# 리스트 뒤집어서 첫번째 원소위치 다시 찾기
last.reverse()
idx = last.index(first[0])
# 각 리스트의 첫번째 원소 위치부터 맞게 가는지 확인
for i in range(n):
    if (first[i] != last[idx + i]):
        # 둘다 틀렸으므로 bad puzzle
        print("bad puzzle")
        break
else:
    # 모두 맞았으면 good puzzle
    print("good puzzle")

리스트로 받아서 각 원소를 비교하는 방식으로 풀었다. exit()를 쓰는건 좀 맘에 안들지만, 함수를 작성하거나 flag같이 상태를 나타내는 변수를 쓰는 것보다는 깔끔한 것 같다..

 

*exit()나 quit()는 프로덕션 코드(프로그램 구현을 담당하는 부분으로 사용자가 실제로 사용하는 소스 코드)에서는 사용하지 않는 것이 좋다.(site 모듈에 의존해서 작동하기 때문 (..?) ) sys.exit()를 사용하자