[SWEA] [파이썬 SW 문제해결 기초] 1. List1

본격적으로 하기 전에 문제만 조금 훑어봤는데 문제가 지금 누가 봐도 "니가 날 푼다고?" 이러고 말하는 것 같다. 포기하고 싶지만 지금 포기하면 아무 것도 안되겠지.

 

4828. N개의 양의 정수에서 가장 큰 수와 가장 작은 수의 차이를 출력하시오.

[입력]
첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 50 )
각 케이스의 첫 줄에 양수의 개수 N이 주어진다. ( 5 ≤ N ≤ 1000 )
다음 줄에 N개의 양수 ai가 주어진다. ( 1 ≤ ai≤ 1000000)

[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

T = int(input())		# 테스트 케이스 개수 T

for test_case in range(1, T+1):		# 테스트 케이스 개수만큼 반복
    N = int(input())		# 양수의 개수 N
    arr = list(map(int, input().split()))		# 정수 각각 리스트 요소로 저장
    
    max_val = arr[0]		# 최댓값: 첫번째 element
    min_val = arr[0]		# 마찬가지로 최솟값도 첫번쨰 element
    
    for i in range(1, N):		# 양수 개수만큼 반복
        if max_val < arr[i]:
            max_val = arr[i] 
    for i in range(1, N):
        if min_val > arr[i]:
            min_val = arr[i]
    
    sub_val = max_val - min_val
    
    print(f"#{test_case} {sub_val}")

아직까지는 쉬운 축에 속한다. 근데 너무 피곤해서 다음 문제부터는 내일 풀어야지... 잠시 임시저장....

다음 날 정신 차리고(정신 차리니 12시 40분) 다시 한 번 풀어봤는데, 멀쩡한 정신으로 푸니 쉽다. 역시 사람은 잠을 잘 자야해.

 

★4831. A도시는 전기버스를 운행하려고 한다. 전기버스는 한번 충전으로 이동할 수 있는 정류장 수가 정해져 있어서, 중간에 충전기가 설치된 정류장을 만들기로 했다. 버스는 0번에서 출발해 종점인 N번 정류장까지 이동하고, 한번 충전으로 최대한 이동할 수 있는 정류장 수 K가 정해져 있다. 충전기가 설치된 M개의 정류장 번호가 주어질 때, 최소한 몇 번의 충전을 해야 종점에 도착할 수 있는지 출력하는 프로그램을 만드시오. 만약 충전기 설치가 잘못되어 종점에 도착할 수 없는 경우는 0을 출력한다. 출발지에는 항상 충전기가 설치되어 있지만 충전횟수에는 포함하지 않는다.

이건 문제부터 잘 이해해야 할 것 같다. 갑자기 복잡하게 나오잖아. 흐음.

# 초안
T = int(input())		# 노선 수 = 테스트 케이스 수

for test_case in range(1, T+1):
    # N: 종점 번호
    # K: 최대한 이동 가능한 정류장 수
    # M: 충전기가 설치된 정류장 개수
    K, N, M = map(int, input().split(' '))
    M_arr = list(map(int, input().split(' ')))		# 충전기가 설치된 정류장 번호
    
    charging_station = [0] * (N+1)      # station이 0에서부터 시작하니까 0~10
    for i in M_arr:
        charging_station[i] = 1		# 전체 정류장 중 충전기가 있으면 1로 표시
    
    location = 0		# 현재 위치
    charging = 0		# 충전 횟수
    
    while (location < N):		# 현재 위치가 종점 위치가 될 때까지
        # 이제 충전소 찾기
        # 1. 갈 수 있는 충전소가 딱 최대 거리인 경우
        # 2. 그보다 안 쪽인 경우
        # 3. 더 바깥쪽인 경우
        for j in range(0, K+1):
            if charging_station[location + K - j] == 1:
                location = location + K - j
                charging += 1
                break
        else:
            charging = 0
            break
    
    print(f"#{test_case} {charging}")

처음에 이렇게 작성했는데 계속 IndexError가 나오는 이유는 뭘까??아무래도 모르겠어서 gpt한테 설명을 부탁.
내 문제는 'location < N'이 아니라 'location + K < N'을 써야 한다는 것이었는데, 현재 위치에서 마지막 station까지 가는 거니까 'location < N'이 맞는 게 아닌가 했다. 그래서 다시 재질문...
'location + K < N'의 의미 자체가, 이번 충전으로는 종점까지 못 가니까 충전소를 찾아야 한다는 의미라고 한다.
그러니까, 먼저 최대 위치+현재 위치를 했을 때 도달 가능성을 체크하고 나서, 그 안에서 충전소를 찾는 거군.
그리고 'location + K >= N'이면 그냥 도달 가능하니까 while문에서 나오고.
쓰면서 정리하다 보니까 이해가 슬슬 가기 시작한다. 이걸 다시 코드로 작성하면

# 1차 수정
T = int(input())		# 노선 수 = 테스트 케이스 수

for test_case in range(1, T+1):
    # N: 종점 번호
    # K: 최대한 이동 가능한 정류장 수
    # M: 충전기가 설치된 정류장 개수
    K, N, M = map(int, input().split(' '))
    M_arr = list(map(int, input().split(' ')))		# 충전기가 설치된 정류장 번호
    
    charging_station = [0] * (N+1)      # station이 0에서부터 시작하니까 0~10
    for i in M_arr:
        charging_station[i] = 1		# 전체 정류장 중 충전기가 있으면 1로 표시
    
    location = 0		# 현재 위치
    charging = 0		# 충전 횟수
    
    while (location + K < N):		# 한 번의 충전으로는 종점에 도달 불가능한 경우
        # 이제 충전소 찾기
        # 1. 갈 수 있는 충전소가 딱 최대 거리인 경우
        # 2. 그보다 안 쪽인 경우
        # 3. 더 바깥쪽인 경우
        for j in range(0, K+1):
            if charging_station[location+K-j] == 1:
                location = location + K - j
                charging += 1
                break
        else:
            charging = 0
            break
    
    print(f"#{test_case} {charging}")

이렇게 된다. 자신감 있게 제출 눌렀는데 이번에는 시간 초과 문제가 생겼다... 테스트 케이스 넣어서 다시 확인해보다가 2번째 테스트 케이스에서 막힌 거 발견. 2번 테스트 케이스는 1번 케이스와 달리 충전소 사이 거리가 더 먼 부분이 있다.

# 최종 코드
T = int(input())		# 노선 수 = 테스트 케이스 수

for test_case in range(1, T+1):
    # N: 종점 번호
    # K: 최대한 이동 가능한 정류장 수
    # M: 충전기가 설치된 정류장 개수
    K, N, M = map(int, input().split(' '))
    M_arr = list(map(int, input().split(' ')))		# 충전기가 설치된 정류장 번호
    
    charging_station = [0] * (N+1)      # station이 0에서부터 시작하니까 0~10
    for i in M_arr:
        charging_station[i] = 1		# 전체 정류장 중 충전기가 있으면 1로 표시
    
    location = 0		# 현재 위치
    charging = 0		# 충전 횟수
    
    while (location + K < N):		# 한 번의 충전으로는 종점에 도달 불가능한 경우
        # 이제 충전소 찾기
        # 1. 갈 수 있는 충전소가 딱 최대 거리인 경우
        # 2. 그보다 안 쪽인 경우
        # 3. 더 바깥쪽인 경우
        for j in range(0, K):	# K+1 -> K로 수정
            if charging_station[location+K-j] == 1:
                location = location + K - j
                charging += 1
                break
        else:
            charging = 0
            break
    
    print(f"#{test_case} {charging}")

딱 for j in range(0, K+1)에서 for j in range(0, K)로만 수정했는데 원활히 잘 돌아감. 왜일까 생각해보다가 다시 gpt 님께 물어봤더니, 자기 자리에 충전소가 있다는 이유로 그 자리에서 무한 루프에 빠지기 때문이라고 했다. 결국 버스가 그 자리에서 출발을 못하고 있었던 거구나...이런 문제에서는 자기 자리를 제외하고 앞에 충전소가 있는지 찾아야 한다! 그리고 한 번의 충전으로는 목적지에 도달이 불가능하다는 조건을 맨 처음 루프문에... 이렇게 쓰니까 복잡하네. 일단 나중에 다시 풀어봐야 할 듯 싶다.

 

4834. 0에서 9까지 숫자가 적힌 N장의 카드가 주어진다. 가장 많은 카드에 적힌 숫자와 카드가 몇 장인지 출력하는 프로그램을 만드시오. 카드 장수가 같을 때는 적힌 숫자가 큰 쪽을 출력한다.

T = int(input())		# 테스트 케이스 번호

for test_case in range(1, T+1):
    N = int(input())		# 총 카드 개수
    arr = list(map(int, input()))		# 숫자 카드 리스트화
    count = [0] * 10
    
    # 일단 가장 많은 카드에 적힌 숫자부터 찾기
    # 1. 카드 개수 세기
    for i in range(0, N):
        tmp = arr.pop()
        count[tmp] += 1

    # 2. 가장 많은 수 구하기
    max_num = count[0]
    max_key = 0
    
    for k in range(len(count)):
        if max_num <= count[k]:
            max_num = count[k]
            max_key = k
    
    print(f"#{test_case} {max_key} {max_num}")

이번에는 좀 쉽게 했다. 중간에 같은 개수의 숫자는 어떻게 처리할지 방황하다가 그냥 if문의 '<'를 '<='로 바꾸면 되는구나 하고 쉽게 해결! 좀만 생각하면 쉽게 답을 얻을 수도 있군.

 

4835. N개의 정수가 들어있는 배열에서 이웃한 M개의 합을 계산하는 것은 디지털 필터링의 기초연산이다. M개의 합이 가장 큰 경우와 가장 작은 경우의 차이를 출력하는 프로그램을 작성하시오.

오.. 이건 보기만 해도 헷갈리고 어렵다.

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())		# N: 정수 개수 / M: 부분집합 요소 개수
    arr = list(map(int, input().split()))
    
    max_num = 0		# 최댓값
    min_num = 0		# 최솟값
    
    for i in range(N-M+1):
        sum_num = 0		# 구간합
        
        for j in range(i, i+M):
            sum_num += arr[j]
        
        # 무슨 값이든 0보다 클테니 굳이 max_num이 0일 때 의도적으로 구간합 부여 안해도 됨
        if sum_num > max_num:		
            max_num = sum_num
        
        if min_num == 0:			# min_num이 0이면 무조건 0값 나옴
            min_num = sum_num	# 그러니까 0이면 의도적으로 구간합 값 넣어줘야 함
       	
        if sum_num < min_num:
            min_num = sum_num
            
    print(f"#{test_case} {max_num-min_num}")

구간합 구하는 아이디어를 떠올리지 못해서 다른 분들의 코드 좀 참고했다. 전체 N개에서 M개를 빼면 그 부분집합의 개수가 나오는데, 거기에 +1을 해줘야지 마지막 부분집합의 합까지 구할 수 있다. 난 그렇게 이해함.

그리고 i개에서 i+M-1개까지 총 M개의 요소를 더해서 부분집합의 합을 구하면, 그 뒤에 max 및 min값 구하는 건 쉬움.

 

List1 문제가 이렇게 끝났다. 전기버스 문제 빼고는 나름대로 다 풀만 하기는 했는데, 방심은 금물이다. 항상 코드 짜기 전에 어떻게 구성하면 좋을지 주석으로 달아놓는 습관을 들이자!!