0xdeadbeef   3년 전

안녕하세요. 어제 또는 오늘 새벽에 질문을 올렸으나 결국 해결하지 못하고 밤을 새버렸는데요.

바로 밑에 올린 질문에서는 계속 틀리다고 나와 반례를 찾았으나 이번에 새로 다시 짠 코드에서는

런타임 에러가 발생합니다.

질문을 중복할까 싶어 이전 코드를 수정할까 했으나 두 코드의 접근 방법이 달라 두 가지 방법 모두 사용해보기로 했습니다.

이전 코드는 WA로 막히고 지금 코드는 RE로 막히는 상황이거든요.

이 문제를 풀기 위해 무작위로 스도쿠 퍼즐을 생성하는 문제 생성기를 만든 뒤

몇만번 가량 돌려봤음에도 RE는 커녕 WA를 보질 못하고 있습니다.

제가 퍼즐을 생성하는 로직이 허술한건지 아무래도 edge case를 찾지 못한 것 같습니다.

제 코드에서 뭔가 놓치고 있는 부분이나 RE가 날만한 부분이 뭐가 있을까요?


고수님들의 도움 부탁드리겠습니다!

\p.s. p.s. 를 그대로 적으면 뭔가 글이 깨지네요
\\p.p.s. 최대 재귀 함수 호출 횟수 때문인가 싶어 sys.setrecursionlimit(9000) 도 적용해보았으나 RE는 계속 떳습니다.
\\p.p.p.s. 혹시 몰라 중간에 답을 구하자마자 yield하지 않고 바로 print_board(board)로 출력 후 sys.exit(0)으로 나와보았으나 RE는 계속 떳습니다

0xdeadbeef   3년 전

의심이 되는 곳을 하나씩 try-except문으로 감싼 뒤 일부러 잘못된 답을 출력하고 exit() 하여 RE 대신 강제로 WA가 뜨도록 했더니
놀랍게도 아래 코드에서 assert가 걸리더라구요. (만약 저기에서 안걸리고 다른데서 RE가 난다면 10초 이후에 RE가 뜨게 됩니다)

lines = sys.stdin.readlines()

# convert list of strings into 2d matrix with integers
board = [list(map(int, line.split())) for line in lines]

원래 코드는 위와 같았고

board = [list(map(int, input().split())) for _ in range(9)]

이렇게 바꾸니까 제대로 board가 초기화 되었습니다

3번째 테스트 케이스에서 (매 테스트마다 time.sleep(10)을 주어 30초가 지난 시점에 sys.stdin.readlines()를 사용하는 board가 제대로 초기화 되지 않음)
무엇이 문제인진 모르겠으나 sys.stdin.readlines()로 라인을 미리 다 읽고 각 라인을 split해서 int로 map을 하는건 안되고
매번 input()으로 읽고 이를 split()해서 똑같이 int로 map 하는건 제대로 초기화가 되네요

혹시 이게 무슨 원인인지 아시나요?

0xdeadbeef   3년 전

1. input()과 sys.stdin.readlines() 가 특정한 테스트 케이스에서 다르게 동작하는지는 모르겠지만 일단 sys.stdin.readline() 으로 바꾸니 해결되었습니다. 자세한건 나중에 더 살펴볼 계획입니다. (input()도 가능), pypy3에서는 readlines도 되는걸로 보입니다. 아무래도 제가 너무 졸려서 뭔가 착각했나 봅니다.

2. python에서 도저히 통과가 되지 않아 pypy3를 썼습니다.

3. pypy3 에서 작은 규모에서는 set보다 list를 쓰는게 더 빨랐습니다.

4. list에서 if - remove 대신 인덱스로 처리해주니 1초 정도 빨라졌고, 클래스와 yield나 다른 자질구레한것들을 없애니 400ms 더 빨라졌고, readline 대신 readlines를 쓰니 100ms 더 빨라졌네요
하지만 이렇게 빨라진 코드도 python3에선 81%의 벽을 뚫지 못하네요..

파이썬 3으로 통과하신 분들 진짜 멋있어요. 

댓글을 작성하려면 로그인해야 합니다.