[BOJ] 1205. 등수 구하기 (Java)

문제 링크 / level: Silver IV

https://www.acmicpc.net/problem/1205

1205번: 등수 구하기

 

 

내가 생각한 풀이

기분전환 좀 할 겸 대학생 기본반 문제집에 있는 것 중에 어렵지 않은걸로 하나 골라서 풀어봤다.

오늘은 거두절미하고 바로 시작!

내가 생각한 로직!

이 문제가 만약 입력받을 때 들어오는 점수가 내림차순이 아니라 무작위였다면 조금 더 귀찮았을 것이고, 새로 삽입해야 하는 점수가 송유진의 새로운 점수 1개만이 아니라 여러 개였다면 조금 더 귀찮았겠지만... 귀찮을만한 부분은 전부 문제에서 알아서 처리해준 편이라 꽤 간단하게 풀 수 있었다.

가즈아!

나는 LinkedList를 활용해서 문제를 풀었다.

 

메모장에 적어뒀지만 그래도 간단히 로직에 대해 설명하자면,

랭킹 목록에 점수가 하나도 없다면(N==0) 송유진의 점수가 무조건 1등이므로 더이상 볼 필요도 없이 끝. (왜냐? P는 10이상이니까)

 

그 외의 경우는...

1. 주어지는 N개의 목록이 어차피 내림차순으로 주어지기 때문에 들어오는 순서대로 리스트에 저장하면 된다.

2. 만약 리스트의 사이즈(는 곧 N의 값과 같다)가 P와 같은데 현재 랭킹 마지막 순위에 있는 점수보다 송유진의 점수가 작거나 같을시 랭킹 리스트에 올라갈 수 없으므로 끝낸다. '새 점수가 이전 점수보다 더 좋을 때만 점수가 바뀐다.'는 조건이 있기 때문에 점수가 같은 경우도 제외다.

3. 그 외의 경우에는 랭킹에 새롭게 올라갈 수 있는 경우들이다. 리스트를 쭉 돌면서 송유진의 점수보다 같거나 작은 점수를 발견하면 해당 점수의 앞자리에 송유진의 점수를 끼워넣는다고 생각하면 된다. 즉, 현재 index에 점수가 끼워넣어지는 것이므로 i+1를 출력해주고 끝낸다. (나는 리스트 인덱스 0부터 그냥 써서 +1 해줘야 함)

단, 이때 같은 점수가 여러 개일 수도 있기 때문에 출력하고 나서 return으로 끝내줘야함. 안그러면 조건을 만족하는 값이 존재하는 만큼 여러 번 출력될 수 있음.

// 핵심 코드
int size = rank.size();
if (size == P && (score <= rank.get(size-1))) { // 랭킹에 올라갈 수 없을 때
	System.out.println(-1);
} else { // 랭킹에 올라갈 수 있을 때
	for (int i = 0; i < size; i++) {
		if(score >= rank.get(i)) {
			System.out.println(i+1);
			return;
		}
		if (i == size-1) {
			System.out.println(size+1);
		}
	}
}

핵심 코드는 이렇다.

그런데 2번의 틀렸습니다-를 겪었다.😂

 

첫 번째는 로직의 3번에서 return 넣는걸 깜빡해서 그랬고,

두 번째는 모르겠어서 반례를 찾아봤다. (여러 개의 글을 뒤져봄🙄)

 

9 5 10  10 10 10 9 9 8 7 6 6  output: 9  correct answer: 10

※반례 출처: 링크

 

그리고 발견한 이유:

만약 else로 들어간 상황에서 N < P 이면서 if(score >= rank.get(i)) 이 조건문에 한 번도 걸리지 않을 경우 출력이 안됨.

즉, 아직 랭킹에 들어갈 자리는 비어있는 상황에서 송유진의 점수가 맨 마지막에 등록되는 경우 저 조건문에 걸리질 않는 것이었다.

 

그래서 for문을 마지막까지 꽉 채워서 도는 경우 랭킹 마지막 순서에 해당하는 값을 출력하고 끝내는 로직을 추가해줬다.

이전에 랭킹에 올라갈 수 없는 경우를 한 번 걸러줬기 때문에 이곳에서 for문의 마지막까지 돌 경우 랭킹 목록의 맨 마지막 순위로 추가된다는 것을 보장할 수 있다.

 

휴~~ 성공!😁👍

 

 

💌 전체 코드 보기:

https://github.com/psS2mj/Problem_Solving_BOJ_by_JAVA/blob/master/Silver/Main_1205_%EB%93%B1%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0.java

psS2mj/Problem_Solving_BOJ_by_JAVA