[ BOJ 오답노트 ] 18870 파이썬 : 좌표 압축

2022-02-26

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 일단 문제를 아주 얕잡아 봤다. 그래서 단순히 정렬만으로는 해결할 수 없는 문제라는 것을 알고 좀 더 오랫동안 고민했다.

- 입력 범위가 1 ~ 1000000이므로 되게 크기 때문에 단순히 sort를 하고 for문으로 자신보다 작은 것의 개수를 세는 방식으로는 분명히 Time Out 결과가 뜰 것이라고 생각했다.

- 입력된 순서대로 출력을 해야하기 때문에, 인덱스 값을 기억해야 했다. 그래서 2차원 리스트를 사용했다.

 

(1) 내가 생각한 풀이

- lst로 입력을 받는다.

- lst_premium에 인덱스와 lst의 원소들을 순서대로 2차원 리스트 화해서 저장한다.

[ [index, value], [index, value], [index, value], ... ,[index, value] ]

 

- lst_premium의 value 값을 기준으로 오름차순 정렬해준다.

- for문으로 길이 n만큼 반복한다.

 

- 현재 값 i와 그 다음 값 i+1을 비교해서 i+1번째 값이 더 크다면,

i번째 원소에 lst_premium[i-1][2] + 1을 append 해주어, 그 전 원소의 순위에 +1을 해주어야 한다. 이렇게 하면 [index, value, rank] 값이 lst_premium의 원소가 된다.

 

- 현재 값 i와 그 다음 값 i+1을 비교해서 두 값이 같다면,

i번째 값의 rank와 i+1번째 값의 rank 값을 같은 값으로 append 해준다.

 

 

(2) 첫번째 런타임 에러 (indexError)

n = int(input())
lst = list(map(int, input().split(' ')))
lst_premium = []

for i in range(n):
    lst_premium.append([i, lst[i]])

lst_premium.sort(key=lambda x: x[1])

for i in range(n-1):
    if lst_premium[i+1][1] > lst_premium[i][1]:
        if i == 0:
            lst_premium[i].append(i)
        else:
            if len(lst_premium[i]) == 2:
                lst_premium[i].append(lst_premium[i-1][2] + 1)
    elif lst_premium[i+1][1] == lst_premium[i][1]:
        if len(lst_premium[i]) == 2:
            if i == 0:
                lst_premium[i].append(0)
                lst_premium[i+1].append(0)
            else:
                rank = lst_premium[i-1][2] + 1
                lst_premium[i].append(rank)
                lst_premium[i+1].append(rank)
        else:
            lst_premium[i+1].append(lst_premium[i][2])

lst_premium.sort(key=lambda x: x[0])

for i in range(n):
    print(lst_premium[i][2], end=' ')

- 이 코드로 실행해보면 lst_premium의 마지막 원소가 연산되지 않는다.

 

- for i in range(n-1)로 반복해주었기 때문이다. 왜 n이 아니라 n-1로 했냐면, 마지막 원소가 그 다음 값이 없는 상태에서 비교 연산이 진행되기 때문에 n-1로 해주었다. 

 

- 이 부분에서 마지막 요소가 연산되지 않고 덩그러니 남게 된다는 것을 깨닫고 수정했다.

 

 

(3) 두번째 런타임 에러 (indexError)

n = int(input())
lst = list(map(int, input().split(' ')))
lst_premium = []

for i in range(n):
    lst_premium.append([i, lst[i]])

lst_premium.sort(key=lambda x: x[1])

for i in range(n-1):
    if lst_premium[i+1][1] > lst_premium[i][1]:
        if i == 0:
            lst_premium[i].append(i)
        else:
            if len(lst_premium[i]) == 2:
                lst_premium[i].append(lst_premium[i-1][2] + 1)

    elif lst_premium[i+1][1] == lst_premium[i][1]:
        if len(lst_premium[i]) == 2:
            if i == 0:
                lst_premium[i].append(0)
                lst_premium[i+1].append(0)
            else:
                rank = lst_premium[i-1][2] + 1
                lst_premium[i].append(rank)
                lst_premium[i+1].append(rank)
        else:
            lst_premium[i+1].append(lst_premium[i][2])

if len(lst_premium[n-1]) == 2:
    lst_premium[n-1].append(lst_premium[n-2][2] + 1)


lst_premium.sort(key=lambda x: x[0])

for i in range(n):
    print(lst_premium[i][2], end=' ')

- 위에서 발견한 오류를 수정해서 len(lst_premium[n-1]) == 2일 때, 즉 마지막 원소의 rank가 결정되지 않았을 때에 마지막에서 두번째의 rank 값에 +1을 해주었다. 

 

- 마지막 원소의 rank가 자동 결정되는 때가 있냐고 하면, 마지막에서 두번째 원소와 마지막 원소가 서로 같다면, lst_premium[i].append(rank)와 lst_premium[i+1].append(rank)을 해주면서 자동 결정되고 append까지 되기 때문에 len(lst_premium[n-1]은 3이 된다.

 

- 하지만 이번에도 indexError가 떴는데, 그 이유를 도저히 모르겠어서 커뮤니티에 질문글을 올렸다.

- n이 1인 경우에는 for문이 실행되지는 않지만, if len(lst_premium[n-1]) == 2에 걸리면서 존재하지도 않는 -1번 인덱스와 -2번 인덱스를 조사하게 된다. 역시나 index에 의한 에러였다.

 

 

 

3. 해결

n = int(input())
lst = list(map(int, input().split(' ')))
lst_premium = []

for i in range(n):
    lst_premium.append([i, lst[i]])

lst_premium.sort(key=lambda x: x[1])

for i in range(n-1):
    if i == 0:
        if lst_premium[i+1][1] > lst_premium[i][1]:
            lst_premium[i].append(0)
        elif lst_premium[i+1][1] == lst_premium[i][1]:
            lst_premium[i].append(0)
            lst_premium[i+1].append(0)

    else:
        if lst_premium[i+1][1] > lst_premium[i][1]:
            if len(lst_premium[i]) == 2:
                lst_premium[i].append(lst_premium[i-1][2] + 1)

        elif lst_premium[i+1][1] == lst_premium[i][1]:
            if len(lst_premium[i]) == 2:
                rank = lst_premium[i-1][2] + 1
                lst_premium[i].append(rank)
                lst_premium[i+1].append(rank)
            else:
                lst_premium[i+1].append(lst_premium[i][2])


if len(lst_premium) == 1:
    print(0)
else:
    if len(lst_premium[n-1]) == 2:
        lst_premium[n-1].append(lst_premium[n-2][2] + 1)

    lst_premium.sort(key=lambda x: x[0])
    print(' '.join(map(str, [lst_premium[i][2] for i in range(n)])))

- n == 1 일 때는 깔끔하게 0을 출력해주도록 했고, n이 1이 아닐 경우에만 길이가 2인지 조사하고 출력을 진행하도록 해주었다.

 

 

 

4. 배운점

- 가장 간과하기 쉬운 n이 1일 때를 잘 생각하자.

- 이번에도 되게 간결한 문법 하나를 알아냈다. 2차원 리스트에서 특정 인덱스 원소들만 출력할 때 사용하기 좋은 문법이다.

print(' '.join(map(str, [lst_premium[i][2] for i in range(n)])))

- 리스트 관련 문제에서는 인덱스를 꼼꼼하게 따져보자.