이전 인덱스에서 이미 파일이 구별되었더라도, 현재 인덱스의 숫자가 같으면 중복으로 간주되는 것 같습니다.

원리는 각 파일에서 k만큼 자른 부분이 유니크한 지를 매번 비교하지 않고 열 단위로 유니크한지 보는데

3
1 2 3 2 3 -1
1 2 3 5 4 -1
1 2 4 5 5 -1

이러한 케이스면 4행에서 5가 중복되었지만 이미 앞에서 다른 값이 나오므로 정답 k는 4가 되어야 하는데 5가 나옵니다.

제가 놓친 부분이 있는지 알려주시면 감사하겠습니다.

snailaww   9달 전

열 단위로 값이 unique 하거나, unique 하지 않다고 길이 k의 prefix가 unique한지 판별할 수 있을까요?

예를 들어

1234

1231

1111

은 모든 열에서 값들이 unique하지 않지만 숫자들을 구분할 수 있습니다.

문제에서 "길이 k"의 prefix가 unqiue한지 물어봤기 때문에 어떤 열에서 값들이 unique하지 않더라도 앞의 열에 있던 값에 따라 충분히 파일들을 구별할 수 있는 상황이 있을 수 있습니다.

그리고 k씩 잘라서 보는 풀이가 존재함에도 굳이 열 단위로 보신 이유가 있으신가요? 문제를 풀 때에는 시간제한이나 메모리 제한을 넘지 않는 선에서 가장 쉬운 풀이를 사용하는 것이 바람직합니다. 구현이 어려운 풀이나, 복잡한 풀이를 선택하면 나중에 "이게 왜 틀렸지?" 하고 의문사를 당하거나 이렇게 잘못된 풀이로 가게 될 가능성이 높습니다.

답변 감사합니다! 그런데 이 코드는 맞힌 사람 코드에서 본 거고 맞았다고 나옵니다.

반례를 직접 대입해 보면 정답이 4이 나와야 하는데 이 코드는 5를 출력하더라고요. 논리적으로 틀린 코드가 정답 처리가 된 걸 보면 현재 문제의 테스트 케이스가 부족해서 통과된 것 같은데, 제가 문제의 조건을 잘못 이해하고 있는 부분이 혹시라도 있을까요? 아니면 단순히 데이터 미비로 보는 게 맞을까요?

snailaww   9달 전

아... 제가 질문을 잘못 이해했네요...

네, 데이터가 약한 것이 맞습니다.

이 문제의 질문 게시판에도 데이터 추가 요청이 올라와 있고 (https://www.acmicpc.net/board/...), 제가 입력된 파일들 중 가장 긴 파일의 길이를 출력하는 코드를 제출했는데도 맞았습니다!! 가 뜨네요.

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