백준, 정렬)수 찾기

2024-07-04 5 분 소요

수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

문제 생각해보기

첫 입력에 n을 입력할거다(예시 : 4를 입력하면 4개의 숫자를 입력가능)

이후 for문으로 n개의 숫자만큼 입력한다

또 다시 n(=m)을 입력후

다시 m개의 숫자만큼 입력한다

출력 예제를 보면

m을 기준으로 하나씩 n과 대조해가면서 출력을하는거같다

입력예제는

n(정렬을 했을때)=12345

m=13795

출력예제

이렇게 나오니 m에서 순차적으로 1이있나? 3이 있나 ? 7이있나 ? 이렇게 하는듯 하다

우선

n을 입력받는다
n만큼의 숫자를 Nnums로 받는다
m을 입력받는다
m만큼의 숫자를 Mnums로 받는다
n을 정렬한다
m을기준으로 n의 값중에 같은 숫자가있으면 1을 출력한다.

StringTokenizer

해당 클래스는 문자열을 우리가 지정한 구분자로 문자영을 쪼개 주는 클래스이다

br.readLine().split(" ");

해당 구문 처럼 하는것보다 StringTokenizer를 사용하는게 좀더 편의성 측면에서 좋다는 이야기를 들어 한번 알아보기로 했다.

생성자(Constructor)

생성자	설명
public StringTokenizer(String str);	절달된 매개변수 str을 기본(default) delim으로 분리합니다. 기본 delimiter는 공백 문자들인 “ \t\n\r\t”입니다.
public StringTokenizer(String str,String delim);	특정 delim으로 문자열을 분리합니다.
public StringTokenizer(String str,String delim,boolean returnDelims);	str을 특정 delim으로 분리시키는데 그 delim까지 token으로 포함할지를 결정합니다. 그 매개변수가 returnDelims로 true일시 포함, false일땐 포함하지 않습니다.

int countTokens()

남아있는 token의 개수를 반환합니다. 전체 token의 갯수가 아닌 현재 남아있는 token 개수입니다.

boolean hasMoreElements(), boolean hasMoreTokens()

다음의 token을 반환합니다. StringTokenizer는 내부적으로 어떤 위치의 토큰을 사용하였는지 기억하고 있고 그 위치를 다음으로 옮깁니다. 두가지 메소드는 모두 같은 값을 반환합니다.

Object nextElement(), String nextToken()

이 두가지 메소드는 다음의 토큰을 반환합니다. 두가지 메소드는 같은 객체를 반환하는데 반환형은 다르네요. nextElement는 Object를, nextToken은 String을 반환하고 있습니다.

출처 : https://reakwon.tistory.com/90

대충 내가 사용할것들을 정리하자면

StringTokenizer st = new StringTokenizer("this is a test");
while (st.hasMoreTokens()) {
    System.out.println(st.nextToken());
}

해당 StringTokenizer은 기본 값으로 문자열값만 받았을때

공백,탭,줄바꿈등을 기준으로 구분한다.

StringTokenizer st = new StringTokenizer("this,is,a,test", ",");
while (st.hasMoreTokens()) {
    System.out.println(st.nextToken());
}

위 기능은 StringTokenizer에 “,”를 또 추가 한것이다

이러면 공백,택,줄바꿈 대신에 , 를 기준으로 구분한다.

첫시도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
 
public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //---------n의수 입력------------
		//받을 수
		int n = Integer.parseInt(br.readLine());
		//n번 만큼 입력될 변수
		int[] Nnums = new int[n];
		//StringTokenizer우로 공백 구분
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++){
			Nnums[i] = Integer.parseInt(st.nextToken());
		}
		
		//---------n의수 입력 끝------------

		//n의수 정렬 하기
		Arrays.sort(Nnums);
		for(int numss : Nnums){
			System.out.println("입력된 넘버 : " + numss);
		}

		//---------m의수 입력------------
		int m = Integer.parseInt(br.readLine());
		//n번 만큼 입력될 변수
		int[] Mnums = new int[m];
		//위에서 토큰의 사용했기때문에 다시 만들어 준다.
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++){
			Mnums[i] = Integer.parseInt(st2.nextToken());
		}
		for(int mumss : Mnums){
			System.out.println("입력된 넘버 : " + mumss);
		}
		//---------m의수 입력 끝------------

		for(int i = 0; i < Mnums.length; i++){
			if(Nnums.equals(Mnums[i])){
				System.out.println("있음");
			}else{
				System.out.println("없음");
			}
		}
		
	}
}

해당 코드로 작성했지만 계속 “없음” 이 출력되었다.

이유를 찾아보니 Java에서는 배열과 정수는 직접적으로 비교를 할수없다고 한다

그렇다면 for문을 하나 더만들어서

Nnums = j의 for문

Mnums= i의 for문을 줘서

읽게 하면 되지 않을까 생각을 해보았다.

하면서 생각하다보니 만약 값을 찾는다고해도

for(int i = 0; i < Mnums.length; i++){
			for(int j = 0; j < Mnums.length; j++){
				if(Nnums[j] == Mnums[i]){
					System.out.println("있음");
				}
			}
			
		}

