문자열 정렬할 때 실수하기 쉬운부분 복기하기 -줄서기-

1. 문제

 

17178번: 줄서기 (acmicpc.net)

17178번: 줄서기

 

2. 풀이

 

문제를 읽어보면서 구조를 잘 생각해보면..

 

n개의 줄에 다섯명씩 있는데 앞 사람부터 입구에 입장을 할건데

 

티켓 순서대로 입장을 수행한다

 

근데 티켓 순서는 알파벳이 사전 순서대로, 그리고 숫자가 작은 순서대로가 먼저 오는것이다

 

입장을 하는데 내 순서가 아니면 대기줄에서 들어갈 순서가 맞는 사람인지 검사해서 

 

들어갈 사람이면 보내주고 그래도 들어갈 사람이 없으면 

 

현재 대기줄이 아닌 사람은 대기공간에 들어가야할 것이다

 

그래서 입력을 받을때 들어갈 순서를 구해야겠지

 

n개 줄에 5명씩 있는데... 순서를 구하기 위해 순서 리스트에는 하나씩만 넣고

 

현재 줄 서 있는 순서는 그냥 넣어두고

 

from sys import stdin

n = int(stdin.readline())

lines = []

orders = []

for _ in range(n):
    
    line = stdin.readline().rstrip().split()

    lines.append(line)

    for m in line:
        
        orders.append(m)

orders.sort()

 

 

한명씩 들어간 리스트를 오름차순 정렬 위해 orders.sort()로 정렬하면

 

알파벳 사전 순서가 앞으로, 그리고 숫자가 작은 순서대로 앞으로 올것이다

 

그리고 대기공간 리스트 만들고 현재 입장 순서 변수 0번부터 만들고

 

줄이 들어간 lines를 순회해서 시뮬레이션 수행

 

입장순서 orders와 현재 순서 변수 num을 이용해 들어가야하는 사람이 순서에 맞는 사람인지 비교한다

 

들어가는데 성공했다면, success 플래그를 True로 바꿔주고..

 

wait = []

num = 0

for line in lines:
    
    for m in line:
        
        success = False

        if orders[num] == m:
            
            success = True
            num += 1

 

 

그 다음에 대기줄에 있는 사람들이 들어갈 수 있는지 아닌지 검사해본다

 

대기줄 리스트 wait의 마지막 원소가 현재 들어갈 순서에 맞는지 아닌지 검사해보고

 

맞다면 마지막 원소를 빼고 입장순서 num을 증가시키고

 

        while wait:
            
            if wait[-1] == orders[num]:
                
                wait.pop()
                num += 1
            
            else:
                
                break

 

순서가 안맞다면 break를 했는데... 이걸로 끝일까??

 

여기서 생각을 조금 더 해야하는데

 

n개의 줄에 서 있는 사람이 들어가는데 성공했다면 일단 상관없지만

 

현재 순서가 아니라서 들어가지 못했을 경우에..

 

그래도 대기줄 검사를 할거야

 

근데 우연히 대기줄 사람이 들어갈 수가 있었어

 

들어갔다고 쳐... 

 

그러면 입장 순서 num이 1 증가했으므로.. 이 순간에 n개의 줄에 서 있던 사람이 들어갈 수 있을 가능성이 생겼으니까

 

이 순간에 그 사람이 들어갈 수 있는지 아닌지를 검사해봐야한다

 

        while wait:
            
            if wait[-1] == orders[num]:
                
                wait.pop()
                num += 1
                
                if success == False:
                    
                    if orders[num] == m:
                        
                        num += 1
                        success = True
            
            else:
                
                break

 

모든 대기줄을 검사하고 나서도 n개의 줄에 있던 사람이 여전히 들어가지 못했다면???

 

그 사람은 다음을 기약하고 대기줄에 넣어줘야겠지

 

wait = []

num = 0

for line in lines:
    
    for m in line:
        
        success = False

        if orders[num] == m:
            
            success = True
            num += 1
            
        while wait:
            
            if wait[-1] == orders[num]:
                
                wait.pop()
                num += 1
                
                if success == False:
                    
                    if orders[num] == m:
                        
                        num += 1
                        success = True
            
            else:
                
                break
        
        if success == False:
            
            wait.append(m)

 

 

모두 진행했는데 wait가 비어있으면.. 모든 사람이 들어가는데 성공한 것일테고

 

그렇지 않다면 모든 사람이 들어가지 못한 것이니까...

 

if wait == []:
    
    print('GOOD')

else:
    
    print('BAD')

 

 

근데 이렇게 풀면 오답이다

 

마지막으로 놓친 부분이

 

문자열 정렬할때이다

 

그냥 A-201, A-104, B-302, C-201,... 등으로 된 문자열 리스트를 sort()하면

 

앞에 있는 문자 기준으로 정렬하니까.. 알파벳 사전 순서대로, 알파벳이 동일하면 숫자가 작은 순서대로 될거라고

 

생각했는데

 

이게 사실 그게 아니야

 

문자열 정렬의 기본은 앞에 있는 문자끼리 비교하는거야

 

알파벳 사전 순서대로 앞으로 오고...

 

그런데 알파벳도 동일하면... 숫자가 작더라도 나중에 오는 경우가 생길 수 있는데 

 

예를 들어 A-102, A-4를 정렬하면 A-4, A-102가 오리라고 기대하는데

 

사실 A-102, A-4가 먼저온다

 

왜냐하면 문자열 비교에서는 102와 4를 비교하는게 아니라 A, -, 그리고 1과 4를 비교해서 1이 더 작으니까 A-102가 앞으로 온다.

 

 

그래서 정렬 순서 리스트 orders를 넣을때 그냥 넣고 정렬하면 안된다

 

-를 기준으로 split한다음에 알파벳, 숫자의 리스트를 넣어주고 정렬시켜야겠다

 

그러면 앞에 있는 알파벳 기준으로 정렬한다음에, 알파벳이 동일하면 숫자 기준으로 정렬하게 될것이다

 

from sys import stdin

n = int(stdin.readline())

lines = []

orders = []

for _ in range(n):
    
    line = stdin.readline().rstrip().split()

    lines.append(line)

    for m in line:
        
        #- 기준으로 split
        a,b = m.split('-')
        
        #알파벳, 숫자형으로 바꾼 숫자, 합체된 번호를 넣어준다
        orders.append([a,int(b),m])

#정렬하면 알파벳 기준으로 사전순이 앞으로
#알파벳이 동일하면 숫자가 작은게 앞으로
#동일한 티켓은 없으니 마지막 m은 정렬에 영향 없다
orders.sort()

wait = []

num = 0

for line in lines:
    
    for m in line:
        
        success = False

        if orders[num][2] == m:
            
            success = True
            num += 1

        while wait:
            
            if wait[-1] == orders[num][2]:
                
                wait.pop()
                num += 1
            
                if success == False:

                    if orders[num][2] == m:

                        success = True
                        num += 1
            
            else:
                
                break
        
        if success == False:
                
            wait.append(m)
        

if wait == []:
    
    print('GOOD')

else:
    
    print('BAD')