[백준] 2562번 최대값

앞에 문제보다 더 쉬운 문제이다. 최대값의 경우 배열에서 Max()를 이용해서 바로 구할 수도 있지만, 현재의 경우에는 어짜피 몇번째 콘솔입력인지 알기위해 for문을 돌려야하기 때문에 배열로 치환하지 않고 바로 최대값 또한 같이 구해주면 한번의 반복문으로 원하는 결과 2가지를 모두 얻을 수 있다.

나의 풀이

int maxNum = 0, count = 0;
for(int i = 0; i < 9; i++){
    int num = int.Parse(Console.ReadLine());
    if(num > maxNum) {
        maxNum = num;
        count = i+1;
    }
}
Console.WriteLine(maxNum);
Console.WriteLine(count);

어짜피 문제는 자연수로 주어지기로 되어있고, 반드시 100이하의 수가 반드시 9개가 들어온다는 전제가 있어서 위와 같이 풀이하였다.

만약 들어오는 수가 자연수가 아닌 음수(-)를 포함하고, 들어오는 개수를 알 수 없을 때는 어떻게 풀어야할까?

일단 내 코드의 경우 maxNum과 for문의 조건식이 잘못되게 된다.

내 코드에서 손을 본다면 maxNum의 초기값은 0이 아닌 int가 가질 수 있는 최소값 즉 int.MinValue가 될것이다.

또한 for문은 while문을 이용하여 다음 입력이 null일때 반복문을 종료해주는 방식을 채택할 수 있을 것 같다.

int maxNum = int.MinValue, count = 0, maxNumCount = 0;
string str = Console.ReadLine();
while(str != null){
	int num = int.Parse(str);
	count++;
	if(num > maxNum) {
		maxNum = num;
		maxNumCount = count;
	}
	str = Console.ReadLine();
}
Console.WriteLine(maxNum);
Console.WriteLine(maxNumCount);

다른사람 풀이

int[] n = new int[9];
for(int i = 0; i<9; i++)
    n[i] = int.Parse(Console.ReadLine());
Console.WriteLine($"{n.Max()}\n{Array.IndexOf(n, n.Max())+1}");

나는 당연하게 for문이 for문의 반복횟수n일 때 O(n)의 시간복잡도를 가지고 있고, Max() Array.IndexOf()메소드 또한 배열을 돌면서 해당값을 찾아야하기 때문에 각각 O(n)의 시간복잡도를 갖을거라 생각했다. 따라서 총 3 O(n)에 시간복잡도가져서 실행시간적인 부분에서 손실이 있을것이라 판단해 "나의풀이"와 같이 풀이 하였는데, 이렇게 풀이하여도 시간차이는 4ms밖에 차이나지 않았다.

이유가 뭘까? 결국 O(n)과 O(n)*3 의 시간복잡도는 현재 입력되는 콘솔입력갯수가 9개로 정해져있을 때는 굉장히 낮은 반복횟수를 갖기 때문에 시간적 차이가 거의 발생하지 않아서 이다. 만약 입력갯수가 10만개 100만개로 늘어나면 당연히 그에따라 시간차이가 늘어나겠지만, 현재 발생하는 구동 시간은 배열의 반복에서 발생하는 시간보다 시스템을 구성하는 시간이 거의 대부분을 차지하기 때문일 것이라 판단한다.