오늘부터 푼 백준 문제 정리한다.
12867번: N차원 여행
boj.ma
간단한 문제 설명
주어진 N차원 좌표, (a, b, c, d, e, ...)(최대 1,000,000,000 차원) 에서,
한번에 한 차원을 +1, -1 움직일 수 있다.
이런식으로 M번 움직일 때, 중복되는 좌표가 존재하는지 판단하는 문제이다.
예시로는 (0, 0, 0) -> (1, 0, 0) -> (1, 0, 1) -> (1, 0, 0)
위의 여행은 (1, 0, 0) 이 중복된다.
감상
실버2 라서 만만하게 봤는데....
생각보다 오래 걸렸다.
설마 이렇게 풀겠어? 하고 생각난 풀이를 망설인 점,
풀이 방법의 구현
2가지를 원인으로 뽑을 수 있을거 같다.
설마 이런 자료구조를 쓰겠어?
왜 처음 풀이를 망설였나하면....
풀이에 필요하다고 판단된 자료구조가 상당히 복잡했기 때문이다.
차원의 최대 크기가 1,000,000,000 이지만,
여행의 횟수가 최대 50번이기 때문에 아무리 모든 차원이 다르더라도, 50개의 종류밖에 되지 않는다.
이 점을 활용하면, 좌표 압축을 떠올릴 수 있다. 이를 위해서 map 자료구조를 떠올릴 수 있었다.
즉, 하나의 상태는 map 하나로 나타낸다.
이 상태를 이전 상태들과 비교해서 같은지 다른지 일일이 비교해도 괜찮다.
최대 상태의 개수가 50개이기 때문이다.
그럼 이제 상태들을 저장하는 자료구조가 필요한데, 슬라이스로 간단하게 표현할 수 있다.
이를 정리하면,
[]map[int]int와 같은 자료구조를 사용하면 된다.
하나하나 분해해보자.
[] // map[int]int앞의 빈 대괄호는 슬라이스라는 의미이다. 다음에 나오는 자료구조를 하나의 원소로 갖는 슬라이스라는 의미이다.
map[int]intGolang에서의 hashtable로, int형 key와 int형 데이터를 갖는다.
([] 안에 key의 자료형, 뒤에 value의 자료형이 온다)
풀이의 구현
큰 풀이는 각 상태를 map 으로 저장하여, 그 전상태와 비교하여 같은지 다른지 판단하면 된다.
전체 풀이는 한 줄이지만, 조금 상세하게 쪼개보면,
- 각 상태 저장
- 다른 상태와의 비교
2가지로 나눌 수 있다.
상태 저장은 어렵지 않았다. 위의 자료구조로 구현하기로 결정했다면, 초기화와 입력을 잘 받아주면 된다.
다른 상태와의 비교는 생각할 부분이 조금 있다.
상태 2개에 대해 비교하는 compare 함수가 있을 때, 이에 대한 구현에 해당하는 문제인데,
고려할 부분이 있다.
좌표 압축으로 인한 0과 nil 과의 차이점
우리는 좌표압축으로서, 차원을 key로 그 차원의 값을 value 로 삼을 것이다.
이에 대한 전제는 모든 차원의 기본값이 0으로 1,000,000,000 개의 차원을 만들어 0으로 만들 수 없으니,
빈 차원은 0이라고 가정해야 한다.
즉, 빈 map, nil 은 (0, 0, 0, 0...) 과 같은 상태라는 것이다.
특정 차원에 대해서 두 상태가 다르다는 것을 나타내는 boolean 식은 다음과 같다. (같다에 대한 부정으로 표현되었다. !같다 == 다르다)
!((!exist && (val == 0)) || (exist && (val == v)))두 상태가 같다는 것은
만약 값이 존재하지 않는다면, 비교하는 대상도 0 이어야하고,
값이 존재한다면, 두 상태의 값이 같아야한다.
이 때, 누구를 기준으로 for문을 돌리는지도 중요하다.
예시를 통해 알아보자.
a = (1, 0, 0, 1)
b = (1, 0, 1, 1) 라고 가정해보자.
// input
// a = {1: 1, 2: 0, 4: 1}
// b = {1: 1, 2: 0, 3: 1, 4: 1}
func compare(a, b *map[int]int) bool {
for idx, val := range *a {
if v, exist := (*b)[idx]; !((!exist && (val == 0)) || (exist && (val == v))) {
return false
}
}
return true
}유의할 점은 a[3] = 0 이 아니라는 점이다.
좌표 압축을 활용했기 때문에 b 의 상태가 되면서 처음 변한 3번째 차원은 이전에는 값이 nil이다.
반면에 2번째 차원은 전에 입력으로 주어진 적이 있다. 더하고 빼다보니 우연히 그 값이 0이 되었을 뿐이다.
즉, 시점은 b가 a 보다 뒤인 시점이다.
이 상황에서 a를 기준으로 for문을 돌리게 되면, 1, 2, 4번째 차원"만" 확인하게 되고, 모두 통과되어 true 값을 반환할 것이다.
하지만, 좌표상으로 두 상태는 같지 않다.
이를 막기 위해 더 뒤 시점인 b가 for문을 돌아야한다.
b가 for문을 돈다면, 3번째 차원에서 a가 값이 존재하지 않지만, b 상태의 값이 0 이 아니기 때문에 false 가 반환될 것이다.
정리
이 문제에서 중요한 점을 정리해보면,
전체 차원 수에 비해, 여행의 길이가 압도적으로 짧다는 점을 통한 좌표 압축,
역시 여행의 길이가 짧다는 사실을 통해 선형 탐색을 해도 문제 없다는 점을 파악,
(Golang 한정) nil 이 0 을 같게 비교함수 조정
(내 함수 한정) 순서에 따라 결과값이 달라질 수 있다는 점
인거 같다.
여담
자랑을 조금 하자면 내가 Golang 최초 정답자이다! 야호
(사실 이거 자랑하려고 블로그글 썼어요 ㅎ...)