백준 10813 c++ 풀이

 

이번 문제는 10810 문제와 굉장히 비슷하지만 더 어려워진 문제였습니다.

전 엉뚱한 곳에서 시간을 계속 썼네요.

대충 30분 정도면 풀릴 정도의 난이도인 문제였습니다.

정답을 보고싶으신 분들은 맨 아래로 내리시면 답이 있습니다.

 

서론은 여기까지 하고 문제 설명을 간략하게 하겠습니다.

 

바구니 N개에 각각 1~N까지 번호가 매겨져 있다.

모든 바구니에는 공이 1개씩 들어있고, 처음엔 바구니의 번호와 일치하다.

앞으로 M번 공을 바꾸려고 한다.

바꿀 바구니를 2개 선택 후 두 바구니에 있는 공을 교환하는 형식이다.

M번 바꾼 이후 두 바구니에 들어있는 공을 구하는 프로그램을 구하시오.

 

 

첫 번째 시도)

 

 

std를 너무 쓰다보니까 가끔 까먹어서 이번엔 namespace를 안쓰고 해보았습니다.

확실히 알고리즘 문제를 풀 때는 namespace가 편하더라구요.

여기서 틀린 점을 보니 첫번째 반복문에서 m번 반복하도록 했더라구요.

m은 여기서 공을 바꾸는 횟수일 뿐이지 바구니의 갯수가 아니었기에 이걸 고친 후 다시 시도했습니다.

 

 

두 번째 시도)

 

 

 

또 틀렸습니다.

코드를 복기해보니 우선 바구니에 각각 번호를 매기는 반복문은 틀린 것이 없었고

마지막인 출력 형식에도 문제가 없었습니다.

고로 전 바꾸는 과정에서 문제가 있었음을 깨닫고 바로 고쳐주었습니다.

 

 

세 번째 시도)

 

 

 

두 번째 시도의 문제점은 바꾸는 과정에서 현재 해당 인덱스의 값을 사용하는 것이 아니라

입력받은 번호를 바꾼 것이었습니다.

그걸 고쳤더니 이번에는 출력 형식이 잘못되었다고 떠서 여기서 시간을 15분 정도 쓴 듯 합니다.

하지만 문제점을 알고 고쳤습니다.

 

 

정답)

 

 

 

틀린 점은 줄바꿈에 있었습니다.

cin은 새로 입력을 받을 때마다 줄바꿈을 하는데 그걸 까먹곤 또 줄바꿈을 한 것이었습니다.

오랜만에 해서 그런지 헷갈린 것도 컸네요.

어쨌든 cin의 특성을 다시 깨달았으니 만족합니다.

하지만 제 정답 코드는 가독성이 매우 떨어져보였기에 약간 고친 후에 코드 설명을 드리도록 하겠습니다.

 

 

개선)

 

 

 

제 최종 코드입니다.

하나하나 꼼꼼히 설명드리겠습니다.

 

 문제에서 N, M, i, j라는 변수를 예로 들었지만 i와 j는 반복문을 사용할 때 보편적으로 사용되는 변수이므로 a와 b로 변경하였습니다.

array의 크기를 101로 정한 이유는 최대 바구니의 크기가 100이라서 그렇습니다.

 사실 함수를 만들지 않아도 되지만 가독성을 위해 그렇게 하였습니다.

swap이란 함수에 인덱스 값을 2개를 받도록 설정했고

임시 변수를 만들어 첫 번째 인덱스의 값을 저장해두었습니다.

이유로는 임시 변수가 없으면 두 번째 인덱스의 값을 바꿀 때 이미 첫 번째 인덱스의 값이 바뀌었기에 바뀌기 전의 값을 알 수 없기 때문입니다.

그렇기에 저장한 이후 다시 사용한 것입니다.

 

 그 다음 배열의 번호를 매겨주기 위해 바구니 갯수를 활용해 매겨주었습니다.

이후엔 공을 바꾸는 횟수인 m을 활용해 m번 반복하는 반복문을 만들었고 전 문단에서 설명한 swap 함수를 사용해 바꾸었습니다.

 

 이후 예제 출력을 참고해 각 값마다 공백으로 구분해 출력하면 끝입니다!

코드 짜는 것보다 이걸 쓰는게 더 오래걸리네요;;

 

어쨌든 cin은 줄바꿈이 된다는 것을 상기했음에 만족하고 그럼 이만