이렇게 할시 없을을 출력할때가 굉장히 곤란해진다.

이제 어떻게 해야하느냐

그건 boolean값으로 true , false값으로 하면 될거같다

찾았을떄 true값으로 멈추고

j for문을 나와서 true 값일때 “있음”을 출력하고

false가 나올시 j for문을 나와서 “ 없음” 을 출력하면된다.

문제 해결(실패)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
 
public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //---------n의수 입력------------
		//받을 수
		int n = Integer.parseInt(br.readLine());
		//n번 만큼 입력될 변수
		int[] Nnums = new int[n];
		//StringTokenizer우로 공백 구분
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++){
			Nnums[i] = Integer.parseInt(st.nextToken());
		}
		
		//---------n의수 입력 끝------------

		//n의수 정렬 하기
		Arrays.sort(Nnums);
		for(int numss : Nnums){
			System.out.println("입력된 넘버 : " + numss);
		}

		//---------m의수 입력------------
		int m = Integer.parseInt(br.readLine());
		//n번 만큼 입력될 변수
		int[] Mnums = new int[m];
		//위에서 토큰의 사용했기때문에 다시 만들어 준다.
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++){
			Mnums[i] = Integer.parseInt(st2.nextToken());
		}
		for(int mumss : Mnums){
			System.out.println("입력된 넘버 : " + mumss);
		}
		//---------m의수 입력 끝------------
		
		for(int i = 0; i < Mnums.length; i++){
			boolean found = false;
			for(int j = 0; j < Mnums.length; j++){
				if(Nnums[j] == Mnums[i]){
					found = true;
					break;
				}
			}
			if(found == true){
				System.out.println(1);
			}else
				System.out.println(0);
			
		}
		
	}
}

j for문에서 같은 값을 찾았을때 계속 돌아가면 결국 false가 나오기떄문에

true값이 나오면 break로 빠져나오게 만들었다.

라고 잘만든줄 알았지만

제출을 해보니 시간 복잡도에 걸려서 내 머리를 백지로 만들어 버렸다.

아마 이유는 2중 for문 사용으로 그런거 같다.

거기다 m의 값을 받을때 같이 그 값이 n의 정수가 있는지 판단 하면 되는데

m의 정수를 for값으로 다받고 그걸 찾을려하니 한번에 해야할 일을 두번 하는 일이 되었다.

해결 방안

HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션으로, 중복된 요소를 저장하지 않는다.

그렇기 때문에 HashSet에 이미 저장되어 있는 요소를 추가하고자 한다면

객체를 저장하기 전에, 먼저 객체의 hashCode()메소드를 호출해서 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한뒤

같은 해시 코드가 있다면 equals()메소드로 두 객체를 비교해서 true가 나오면 돌일한 객체로 판단하고 중복 저장을 하지 않는다.

ArrayList와 달리 저장순서를 유지하지 않기 때문ㅇ에, 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.

import java.util.HashSet;
 
HashSet<타입> set = new HashSet<>(); // HashSet 객체 생성
HashSet<타입> set = new HashSet<>(int initialCapacity); // 주어진 값을 초기용량으로 하는 HashSet 객체 생성
HashSet<타입> set = new HashSet<>(Collection c); // 주어진 컬렉션을 포함하는 HashSet 객체 생성

스크린샷 2024-07-04 오후 10.12.45

출처 :https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-HashSet-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%82%AC%EC%9A%A9%EB%B2%95

해결된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N의 수 입력 및 배열 A 초기화
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        // M의 수 입력 및 배열 M 초기화
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (set.contains(num)) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        // 결과 출력
        System.out.print(sb.toString());
    }
}

Int[]배열 보다는 HashSet을 사용하여 시간복잡도를 용의하게 하였다

그리고 값을 찾을때 입력을 받자 마자

set.contains(num)를 사용하여 num의 값을 찾는다

contains라는 메서드는 해당요소(위 코드에선 num)이 포함되어 있을결우 true를 반환하고 아닐시 false를 반환한다.

그리고 해당 출력 값들을 바로 출력하지 않고

StringBuilder에 저장하고 for문을 빠져나온다음에

System.out.print(sb.toString());으로 출력을 하였다.

마치며

이번에도 결국 혼자서는 해결을 하지 못하여 검색의 힘을 빌렸다.. 검색을 할때마다 새로운걸 배우긴하지만 아직 배울게 너무 많아서 문제를 풀때마다 결국 혼자 못풀고 검색을 하게된다. 언젠가는 혼자서 풀수 있는 날이 올떄까지 열심히 풀어보겠다.

Twitter Facebook LinkedIn

JaeHwan

백준, 정렬)수 찾기

수 찾기

문제

입력

출력

문제 생각해보기

StringTokenizer

첫시도

문제 해결(실패)

해결 방안

HashSet

해결된 코드

마치며

공유하기

댓글남기기

참고

프로젝트)카카오, 네이버 로그인시 db저장

Mypageupdate

프로젝트)카카오, 네이버 로그인시 db저장

프로그래머스) day 5 기초 코딩