★백준 1920번 수 찾기 C#으로 문제 풀어보기★

안녕하세요 박민성입니다.

 

오늘은 백준 1920번 수 찾기를 풀어 보겠습니다.

문제는 간단합니다.

입력은 1보다 크거나 같고 100,000보다 작거나 같은 N이라는 두 번째 줄에 들어올 숫자들에 개수를 주어줍니다.

두 번째 줄에는 -2^31 보다 크거나 같고 2^31보다 작은 수들이 들어옵니다.

세 번째 줄에도 첫 번째 줄처럼 네 번째 줄에 들어올 수의 개수를 줍니다.

네 번째 줄엔도 두 번째 줄처럼 -2^31 보다 크거나 같고 2^31보다 작은 수들이 들어옵니다.

 

출력은 네번째 들어온 수들 중 두 번째 들어온 수들 중에 같은 것이 있는지 없는지 출력해야 합니다. 있으면 1 없으면 0입니다.

 

저는 문제를 보고 출력할 때 시간초과가 무조건 걸릴 것 같다고 생각했습니다. 예전이었으면 문제를 안풀어겠지만 지금에 저는 

문제를 풀어보기 위해 C#에서 출력을 빠르게 해줄 수 있는 StringBuilder라는 걸 배웠습니다.

간단하게 말하자면 보통 출력을 할 때는 Console.ReadLine()으로 하지만 이걸로 한 줄씩 출력하려면 이 문장을 최대 100,000(N의 최대 입력 값이 100,000 번 호출을 해야 합니다 그렇기 때문에 StringBuilder을 사용해야 합니다.

StringBuilder는 간단하게 미리 문자들을 담아 놓고 출력할 때 한 번만 호출하는 간단한 c#에서 지원하는 클래스입니다.

자세한 건 https://code-piggy.tistory.com/entry/StringBuilder 이분에 블로그를 보고 배웠습니다.

 

처음에는 StringBuilder 객체를 인스턴스화 해주었습니다.

그리고 첫 번째 줄과 두 번째 줄에 입력을 받습니다. 

100,000 공간에 bool 배열도 받습니다.

bool 배열을 받은 이유는 두번째 줄에서 들어온 수를 있는지 없는지 판별하기 위해서입니다.

보통 배열에 때려 박고 있는지 없는지 체크를 for문으로 체크하려면 만약 100,000개가 주어지면 엄청나게 많은 for문을 돌려야 할 것 같아서 불 배열로 그 수를 인덱스로 활용하여 num1 입력으로 들어온 수]에 두 번째 줄에서 들어온 수들에 해당하는 인덱스에 값을 true로 만들어주고 나중에 네 번째 줄에 들어온 수를 체크할 때 그 수들에 인덱스 번호에 값이 true인지 false인지만 확인하면 시간적으로나 효율적으로 좋을 것 같다고 생각하여 bool 배열을 선언하였습니다.

 

제가 말한 방법대로 들어온 수들에 해당하는 인덱스 번호에 값을 true로 바꿔줍니다.

그리고 세 번째 줄과 네 번째 줄 입력을 받아주고

for문을 이용하여 네번째 줄에 들어온 수들에 인덱스 번호에 값이 true인지 아닌지를 if문을 사용하여 1 아니면 0을 넣어줍니다.

그리고 마지막으로 출력을 해주면 끝입니다.

 

하지만 이 코드는 틀렸습니다

왜냐하면 두 번째 줄, 네 번째 줄에 들어오는 수는 -2^31 보다 크거나 같고 2^31보다 작은 수들입니다.

하지만 지금 이 방법대로 한다면 문제가 생길 것입니다.

왜냐하면 인덱스는 -값이 안 들어갈뿐더러 그런 값이 모두 들어간 배열을 만들 수 없습니다.

 

그렇기 때문에 저는 Dictionary를 사용하기로 Dictionary란 간단하게 key와 value를 세트로 만들어서 사용할 수 있게 만드는 것입니다. 자세한 설명은 https://engineer-mole.tistory.com/174 이분에 블로그를 보고 배웠습니다. 

StringBuilder를 객체와 시켜주고

Dictionary는 인덱스 번호를 타입으로 받을 수 있습니다. 저는 이 문제를 풀기 위해 key는 string으로 값 value는 bool 값으로 저장하겠습니다. 

그리고 입력도 한 번에 받아줍니다.

그리고 string으로 파씽을 하고 false로 입력한 수들을 넣어줍니다.

그리고 Dictionary가 제공하는 메서드 중 ContainsKey라는 있는지 없는지 검색할 수 있는 메서드가 있어서 네 번째 줄에 입력이 들어온 값이 Dictionary에 있는지 검사하고 있으면 1 없으면 0을 sb에 담아줍니다.

마지막으로 출력까지 하면 진짜로 끝입니다.

이것이 전체 코드입니다.

제출하실 때에는 using문까지 다 적어야 합니다

이렇게 백준에 제출하였더니 

정답이었습니다.